Solving 2^k ≡ n mod p with Modular Arithmetic

[CRGreathouse]

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

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?

 

[Hurkyl]

http://en.wikipedia.org/wiki/Discrete_logarithm

 

[CRGreathouse]

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.

 

[CRGreathouse]

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...?

 

[Hurkyl]

OK, follow-up now. What's the fastest discrete log algorithm for small primes?

Lookup table. Well, I suppose it depends on what you mean by "small".

 

[CRGreathouse]

Lookup table. Well, I suppose it depends on what you mean by "small".

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.

 

[dodo]

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.

 

[CRGreathouse]

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.

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).

 

[mhill]

my idea was a bit crazier, let's suppose we want to calculate $$f(x)=0 mod(p)$$

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

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 .

 

[CRGreathouse]

mhill, I don't understand. Say I wanted to find a k with 2^k = -2131 (mod 10000019). How does your method find that?

 

[mhill]

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

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

$$f: \mathcal R \rightarrow (0,10000019)$$

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 continuous 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

$$f(x)= frac( 2^{k}+2131)(10000019)^{-1}$$

where frac(x) is the fractional part of 'x'

 

[mhill]

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

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

$$f: \mathcal R \rightarrow (0,10000019)$$

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 continuous functions with discontinuties at the point 'a' so f(a)=kp in order to solve the congruences $$f(x)=0 mod(p)$$ however i do not know if there exists root-finding algorithm that can deal with discontinuities.