Small-base powm

[Torbjorn Granlund]

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 tricks are valuable only for limited exponents; as soon as the
exponent is large, the fraction of optimisable initil operatons will
become negligible.
  
  * One could find the largest k such that u^{2^k-1} fits in a single
    limb, and process k exponent bits at a time.
  
True.

  * One could handle powers of 2 specially, with shifts instead of
    multiplies.
  
Perhaps then with a separate mpn function.

  * Maybe one could extend this to take advantage of addmul_2, if present.
  
Not sure to follow you here.  You mean to use mul_2 for the multply by b
(or b^x for some x) and addmul_2 for some clever (non-principal)
reduction?

  * In general, for "small" U of size somewhere between a single limb, and
    full n limbs, there's got to be some threshold between using euclidean
    reduction of less than n limbs, to montgomery reduction of n limbs.
  
Makes sense.

  * Maybe one shouldn't do the n+1 to n reduction as a separate step, but
    somehow combine it with a montgomery reduction. E.g., one could
    probably write a pretty efficient function which computes u R B^{-1}
    (mod M) as an n-limb number. We then get some additional power of
    B^{-1} (mod M) into the result, but maybe they can be handled
    efficiently.
  
I need to think more about this...

  And if we do additional powm functions, with single limb modulo (and
  possibly large exponent, since reducing it requires the factorization of
  m), or single-limb exponent, or single-limb base, we get another
  challenge in naming all the functions. ;-)
  
We need to consult Dijstra on this.  :-)

I think our overhead for modexp ops with few-limb modulo is currently
terrible.  But it is not going to be easy to fix this, without resorting
to full assembly functions.


Torbjörn