- Paul:
> if f|x^f-x => f is Baillie-PSW

As far as I can tell, the Baillie-PSW test

> probable prime (where f=x^3-x-1)

was restricted to n = 2 or 3 (mod 5).

What do you do in the other 50% of the cases?

David - --- In primenumbers@y..., "djbroadhurst" <d.broadhurst@o...> wrote:
> Paul:

This agrees with:

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

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 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!) - --- In primenumbers@y..., "djbroadhurst" <d.broadhurst@o...> wrote:
> Paul: What do you say about n=41*61*101=1 mod 5 ?

Oh! I am going to use 5 rounds of Miller Rabin instead!

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

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

http://groups.yahoo.com/group/primenumbers/files/pseudo/52paul.txt

> 2-sPrP Fibonacci pseudoprimes to 52 bits

Thanks to Jason, for the 2-sPrP part.

Can someone check this bestiary, please?

David (about to disappear on another trip)