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

Re: [PrimeNumbers] Factors of 2^n-1 numbers

Expand Messages
  • Alan Eliasen
    ... Yes, I should have explained that. modPow[s,2,m] in the program is just the familiar modular exponentiation s^2 mod m. As you know, doing this in the
    Message 1 of 15 , May 25, 2004
    • 0 Attachment
      Kevin Acres wrote:
      > Thanks for writing back. However I'm not sure of everything that's
      > hidden in the "modPow" function at:
      >
      > http://futureboy.homeip.net/fsp/colorize.fsp?fileName=LucasLehmer.frink

      Yes, I should have explained that. modPow[s,2,m] in the program is just
      the familiar modular exponentiation s^2 mod m. As you know, doing this in the
      naïve way (doing an exponentiation and then taking the modulus) is far less
      efficient than the algorithms found by Montgomery et al to do the same operations.

      The last line, "return s==0" returns true if s is equal to zero (indicating
      this is indeed prime,) or false if s is anything but zero, indicating that
      it's composite.

      By the way, does anyone know if there's a bail-out condition that one could
      test to see if the number is definitely not prime? The usual descriptions of
      the Lucas-Lehmer test show it running through the entire loop, but I'd think
      there could be earlier indications that the number is not prime that would
      allow you to bail out earlier. I'm not talking about the usual pre-sieving
      that is done; I usually perform the well-known tests, and possibly strong
      pseudoprime tests base 3 before running the Lucas-Lehmer test.

      > <http://futureboy.homeip.net/fsp/colorize.fsp?fileName=LucasLehmer.frink>_If
      > it is this easy to prove a Mersenne number is prime then why does it
      > take such a long time to prove primality on some of the large ones?

      "Because they're big" is the only good reason I can give, I guess. When
      you're talking about multiplying, exponentiating, or taking the modulus of
      huge numbers like 2^20996011-1, it simply takes a long time. Note that the
      loop goes from 2 to n-1, meaning you have to go through the loop 20 million
      times for numbers of this size. A 20-million-bit number is a big number, indeed.

      Note that this is also a *proof* of primality for Mersenne numbers; proving
      primality for general numbers of this size tends to run far, far slower yet.

      --
      Alan Eliasen | "You cannot reason a person out of a
      eliasen@... | position he did not reason himself
      http://futureboy.homeip.net/ | into in the first place."
      | --Jonathan Swift
    Your message has been successfully submitted and would be delivered to recipients shortly.