? c=precprime(2^50)
1125899906842597
? Mod(2,c)^2^10^7
*** _^_: Warning: Mod(a,b)^n with n >> b : wasteful.
Mod(599926376112046, 1125899906842597)
? Mod(2,c)^lift(Mod(2,c-1)^10^7)
Mod(599926376112046, 1125899906842597)
This works because of Fermat's Little Theorem, though I haven't seen a proof. It could go recursively, but c-1 is not prime, so we would need something more powerful than Little Theorem.
No comments :
Post a Comment