2009/12/4 Jeff Gilchrist <[email protected]>: > On Fri, Dec 4, 2009 at 1:56 PM, Bill Hart <[email protected]> wrote: > >> I'm not sure I understand exactly what check you did up to 2^64. Did >> you take all the (composite) base 2 strong pseudoprimes and then test >> that BPSW eliminates them all? If you consider that to be a reliable >> result, I could use this in FLINT-Lite to give a guaranteed primality >> test up to 2^64 could I not? Was there some trial factoring done >> first? If so, what was the limit? > > Yes, I took all the composite base 2 pseudoprimes and tested them with > BPSW to ensure none of them were reported as pseudoprime. We are > double checking the results to make sure we didn't miss any base 2 > psp's but once that is done then yes using BPSW for anything under > 2^64 would be a guaranteed primality test.
Great!! Can't wait! > > Are you asking if we do trial factoring first before BPSW? Nicely's > BPSW code will actually try the primes < 1000 as trial prime divisors > first before doing the BPSW algorithm itself. No, I meant, was trial factoring done before testing for base 2 pseudoprimality. I guess not. I guess that you have a list of *all* base 2 pseudoprimes up to 2^64 and worked with that, i.e. base 2 pseudoprime test followed by BPSW is unconditional primality test to 2^64, and it is not necessary to do trial factor to 1000, then base 2, then BPSW (though it may be more efficient to do so). In other words, I can tune my own trial factoring cutoff to whatever limit I like and the result is still guaranteed. It is only an efficiency thing. > > Jeff. > > -- > > You received this message because you are subscribed to the Google Groups > "mpir-devel" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/mpir-devel?hl=en. > > > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
