1) There is Fermat's Little Theorem, stating that a^b = a^(b mod (p1)) 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 (p1)) + 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 20060323 at 10:12
