Pseudo prime tests

[David Cleaver]

On 6/14/2012 7:41 AM, Torbjorn Granlund wrote:
> bodrato writes:
>
>    You mean the BPSW primality test?
>
> I wasn't aware of this "BPSW" suggestion.
>
> What I am suggesting is similar, but I am not familiar with the Lucas
> test.  I also think one should do more trial dividing, and let its
> limits be operand dependent.
>
>    Some months ago, David Cleaver did post some implementation for this or
>    something similar. If he still is interested we might ask if he want to
>    assign the copyright of his code to FSF and/or revise our code.
>
> Good idea!

I would be happy to contribute code to GMP and/or the FSF.  Please let me know 
how best to accomplish this.

I've tested my implementation of the BPSW test against many primes and 
composites and it has always correctly identified them as such.  Well, it 
returns PRP for all primes because we do not know if there are any composites 
that can pass both the strong probable prime test to base 2 and the Lucas 
pseudoprime test.

I'm not sure how fast people would expect the BPSW test to be.  I think I 
remember seeing how much slower it should be compared to a single SPRP test, but 
I can't find the reference right now.  I have just run some timings on my SPRP 
test vs my BPSW test.  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.

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

-David C.