- #1
- 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:
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?
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;
Calculating the order of 2 mod p won't help -- unless it cost less than a comparison at each step, I guess. Thoughts?