About how much time would it take to test the primality of a billion digit Mersenne number with a typical processor?

Question

I'm wondering how long it might take to run a Lucas Lehmer primality test on a one billion digit Mersenne prime using a 3.0 ghz processor.

Answer 1

It would depend on too much, to get a good answer:

• Computer memory using the square minus 2 version of the test talked about on the wikipedia page, you'd need about 6.7 Gib ( gibibits) just to hold an intermediate value.
• That also takes about 11 quadrillion register multiplies. If you use grade school style arithmetic, at 3 billion per second, one iteration would take ... somewhere on the order of 3667 seconds (north of an hour) just for the squaring (so probably two if you include carries and adds and shifts for mod).
• You wanted to do roughly 3.32 billion of these right ? So hmmm that's about 757991 years ... ( No. you wanted to do a 3.32 billion bit number of these...).

Thankfully, we have quicker versions, and could find a potential factor by then...

Comments

• Even 64 bit registers would take about 189500 years without optimizations.

• Even 512 bit bus doesn't get us below 2690 years without better alogirthm implementation.

• Lastly ( might add these as updates), the 4096 bit bus of the nvidia pascal GP100 of 2015, still fails to get it to under 46 years.

ADDENDUM

• A space vs time tradeoff could do it all in one iteration ( plus connections to see if it goes to 0). But,would require about 1.2 EiB ( exbiBytes) all at once ( okay maybe half or less using equality among quadratic residues)
• We can parallel the adds and multiplies as we go to an extent, just need to stay within bandwidth.
• We need not check every prime exponent, if we use known properties of Mersenne exponents, or Mersenne divisors.
• We can use matrix multiplication to setup the multiplies.
• Etc.