best way to do "fermat" primalty checks
Décio Luiz Gazzoni Filho
decio at decpp.net
Sun Nov 13 20:39:44 CET 2005
On Nov 13, 2005, at 5:28 PM, Torbjorn Granlund wrote:
> Juergen Bullinger <juergen.bullinger at gmx.net> writes:
> I am not familiar with the miller rabin test, but from what I
> read about
> it, I think it would not be faster than the fermat check, because it
> repeats something like a fermat check several times. Am I right?
> Is there anybody who can tell how much a special powm-function
> with a
> fixed base of two would be faster than the normal powm-function?
> Do you expect any difference at all?
> 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.
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.
> 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. 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20051113/64cfa1a4/PGP-0001.bin
More information about the gmp-discuss