best way to do "fermat" primalty checks

[Décio Luiz Gazzoni Filho]

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?
>
> Basically.
>
>   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.

Décio
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
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