Monday, October 15, 2018

[nlzlxsyv] Avoiding the Pari/GP "wasteful" warning on repeated modular squarings

? 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 :