best way to do "fermat" primalty checks
Paul Zimmermann
Paul.Zimmermann at loria.fr
Mon Nov 14 09:00:44 CET 2005
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
More information about the gmp-discuss
mailing list