## Re: Baillie-PSW

Expand Messages
• ... This agrees with: http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html but page 18 of:
Message 1 of 17 , Sep 2, 2002
• 0 Attachment
> Paul:
> > if f|x^f-x => f is Baillie-PSW
> > probable prime (where f=x^3-x-1)
> As far as I can tell, the Baillie-PSW test
> was restricted to n = 2 or 3 (mod 5).
> What do you do in the other 50% of the cases?
This agrees with:
http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html
but page 18 of:
http://www.hipilib.de/prime/primality-tests-on-commutator-curves.ps.gz
tells a different story.
Paul
• Paul: What do you say about n=41*61*101=1 mod 5 ? By me, 2^n=2 mod n and lucasU(1,-1,n-1)=0 mod n. So it is 2-PrP (also 2-sPrP, I believe) and is a Fibonacci
Message 2 of 17 , Sep 2, 2002
• 0 Attachment
Paul: What do you say about n=41*61*101=1 mod 5 ?
By me, 2^n=2 mod n
and lucasU(1,-1,n-1)=0 mod n.
So it is 2-PrP (also 2-sPrP, I believe)
and is a Fibonacci pseudoprime, according
to Crandall-Pomerance book.
Baillie-PSW exclude it, because n=1 mod 5.
What would you do with it, please?
David (at speed, error prone!)
• ... Oh! I am going to use 5 rounds of Miller Rabin instead! I am way out of my depth with Lucas sequences. At least with the M-R there less that 1 in 1024
Message 3 of 17 , Sep 2, 2002
• 0 Attachment
> Paul: What do you say about n=41*61*101=1 mod 5 ?
> By me, 2^n=2 mod n
> and lucasU(1,-1,n-1)=0 mod n.
> So it is 2-PrP (also 2-sPrP, I believe)
> and is a Fibonacci pseudoprime, according
> to Crandall-Pomerance book.
> Baillie-PSW exclude it, because n=1 mod 5.
> What would you do with it, please?
> David (at speed, error prone!)
Oh! I am going to use 5 rounds of Miller Rabin instead!
I am way out of my depth with Lucas sequences.
At least with the M-R there less that 1 in 1024 chance of missing the
first counterexample.
Thanks for you help!
paul
• Oh dear, Paul, it seems that 252601=41*61*101 turned you off Fermat-Lucas when n^2=1 mod 5. FYI, I shall post 49,285 such double-pseudoprimes (I think, but no
Message 4 of 17 , Sep 2, 2002
• 0 Attachment
Oh dear, Paul, it seems that 252601=41*61*101
turned you off Fermat-Lucas when n^2=1 mod 5.

FYI, I shall post 49,285 such double-pseudoprimes
(I think, but no checking has been done!)
in the files area.

I hope someone will check that these
are all 2-sPrP and Fibonacci-PrP.

I was amazed by how prolific they appear to be.

None is congruent to 2 or 3 (mod 5),
so no \$620 cigar, of course!

[goes to post file..]

OK .... file is (I hope)