Baillie-PSW - Which variant is correct?
Henrik
A. n = 2 or 3 (mod 5); base-2 pseudoprime (Fermat); Fibonacci
pseudoprime.
B. strong pseudoprime to base 2; passes Lucas test A.
C. base-2 strong pseudoprime; in the sequence 5, -7, 9, -11, 13,...
find the first number D for which (D/n) = -1; Lucas pseudoprime test
with discriminant D on n.
D. base-2 pseudoprime; Lucas test; n = 2 (mod 5); Lucas pseudoprime
test.
Now some questions:
1. All of the above are claimed to be Baillie-PSW. This confuses me.
Which one is the right one?
2. My sources are old. Are there counter-examples to the Baillie-PSW
test today?
A big thank you!
Marcel Martin
>
> While searching for Baillie-PSW I found a few variants:
>
> A. n = 2 or 3 (mod 5); base-2 pseudoprime (Fermat); Fibonacci
> pseudoprime.
>
> B. strong pseudoprime to base 2; passes Lucas test A.
>
> C. base-2 strong pseudoprime; in the sequence 5, -7, 9, -11, 13,...
> find the first number D for which (D/n) = -1; Lucas pseudoprime test
> with discriminant D on n.
>
> D. base-2 pseudoprime; Lucas test; n = 2 (mod 5); Lucas pseudoprime
> test.
>
> Now some questions:
> 1. All of the above are claimed to be Baillie-PSW. This confuses me.
> Which one is the right one?
Probably all of them.
Personally, for Primo I use the variant C (except the test is a Lucas
strong pseudoprime test, i.e., not just a Lucas pseudoprime test).
> 2. My sources are old. Are there counter-examples to the Baillie-PSW
> test today?
AFAIK, none. Not only none was found but nobody succeeded in building
a counterexample.
Primo is used since now more than 3 years and, for each primality
certificate it produces, all intermediate 'primes' are checked with
this test. If one was composite, the certification would necessarily
have failed. This never occurred. In fact, it is presumably that no
composite less than, say, 10000 digits can fool this test.
BTW, in my docs, I don't use "Baillie-PSW" to refer to this test but
simply "BSW" (Baillie-Selfridge-Wagstaff). I have nothing against
Pomerance. Just, I reported the name I found in François Arnault's
thesis (page 72).
mm
--
http://www.ellipsa.net/
m...@ellipsa.no.sp.am.net ( suppress no.sp.am. )
Phil Carmody
> Probably all of them.
Yup, depending on which paper/book by which of B, P, S, or W, you look at.
> BTW, in my docs, I don't use "Baillie-PSW" to refer to this test but
> simply "BSW" (Baillie-Selfridge-Wagstaff). I have nothing against
> Pomerance. Just, I reported the name I found in François Arnault's
> thesis (page 72).
Crandall & Pomerance have P, S, & W as the financeers of the challenge,
for reference (3.8 Research problems, 3.41)
Phil
--
Unpatched IE vulnerability: Extended HTML Form Attack
Description: Cross Site Scripting through non-HTTP ports, stealing cookies, etc.
Published: February 6th 2002
Reference: http://eyeonsecurity.org/advisories/multple-web-browsers-vulnerable-to-extended-form-attack.htm
Marcel Martin
>
> Marcel Martin <m...@ellipsa.no.sp.am.net> writes:
> > Probably all of them.
>
> Yup, depending on which paper/book by which of B, P, S, or W, you look at.
Completely.
>
> > BTW, in my docs, I don't use "Baillie-PSW" to refer to this test but
> > simply "BSW" (Baillie-Selfridge-Wagstaff). I have nothing against
> > Pomerance. Just, I reported the name I found in François Arnault's
> > thesis (page 72).
>
> Crandall & Pomerance have P, S, & W as the financeers of the challenge,
> for reference (3.8 Research problems, 3.41)
Yes but, since the "P" is also the co-author of the book, the
reference is a little biaised :-)
More seriously, I just wanted to explain why I call this test the
"BSW" test (simply because this is this name I found in the source
I used when I programmed it).
Francois Grieu
henrik...@tyko.nu (Henrik) wrote:
> All of the above are claimed to be Baillie-PSW.
> Which one is the right one?
Much of the confusion comes from the fact that the test was
proposed in two articles near simultaneously.
Carl Pomerance, J.L. Selfridge and Samuel S. Wagstaff, Jr.
The Pseudoprimes to 25.10^9
in Mathematics of Computation, Volume 35, Number 151,
July 1980, pages 1003-1026.
Robert Baillie and Samuel S. Wagstaff, Jr.
Lucas Pseudoprimes
in Mathematics of Computation, Volume 35, Number 152,
October 1980, pages 1391-1417.
The articles are at
<http://mapage.noos.fr/ssw/>
Francois Grieu
Marcel Martin
Thanks for the papers (I had not the PSW one).
Though not all is quite clear [*], from now on, I will call these
tests the "BPSW" tests :-)
[*] In the PSW paper (page 1024), their description of the variants A
and B of the test refers to the SW paper. And, here, the publication
dates are not of a big help.
BTW, in my previous post, I wrote that I use the variant
D = 5,-7,9,-11,... with Primo. Yes but with NX I use the slightly
faster variant D = 5,21,45,...,(2k+1)^2-4,... (due to Wei Dai?).
I hope it is as good as the ones proposed by BPSW.