Algorithm for quick Fermat test ?



Is there a specific algorithm for computing 2^(n-1) mod n, faster than
the usual exponentiation by squaring?
The purpose is to do a quick Fermat primality test using base 2 rather
than another number.

.



Relevant Pages

  • Algorithm for quick Fermat test ?
    ... the usual exponentiation by squaring? ... The purpose is to do a quick Fermat primality test using base 2 rather ...
    (sci.crypt)
  • Re: Algorithm for quick Fermat test ?
    ... the usual exponentiation by squaring? ... The purpose is to do a quick Fermat primality test using base 2 rather ... Expanding a bit from Sebastian's suggestion and trying to reach something ...
    (sci.crypt)
  • Re: Algorithm for quick Fermat test ?
    ... the usual exponentiation by squaring? ... memory", ... A reasonable speedup is to perform a "square and multiply" scanning the ...
    (sci.crypt)
  • Re: Algorithm for quick Fermat test ?
    ... Sebastian Gottschalk writes: ... the usual exponentiation by squaring? ... memory". ...
    (sci.crypt)