20160825, 17:32  #1 
"Daniel Jackson"
May 2011
14285714285714285714
288_{16} 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 LLtest 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 worldrecord primes. Think about it. With an O(ln(n)) time complexity, you could do the following:
1. Test MM61 in 61 CPUdays. 2. Test MM89 in 89 CPUdays. 3. Test MM127 in 127 CPUdays. 4. Test MM521 in 521 CPUdays. Someday, we might find an algorithm that works that fast, or even faster. Last fiddled with by Stargate38 on 20160825 at 17:37 
20160826, 07:56  #2 
Jan 2007
Germany
12D_{16} 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 20160826 at 08:02 
20160826, 08:07  #3 
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. 
20160826, 11:35  #4  
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
Quote:
Code:
(08:28) gp > .078*(2^611) %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 toplevel: (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 Last fiddled with by science_man_88 on 20160826 at 11:58 

20160826, 20:28  #5 
"Daniel Jackson"
May 2011
14285714285714285714
2^{3}×3^{4} Posts 
I know one thing: It would take 566 trillion tons of iron atoms to make a multiqubit 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 20160826 at 20:32 
20160827, 00:20  #6  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
11×557 Posts 
Quote:


20160827, 00:41  #7  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
Last fiddled with by science_man_88 on 20160827 at 00:42 

20160827, 01:26  #8 
Aug 2006
3^{2}×5×7×19 Posts 
Bigger problem: Shor's algorithm is no faster than the LucasLehmer test, even though the latter only needs a classical computer to work.

20200128, 05:44  #9 
Oct 2019
5×19 Posts 
2^(2^611)+1 has a nontrivial factor: 360850409123604417744530775495739
It seems very unlikely that 2^(2^611)1 (aka. MM61) is prime. Otherwise, a huge prime was found, and the farfetched MersenneWagstaff conjecture was also denied. Too good to be true. Last fiddled with by Fan Ming on 20200128 at 05:47 
20200128, 23:29  #10 
∂^{2}ω=0
Sep 2002
República de California
26552_{8} Posts 
For the smallest of the OP's cases, MM61, I see the naive Moore'slawbased extrapolation was not yet done. So, let's see:
o throughput 2x every 2 years; o each doubling of exponent ==> 4x effort for LLtest, thus we double our wavefront exponents every 4 years; o current wavefront ~p = 2^27, so 6127 = 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 liquidH droplet" processor is 10^12 Hz. If we further assume some kind of magical massivelyparallel atomscale FFT algorithm that allows an entire modMM61 squaring to be done each tick of clock, we can do 10^12 ~ 2^40 LLtest iterations/sec, thus need ~2^21 sec = 24 days to finish. That's easy! 
20200129, 01:45  #11  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
11·557 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test  a1call  Miscellaneous Math  194  20180319 05:54 
Primality testing nonMersennes  lukerichards  Software  8  20180124 22:30 
Testing an expression for primality  1260  Software  17  20150828 01:35 
a new Deterministic primality testing  wsc812  Computer Science & Computational Number Theory  36  20130304 06:25 
a new primality testing method  jasong  Math  1  20071106 21:46 