best way to do "fermat" primalty checks

[Paul Zimmermann]

   I don't think the fact that the base is 2 could allow for any
   shortcuts.  However, all small bases could allow for somewhat
   faster arithmetic.

   If somebody would want to try to write a special mpz_powm for
   that case (perhaps mpz_ui_powm) that would be a welcome
   contribution to the GMP project.

There are two reasons why using small bases would ***not*** lead to a
significant improvement in the current mpz_powm code:

1) using small bases saves only in the plain multiplies, not in the squares.
   As Torbjo"rn said, the sliding-window method implemented in GMP reduces
   the number of plain multiplies.
2) the mpz_powm code uses Montgomery's multiplication, which replaces each
   residue a by a*R^l mod N. If a is smooth, there is no reason why
   a*R^l mod N would be smooth. [For primality checking, we could choose
   a such that a*R^l mod N is smooth, but due to 1) this would not gain much.]

About other points in that thread:

3) FFT utilization. I also don't know any algorithm that stays in the FFT
   domain. You have to perform a reduction after each multiply. Some authors
   proposed ways to perform that reduction in the FFT domain, but the cost
   is roughly the same.

4) about FFT and modular exponentiation. D. Phatak <phatak at umbc.edu> sent me
   a preprint where he improves on the "classical" Barrett reduction (which
   costs 1.5M(n) per reduction), and further improvements for modular exp.

5) about keeping FFT transforms. I wrote an extension of GMP to do that,
   see <http://www.loria.fr/~zimmerma/bignum/> [FFT Patch for gmp-4.1.4].
   For modular exponentiation where each square is reused only once, I'm not
   sure this will save much (see 3), but this can be useful for other
   applications. Any feedback is welcome on this interface.

Paul Zimmermann