Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

281 views

Skip to first unread message

Jan 9, 2004, 2:14:28 PM1/9/04

to

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?

2. My sources are old. Are there counter-examples to the Baillie-PSW

test today?

A big thank you!

Jan 9, 2004, 5:12:44 PM1/9/04

to

Henrik a écrit :

>

> 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?

>

> 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. )

Jan 10, 2004, 2:42:46 AM1/10/04

to

Marcel Martin <m...@ellipsa.no.sp.am.net> writes:

> Probably all of them.

> 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

Jan 10, 2004, 3:21:26 PM1/10/04

to

Phil Carmody a écrit :

>

> 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.

>

> 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).

Jan 11, 2004, 7:32:01 AM1/11/04

to

In article <dec97132.04010...@posting.google.com>,

henrik...@tyko.nu (Henrik) wrote:

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

Jan 11, 2004, 1:51:25 PM1/11/04

to

Francois Grieu a écrit :

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.

0 new messages

Search

Clear search

Close search

Google apps

Main menu