best way to do "fermat" primalty checks

[Torbjorn Granlund]

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