In a message dated 31/12/03 12:57:49 GMT Standard Time,

paulunderwood@... writes:

> --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote:

> > You are correct in showing that for your particular form of 2k-bit

> exponent

> > E, computing 2^E mod C takes about 2k squarings.

> > (The same is true for Mersennes.)

> >

> > Whereas for a general 2k-bit exponent, with about half of the bits

> being 1

> > and half 0, computing the residue would take about 2k squarings

> plus k

> > multiplications.

> >

> > So primality testing of your numbers is faster to just this extent

> (say 50%)

> > than for an arbitrary number of similar size.

> >

>

> A greater saving can be made for Carol/Kynea ( and other similar

> trinomial forms ) by implementing modular reduction using shifts (

> and mults )

>

1. I agree, Paul.

And many moons ago, Chris Nash had hoped to look into doing this for the

Gaussian Mersennes, but nothing came of it.

Jim?...

2. A correction to my post:-

Phil (the Silent) has pointed out that, provided the base for the Fermat test

is << C, the multiplications are essentially free, so the cost is just the 2k

squarings, i.e. instead of a 50% speed-up there is in fact no measurable

saving at all.

-Mike Oakes

[Non-text portions of this message have been removed]