mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2016-08-25, 17:32   #1
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

28816 Posts
Question 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
Stargate38 is offline   Reply With Quote
Old 2016-08-26, 07:56   #2
Cybertronic
 
Cybertronic's Avatar
 
Jan 2007
Germany

12D16 Posts
Default

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
Cybertronic is offline   Reply With Quote
Old 2016-08-26, 08:07   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11×557 Posts
Default

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.
retina is online now   Reply With Quote
Old 2016-08-26, 11:35   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
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 > (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 ?

Last fiddled with by science_man_88 on 2016-08-26 at 11:58
science_man_88 is offline   Reply With Quote
Old 2016-08-26, 20:28   #5
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

23×34 Posts
Default

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
Stargate38 is offline   Reply With Quote
Old 2016-08-27, 00:20   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11×557 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
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.
retina is online now   Reply With Quote
Old 2016-08-27, 00:41   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-08-27, 01:26   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by retina View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-01-28, 05:44   #9
Fan Ming
 
Oct 2019

5×19 Posts
Default

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
Fan Ming is offline   Reply With Quote
Old 2020-01-28, 23:29   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

265528 Posts
Default

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!
ewmayer is offline   Reply With Quote
Old 2020-01-29, 01:45   #11
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11·557 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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!
retina is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test a1call Miscellaneous Math 194 2018-03-19 05:54
Primality testing non-Mersennes lukerichards Software 8 2018-01-24 22:30
Testing an expression for primality 1260 Software 17 2015-08-28 01:35
a new Deterministic primality testing wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25
a new primality testing method 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.