How long will it be until MM61 is within practical reach of PRP/primality testing?

[Stargate38]

Assuming Moore's Law holds, how long (in years) will it be until we'll be able to run an LL-test on MM61 in less than 10 years (wall clock time)? What about MM89, MM107, and MM127? Will we ever find a faster algorithm than LL, even if it needs a quantum computer to run it? Hopefully, that will happen within our lifetimes, because I've been waiting for an algorithm with a time complexity of O(n), O(sqrt(n)), or even O(ln(n)), where "n" is the Mersenne exponent. That would really speed up the rate at which we find world-record primes. Think about it. With an O(ln(n)) time complexity, you could do the following:

1. Test MM61 in 61 CPU-days.
2. Test MM89 in 89 CPU-days.
3. Test MM127 in 127 CPU-days.
4. Test MM521 in 521 CPU-days.

Someday, we might find an algorithm that works that fast, or even faster.

[Cybertronic]

Never possible..or we find a MPrime Test only with exponent p.
Look , MM127 have 10^39 digits. Will you write out this number and each number 1mm ...you get 6 million lines and every line is 20 billion lightyears long. No chance only write in memory such number. MM61 have ~10^18 digits, the same problem. The LL TEST need for MM61 10^18 or so interations. In Memory is a number with 10^19 binary digits. One interation per seconds we have 73 billion years. Longer as our sunsystem exist.

[retina]

Right now, we don't know the answer. We don't know if it is never possible. We also don't know if it is ever possible.

While it might be fun to think about how many sheets of toilet paper it requires to write the number, that tells us nothing about whether or not it can be proven prime.

Waiting for a new algorithm won't help either. If it really matters to you then start working on the problem yourself, or fund people who can do the work for you.

[science_man_88]

Originally Posted by Stargate38

Assuming Moore's Law holds, how long (in years) will it be until we'll be able to run an LL-test on MM61 in less than 10 years (wall clock time)? What about MM89, MM107, and MM127? Will we ever find a faster algorithm than LL, even if it needs a quantum computer to run it? Hopefully, that will happen within our lifetimes, because I've been waiting for an algorithm with a time complexity of O(n), O(sqrt(n)), or even O(ln(n)), where "n" is the Mersenne exponent. That would really speed up the rate at which we find world-record primes. Think about it. With an O(ln(n)) time complexity, you could do the following:

1. Test MM61 in 61 CPU-days.
2. Test MM89 in 89 CPU-days.
3. Test MM127 in 127 CPU-days.
4. Test MM521 in 521 CPU-days.

Someday, we might find an algorithm that works that fast, or even faster.

(08:28) gp > .078*(2^61-1)
%3 = 179855754718668128.17800000000000000000
(08:28) gp > %/3600
%4 = 49959931866296.702271666666666666666667
(08:28) gp > %/24
%5 = 2081663827762.3625946527777777777777778
(08:28) gp > %/365
%6 = 5703188569.2119523141171993911719939117
(08:28) gp > %/10
%7 = 570318856.92119523141171993911719939117
(08:29) gp > (logint(%,2)+1)*1.5
  ***   at top-level: (logint(%,2)+1)*1.5
  ***                  ^------------------
  *** logint: incorrect type in logint (t_REAL).
(08:29) gp > (floor(log(%)/log(2))+1)*1.5
%8 = 45.000000000000000000000000000000000000

so assuming 78 ms per iteration doubling speed every 18 months we could expect to finish it in 10 years in about another 45 years. in theory with a big enough quantum ( or other) computer you could do all x^2-2 mod the mersenne number and string them together afterwards to get your result. the difficulty then would be when will a computer big enough be made. edit: in theory if we could find a pattern in the a such that s_(p-2)=a*x where x is a mersenne prime we could use that and the fact that x=2*k*p+1 proving that s_n is a mod p and calculate from that as a guess at least. so you up to helping find a pattern in the larger a values ?

[Stargate38]

I know one thing: It would take 566 trillion tons of iron atoms to make a multi-qubit processor capable of proving MM127 prime (or factoring it) with Shor's algorithm, 1.132 quadrillion tons for the memory, and 283 trillion tons to make a large enough quantum storage device, making it weigh about 5/18 the mass of Jupiter's moon Amalthea. It would have to be built in orbit, not on the ground, and it would probably take millennia to build. On the other hand, MM61 would probably be provable with 70/8675309 (about 0.000008068875855) moles of a given element. Either way, it would be prohibitively expensive to build with current technology. Just think of how much liquid helium would be needed to cool the former device.

[retina]

Originally Posted by Stargate38

I know one thing: It would take 566 trillion tons of iron atoms to make a multi-qubit processor capable of proving MM127 prime (or factoring it) with Shor's algorithm, 1.132 quadrillion tons for the memory, and 283 trillion tons to make a large enough quantum storage device, making it weigh about 5/18 the mass of Jupiter's moon Amalthea. It would have to be built in orbit, not on the ground, and it would probably take millennia to build. On the other hand, MM61 would probably be provable with 70/8675309 (about 0.000008068875855) moles of a given element. Either way, it would be prohibitively expensive to build with current technology. Just think of how much liquid helium would be needed to cool the former device.

Shor's algorithm could never prove a number prime, it is probabilistic in nature and if no factor is found you can't be sure that none exists.

[science_man_88]

Originally Posted by science_man_88

edit: in theory if we could find a pattern in the a such that s_(p-2)=a*x where x is a mersenne prime we could use that and the fact that x=2*k*p+1 proving that s_n is a mod p and calculate from that as a guess at least. so you up to helping find a pattern in the larger a values ?

yeah I just re-realized the error in that method for all exponents that are 1 or 7 mod 8; 2 is a quadratic residue which leads to an eventual residue of 0. so for all primes of those forms p happening as divisors before the (p-2)th step will lead to a 2 and no useful information about the mersenne number holding that exponent. so if anything the relation using the exponent is ruled to be not modular arithmetic related. at least within the LL test itself.

[CRGreathouse]

Originally Posted by retina

Shor's algorithm could never prove a number prime, it is probabilistic in nature and if no factor is found you can't be sure that none exists.

Bigger problem: Shor's algorithm is no faster than the Lucas-Lehmer test, even though the latter only needs a classical computer to work.

[Fan Ming]

2^(2^61-1)+1 has a non-trivial factor: 360850409123604417744530775495739
It seems very unlikely that 2^(2^61-1)-1 (aka. MM61) is prime.
Otherwise, a huge prime was found, and the far-fetched Mersenne-Wagstaff conjecture was also denied. Too good to be true.

[ewmayer]

For the smallest of the OP's cases, MM61, I see the naive Moore's-law-based extrapolation was not yet done. So, let's see:

o throughput 2x every 2 years;
o each doubling of exponent ==> 4x effort for LL-test, thus we double our wavefront exponents every 4 years;
o current wavefront ~p = 2^27, so 61-27 = 34 doublings needed ==> 34*4 = 136 years.

Unlike, say MM127, for MM61 the number of bits needed to store the modulus, assuming 1 bit per atom, is a mere 1/250,000th of a mole, thus it is at least conceivable that a processor which can handle a number that large could remain small enough to operate a frequency sufficiently high to perform computations at the needed speed. 1/250,000th of a mole of liquid H, at a density of 1 g/cm^3, could fit in a sphere of radius r ~= 0.01cm = 10^-4m. Diameter d = 2r = 2*10^-4m, figure speed of signal ~2/3 that of light in vacuo, i.e. ~2*10^8 m/sec, thus a signal needs ~10^-12 sec to cross such a sphere, hence the maximum possible operating frequency of our little "magical liquid-H droplet" processor is 10^12 Hz. If we further assume some kind of magical massively-parallel atom-scale FFT algorithm that allows an entire mod-MM61 squaring to be done each tick of clock, we can do 10^12 ~ 2^40 LL-test iterations/sec, thus need ~2^21 sec = 24 days to finish. That's easy!

[retina]

Originally Posted by ewmayer

For the smallest of the OP's cases, MM61, I see the naive Moore's-law-based extrapolation was not yet done. So, let's see:

o throughput 2x every 2 years;
o each doubling of exponent ==> 4x effort for LL-test, thus we double our wavefront exponents every 4 years;
o current wavefront ~p = 2^27, so 61-27 = 34 doublings needed ==> 34*4 = 136 years.

Unlike, say MM127, for MM61 the number of bits needed to store the modulus, assuming 1 bit per atom, is a mere 1/250,000th of a mole, thus it is at least conceivable that a processor which can handle a number that large could remain small enough to operate a frequency sufficiently high to perform computations at the needed speed. 1/250,000th of a mole of liquid H, at a density of 1 g/cm^3, could fit in a sphere of radius r ~= 0.01cm = 10^-4m. Diameter d = 2r = 2*10^-4m, figure speed of signal ~2/3 that of light in vacuo, i.e. ~2*10^8 m/sec, thus a signal needs ~10^-12 sec to cross such a sphere, hence the maximum possible operating frequency of our little "magical liquid-H droplet" processor is 10^12 Hz. If we further assume some kind of magical massively-parallel atom-scale FFT algorithm that allows an entire mod-MM61 squaring to be done each tick of clock, we can do 10^12 ~ 2^40 LL-test iterations/sec, thus need ~2^21 sec = 24 days to finish. That's easy!

But how long is the FFT, and how many bits per point? What is the minimum FP precision needed? Those guys in 136 years will need to know!