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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
http://gmplib.org/mailman/listinfo/gmp-devel
