# Modular arithmetic

1. Feb 25, 2008

### 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:

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. Feb 25, 2008

### Hurkyl

Staff Emeritus
3. Feb 25, 2008

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

4. Feb 25, 2008

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

5. Feb 25, 2008

### Hurkyl

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

6. Feb 25, 2008

### CRGreathouse

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.

7. Feb 26, 2008

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

8. Feb 26, 2008

### CRGreathouse

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

9. Feb 27, 2008

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

10. Feb 29, 2008

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

11. Mar 1, 2008

### 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 continous 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. perhaps in your case we should find the roots of [tex] f(x)= frac( 2^{k}+2131)(10000019)^{-1}$$

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

Last edited: Mar 1, 2008
12. Mar 1, 2008

### 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 continous 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.