I've been thinking a bit about how to handle powm with a single limb
base. In particular, the base 2 seems to be a popular choice for
primality testing.
Now, all algorithms do bitsize(e) modular squarings (ok, not all; with a
fix base precomputation as in Pippinger's algorithm
I think what you suggest is very close to the pseudo code at
https://gmplib.org/devel/, under the header mpz_powm and mpz_powm_ui.
But you suggest several additional refinements.
I wasn't considering of the case when the base is just a single limb,
but any time 2 * log(b) = log(m).
These
Torbjorn Granlund t...@gmplib.org writes:
These tricks are valuable only for limited exponents; as soon as the
exponent is large, the fraction of optimisable initil operatons will
become negligible.
The cost of all squarings are about 2*M(n) * exponent size, and in the
case of a small base,
