14295Re: [PrimeNumbers] Re: Modification of PFGW
- Dec 31, 2003In a message dated 31/12/03 12:57:49 GMT Standard Time,
> --- In firstname.lastname@example.org, mikeoakes2@a... wrote:1. I agree, Paul.
> > You are correct in showing that for your particular form of 2k-bit
> > 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 )
And many moons ago, Chris Nash had hoped to look into doing this for the
Gaussian Mersennes, but nothing came of it.
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.
[Non-text portions of this message have been removed]
- << Previous post in topic Next post in topic >>