Solving 2^k ≡ n mod p with Modular Arithmetic

  • Thread starter CRGreathouse
  • Start date
  • Tags
    Arithmetic
In summary, the conversation discusses finding a solution to 2^k ≡ n (mod p) where p is an odd prime and the current program being used. The conversation then moves on to discussing a better way to solve the problem and mentions the discrete logarithm algorithm for small primes and using baby step-giant step for performance improvements. There is also a discussion about using a lookup table and converting integers to floating-point. The conversation ends with a mention of using root-finding algorithms to handle discontinuities in the function.
  • #1
CRGreathouse
Science Advisor
Homework Helper
2,844
0
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:
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?
 
Physics news on Phys.org
  • #3
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
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
CRGreathouse said:
OK, follow-up now. What's the fastest discrete log algorithm for small primes?
Lookup table. :smile: Well, I suppose it depends on what you mean by "small".
 
  • #6
Hurkyl said:
Lookup table. :smile: 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.
 
  • #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.
 
  • #8
Dodo said:
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).
 
  • #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 .
 
  • #10
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
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 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

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

where frac(x) is the fractional part of 'x'
 
Last edited:
  • #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 continuous 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.
 

Related to Solving 2^k ≡ n mod p with Modular Arithmetic

1. How do you use modular arithmetic to solve equations involving exponentiation?

To solve equations involving exponentiation using modular arithmetic, you need to first convert the equation into a congruence modulo a given number (p). This means that the remainder of the equation when divided by p should be equal to a given value (n). Once you have a congruence equation, you can use properties of modular arithmetic such as modular multiplicative inverse and modular exponentiation to find the value of the exponent (k).

2. What is the purpose of solving equations using modular arithmetic?

The purpose of solving equations using modular arithmetic is to find the value of an unknown variable in a congruence equation. This can be useful in many fields such as cryptography, coding theory, and number theory.

3. How can I determine the value of k in 2^k ≡ n mod p?

To determine the value of k in the equation 2^k ≡ n mod p, you can use the discrete logarithm function in modular arithmetic. This means that you need to find the smallest positive integer k such that 2^k is congruent to n modulo p. This can be done by using modular exponentiation and checking the values of 2^k mod p until you find a match for n.

4. Can this method be extended to solve equations with different bases?

Yes, this method of using modular arithmetic to solve equations can be extended to other bases such as 3, 4, 5, etc. The process would be the same, where you convert the equation into a congruence modulo a given number and then use modular arithmetic properties to find the value of the exponent.

5. Are there any limitations to using modular arithmetic to solve equations?

One limitation of using modular arithmetic to solve equations is that it only works for certain types of equations, specifically those involving exponents and remainders. Additionally, the solutions obtained using modular arithmetic may not always be unique, as there can be multiple values of k that satisfy the congruence equation.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
876
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Precalculus Mathematics Homework Help
Replies
1
Views
776
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
930
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
16
Views
2K
Back
Top