Pseudo prime tests

[bodrato at mail.dm.unipi.it]

Ciao David,

Il Ven, 15 Giugno 2012 2:19 am, David Cleaver ha scritto:
> I would be happy to contribute code to GMP and/or the FSF.  Please let
> me know how best to accomplish this.

The first step is: produce a valuable piece of code; the next one is some
paperwork (copyright assignments to FSF), but I don't remember the
details.

> I'm not sure how fast people would expect the BPSW test to be.

I'd expect it to be comparable in speed with the current
mpz_probab_prime_p (tested_number, 5);
with five or six repetitions.

> I can't find the reference right now.  I have just run some timings on
> my SPRP test vs my BPSW test.

When you compare two algorithms, it makes sense to implement both (using
comparable skills and efforts) and compare them...
But, if you want to propose your code for insertion into GMP, you should
better compare your code with the code in the library.

> It looks like the BPSW test takes 9 times longer to run
> than the SPRP test.  I think we should be able to reduce this quite
> a bit, since I implemented it all with mpz's and I did not necessarily
> use the fastest algorithms in my implementation.

I wrote some code for the strong Lucas primality test, with Selfridge
parameters. It takes 3-5 times the time of a Miller-Rabin iteration. It
should be optimised, using Montgomery reduction, and possibly using some
cleverer formulas. (you can also use it for your code, as any other piece
of code already assigned to FSF)

> Please let me know what you think of the above and if you are still
> interested in having a BPSW test integrated into GMP.

I am. If we obtain an efficient code, I'm confident that the other
developers will accept the insertion.


But there still are some questions.

After trial division, BPSW requires a base-2 Miller-Rabin test, i.e.
computing some powers of 2 modulo N, the exponent being
(N-1)/2^some_thing.
The formulas I've found to compute Lucas numbers use some powers of Q
modulo N, the exponent being (N+1)/2^some_exp.
(N+1) and (N-1) typically share most of the bits, Q=2 when we choose D=-7
and we can choose it when jacobi(-7/N)=-1, i.e. roughly half of the times.
It would be nice to mix the two tests in one, whenever we can. Do you
think we can use D=-7 even if jacobi(5/N)=-1 and we should use D=5
according to the rule "the first in the list 5, -7, 9, -11, 13,..."?


The attached code shows the times of Lucas test compared to base-2
Miller-Rabin, for Mersenne numbers (where Miller-Rabin gives many false
positives, and Lucas-Lehmer is used by my code) and factorials+1 (where
the search for a small D such that jacobi(D/N)=-1 is longer).

Best regards,
Marco

-- 
http://bodrato.it/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: primetest.c
Type: text/x-csrc
Size: 13924 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120623/7ab78100/attachment.bin>