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

14294Re: Modification of PFGW

Expand Messages
  • Paul Underwood
    Dec 31, 2003
      --- 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 )

      Paul
    • Show all 19 messages in this topic