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

22·3·5 Posts
Default

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

Therefore,
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