GMP PRP programs

[paulunderwood]

This is the first in a series of three GMP based PRP programs; It does A times Fermat PRP tests followed by B times Lucas PRP tests. The second program will do the same but with "Jacobi strength" ; The third will do strong tests.

Note parts of the codes can be replaced with mpz_powm(res, base, something, align);

[paulunderwood]

Here is a program that does Miller-Rabin (Fermat) and the same sort of thing in Lucas terms.

[paulunderwood]

Here attached is a GMP program that does a base 2 Fermat PRP test followed by a Lucas binary chain PRP test over x^2-2^r*x+1 where jacob(4^r-4,n) is -1. It has a section to deal with Fermat numbers, and products of these.

Both Fermat and Lucas parts can be made strong. It does no trial division.

It is nearly as fast as GMP's mpz_probab_prime_p function. The speed comes form using 2^r in the chain and I believe a hand-crafted "mpn" program should be even quicker and as such would be quicker than mpz_probab_prime_p.

(It is similar to Pari/GP's ispseudoprime function, but uses 2^r instead of minimal "a"; The latter has to propogate more than the former when subtraction is done in the chain.)