Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular arithmetic

  1. Feb 25, 2008 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I'm trying to write a program which finds a solution to [itex]2^k\equiv n\pmod p[/itex] where p is an odd prime. At the moment I'm using a program like this:

    Code (Text):
    power = 2;
    exp = 1;
    while (power != n) {
      power = (2 * power) % p; // actually coded as an addition and conditional subtract
      if (power == 1)
        return "No solution";
      exp += 1;
    }
    return exp;
    which can take time proportional to p in the worst case -- which is not rare. Does anyone know of a better way to do this?

    Calculating the order of 2 mod p won't help -- unless it cost less than a comparison at each step, I guess. Thoughts?
     
  2. jcsd
  3. Feb 25, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

  4. Feb 25, 2008 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Heh, of course. Sorry, transforming the problem into the form above took a lot of abstraction, and I totally missed the obvious connection since I was used to seeing the trees for the forest.
     
  5. Feb 25, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    OK, follow-up now. What's the fastest discrete log algorithm for small primes? Say I wanted to calculate a discrete logarithm for various numbers mod the first ten million to one billion primes. Since the individual primes are small the powerful methods seem to be too much, but since I'm doing millions of applications speed is still relevant.

    I'm going to try out baby step-giant step on this problem to see if it helps performance. Unfortunately this will slow down other parts of my program, but the gains should be worth it...?
     
  6. Feb 25, 2008 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Lookup table. :smile: Well, I suppose it depends on what you mean by "small".
     
  7. Feb 25, 2008 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The prime moduli would be 6-9 digits long. I'll be doing at least 6 million, and perhaps as many as a billion, total discrete log calculations. (If the algorithm turns out to be faster than expected, I might do yet more.)

    Edit: And congratulations on passing 10,000 posts.
     
  8. Feb 26, 2008 #7
    If you work on a language that allows bit operations, it could be helpful to convert an integer to floating-point, and extract the exponent from the IEEE representation.
     
  9. Feb 26, 2008 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Doesn't help. I'm looking for the discrete log in GF(p), not the binary (or natural) log over the reals.

    The discrete log (base 2) of -2131 = 3 (mod 11) is 8, because 2^8 = 3 (mod 11). That 3 is 1.1 x 10^1 in binary doesn't get me there (as far as I know).
     
  10. Feb 27, 2008 #9
    my idea was a bit crazier, let's suppose we want to calculate [tex] f(x)=0 mod(p) [/tex]

    then using Newton iterative method [tex] x_{n+1}=x_{n}- \frac{f(x_{n}}{f'(x_{n})} mod(p) [/tex]

    for example if through the iteration process you get 6.7890345 and p=5 then taking the previous quantity 0 mod(5) we get 1.7890345 .
     
  11. Feb 29, 2008 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    mhill, I don't understand. Say I wanted to find a k with 2^k = -2131 (mod 10000019). How does your method find that?
     
  12. Mar 1, 2008 #11
    i do not know , my question is to use a root-finding algorithm that allow a function f(x) to be non-continous for example your function

    [tex] 2^{k}+2131 [/tex] is smooth, however if we impose that f(x) in your particular problem is of the form

    [tex] f: \mathcal R \rightarrow (0,10000019) [/tex]

    then f(x) would be discontinous at the points f(x)=k10000019 for any integer 'k' . My idea was to replace the initial function f(x) by a piecewise continous functions with discontinuties at the point 'a' so f(a)=kp in order to solve the congruences [tex] f(x)=0 mod(p) however i do not know if there exists root-finding algorithm that can deal with discontinuities.

    perhaps in your case we should find the roots of

    [tex] f(x)= frac( 2^{k}+2131)(10000019)^{-1} [/tex]

    where frac(x) is the fractional part of 'x'
     
    Last edited: Mar 1, 2008
  13. Mar 1, 2008 #12
    i do not know , my question is to use a root-finding algorithm that allow a function f(x) to be non-continous for example your function

    [tex] 2^{k}+2131 [/tex] is smooth, however if we impose that f(x) in your particular problem is of the form

    [tex] f: \mathcal R \rightarrow (0,10000019) [/tex]

    then f(x) would be discontinous at the points f(x)=k10000019 for any integer 'k' . My idea was to replace the initial function f(x) by a piecewise continous functions with discontinuties at the point 'a' so f(a)=kp in order to solve the congruences [tex] f(x)=0 mod(p) [/tex] however i do not know if there exists root-finding algorithm that can deal with discontinuities.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Modular arithmetic
  1. N^2 Modular Arithmetic (Replies: 3)

  2. Modular arithmetic (Replies: 1)

  3. Modular arithmetic (Replies: 4)

Loading...