--- In

primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:

>

>

>

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

>

In FFT land, this neat version would save 2 forward transforms for each bit, compared to my rather clumsy left-to-right algorithm given in section 4,

Paul