best way to do "fermat" primalty checks
Torbjorn Granlund
tege at swox.com
Sun Nov 13 20:51:36 CET 2005
Décio Luiz Gazzoni Filho <decio at decpp.net> writes:
The idea is to replace a general-purpose multiplication by an
addition chain (in the case 2, a single addition). PFGW does this
for exponentiations with bases < 256, I believe.
My point is that when computing "smallbase^bigexp mod bigmod",
the time will be O(M(log(bigmod)) + O(log(bigmod)). The 2nd term
could be optimized by using addition instead of multiplication,
but since the 2nd term is negligible in the first place, we might
as well handle all small bases.
> 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.
Such an improvement would be very pronounced compared to a
vanilla binary exponentiation algorithm and `typical'
exponents. As GMP uses a sliding-window algorithm I don't expect
the improvement to be large.
I thought so too at first. (I actually typed in a reply with
about the same words you use above...) But I think we could get
good improvements nevertheless.
(For those who are not familiar with the effects of the
sliding-window algorithm, let me explain that it avoids most of
the multiplications by the base, which makes the algorithm spend
most if its time squaring. With a plain implementation, one will
do q/2 multiplications and q squarings, for a random q-bit
exponent.)
Also, I'm not sure how applicable
it would be outside of the example in question (PRP
testing). Still, it would be useful as a hardcoded subroutine of
the PRP test code.
Useful, I think. The current mpz_probab_prime_p implementation
uses a plain fermat test first. That test rejects lots of
composite numbers, using less time than one Miller-Rabin test.
--
Torbjörn
More information about the gmp-discuss
mailing list