mersenneforum.org How long will it be until MM61 is within practical reach of PRP/primality testing?
 Register FAQ Search Today's Posts Mark Forums Read

 2016-08-25, 17:32 #1 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 28816 Posts How long will it be until MM61 is within practical reach of PRP/primality testing? 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. Last fiddled with by Stargate38 on 2016-08-25 at 17:37
 2016-08-26, 07:56 #2 Cybertronic     Jan 2007 Germany 12D16 Posts 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. Last fiddled with by Cybertronic on 2016-08-26 at 08:02
 2016-08-26, 08:07 #3 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 11×557 Posts 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.
2016-08-26, 11:35   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 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.
Code:
(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 > (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 ?

Last fiddled with by science_man_88 on 2016-08-26 at 11:58

 2016-08-26, 20:28 #5 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 23×34 Posts 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. Last fiddled with by Stargate38 on 2016-08-26 at 20:32
2016-08-27, 00:20   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11×557 Posts

Quote:
 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.

2016-08-27, 00:41   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2016-08-27 at 00:42

2016-08-27, 01:26   #8
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 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.

 2020-01-28, 05:44 #9 Fan Ming   Oct 2019 5×19 Posts 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. Last fiddled with by Fan Ming on 2020-01-28 at 05:47
 2020-01-28, 23:29 #10 ewmayer ∂2ω=0     Sep 2002 República de California 265528 Posts 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!
2020-01-29, 01:45   #11
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11·557 Posts

Quote:
 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!

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 194 2018-03-19 05:54 lukerichards Software 8 2018-01-24 22:30 1260 Software 17 2015-08-28 01:35 wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25 jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 15:08.

Thu Apr 22 15:08:21 UTC 2021 up 14 days, 9:49, 0 users, load averages: 1.71, 1.92, 2.04

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.