--- In

primenumbers@yahoogroups.com,

"paulunderwooduk" <paulunderwood@...> wrote:

> but surely Grantham's b^((n-1)/2) can be tested first,

> making it 1 + 2 selfridge?

Yes. I wrote 2 + 1 for Frobenius only to paraphrase CP

Algorithm 3.5.9. But batch processing should be done as 1 + 2,

as per BPSW 1 + 2. Note that in your 1 + 2 method of Section 9

where "batch testing was sped up by pre-screening with the

1 selfridge test", we can use CP to speed up your (less often)

used 2-selfridge Lucas test, using the CP Lucas chain

V(2*n) = V(n)^2 - 2 mod N

V(2*n+1) = V(n+1)*V(n) - c mod N

where c = (4+x)^2/(2*x+5) - 2 mod N

is precomputed, using modular inversion.

Then you would have a squaring and a multiplication,

as against the two multiplications in your

left-right binary method of Section 4.

Squaring and multiplication are taken as equally

costly for selfridge counting, but a squaring may be

cheaper than a multiplication, in practice?

But as that small difference affects only O(1/log(N))

of the cases tested in batch testing, who really cares?

David