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

Re: [PrimeNumbers] Digest Number 1340

Expand Messages
  • Will Edgington
    If 2^p -1 is a prime number then 2 ^p does not have a divisor (
    Message 1 of 2 , Jun 27, 2004
      If 2^p -1 is a prime number then 2 ^p does not have a divisor (< 2^ p -1 and
      > 2) which yields a remainder of 1. I call this a prime 1 in distinction
      with ordinary primes which are prime 0. There are of course other higher order
      primes prime 2 etc.
      Because 2^p is factorable, it might be easier to search for prime 1 numbers.
      If one is found then 2^p - 1 would be a Mersenne prime. Does this help?

      If I follow what you are saying, it does indeed help and is already
      being used by many programs, including George Woltman's Prime95 and
      the factoring programs of the mers package that I maintain.

      What those programs do - instead of actually calculating 2^p - 1 and
      then dividing it by each possible factor - is calculate the power of 2
      modulo each possible factor and see if the result is 1. Since the
      possible factors being tested are much smaller than 2^p - 1 itself,
      the modulo (remainder) operations are much faster ... so much faster,
      in fact, that they easily more than making up for having to
      recalculate 2^p every time. But the programs also don't calculate 2^p
      modulo the possible factor by doubling p times; there's a faster way
      involving squaring (from Knuth, if I recall correctly).

      But even that isn't fast enough to prove that 2^p - 1 is prime except
      for _very_ small values of p (less than 100, say); there are simply
      too many possible factors less than the square root of 2^p - 1.
      For that, the Lucas-Lehmer test is needed. See George's web site,
      below, and others for more details.


      George Woltman's site, including Prime95 (free) and GIMPS, the Great
      Internet Mersenne Prime Search, discoverer of the last seven largest
      primes known:

      My own Mersenne related web pages, including the mers package (free):
    Your message has been successfully submitted and would be delivered to recipients shortly.