Loading ...
Sorry, an error occurred while loading the content.

14295Re: [PrimeNumbers] Re: Modification of PFGW

Expand Messages
  • mikeoakes2@aol.com
    Dec 31, 2003
    • 0 Attachment
      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.

      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]
    • Show all 19 messages in this topic