Sorry, an error occurred while loading the content.

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

Expand Messages
• ... 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 10:31 AM
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.