View Single Post
Old 2006-03-23, 10:03   #2
Jushi's Avatar
Sep 2005

22·3·5 Posts

1) There is Fermat's Little Theorem, stating that a^b = a^(b mod (p-1)) mod p, whenever p is prime.

p is a factor of a^b + c
if and only if
a^b + c = 0 mod p
if and only if
a^(b mod (p-1)) + c = 0 mod p

2) a^b mod p is reasonable easy to compute, because you can reduce mod p at every step.

Last fiddled with by Jushi on 2006-03-23 at 10:12
Jushi is offline   Reply With Quote