7 ms·

All Mersenne prime exponents below 100m tested at least once

101 points by potiuper 6y ago

deleted 6y ago
[deleted]
stillbourne 6y ago
I think it got hugged to death.
- imglorp 6y ago
  https://webcache.googleusercontent.com/search?q=cache:https://www.mersenne.org/report_milestones/ https://webcache.googleusercontent.com/search?q=cache:https:... https://web.archive.org/web/*/https://www.mersenne.org/report_milestones/ https://web.archive.org/web/*/https://www.mersenne.org/repor...
schoen 6y ago
When I was at EFF, I helped run the Cooperative Computing Awards project (https://www.eff.org/awards/coop/ https://www.eff.org/awards/coop/), which was funded decades ago by an individual donor and provides cash rewards for finding prime numbers of certain sizes. Because of EFF's advocacy for cryptography, people always thought that there was a more direct connection between the Mersenne prime search and cryptographic techniques, but the connection is at best distant and tenuous. The record primes that GIMPS finds and that can receive EFF's awards are * much (much much) bigger than the primes that we use for cryptography * too big to do almost any kind of practical computation with * not secret, so couldn't be used as part of a secret key The distribution or explicit values of Mersenne primes (and, correspondingly, perfect numbers) also don't really help in our assessment of the difficulty of the RSA problem or the security of public-key cryptography, because they aren't closely related to any of the fastest factorization algorithms that apply to arbitrary numbers. (Mersenne primes are much easier to deterministically test for primality than numbers in general, which is why the record primes that GIMPS finds are Mersenne primes. The runtime complexity of primality-testing algorithms for special-form numbers is sometimes much less than algorithms for an arbitrary number, and this is a great example.) I think the main contribution of projects like GIMPS to cryptography and computer security lies in getting people more interested in number theory and mathematics in general. Hopefully that will lead to faster improvements in humanity's knowledge of mathematics in ways that lead to more secure public-key algorithms or to better public assessments of the algorithms that we have now. (Although a lot of the important current research on public-key cryptography is not about factorization but rather about elliptic-key systems and post-quantum systems.) I always felt I had a hard time explaining to people that the awards existed in order to publicize the idea of cooperative distributed computing projects, which were quite novel when EFF's awards were first created, and which were a demonstration of the power of the Internet to help people who've never even met each other work together. (The awards, contrary to the hopes and dreams of math enthusiasts and cranks around the world, didn't anticipate progress through new research or ideas so much through more volunteer computer time.) Probably today we have ample other demonstrations of that power, and that concept is no longer in much doubt, and the GIMPS project probably no longer even registers for most people as a particularly impressive example. But it is impressive in continuing to set multiple world records on one of the simplest, purest, most basic mathematical problems.
- Blahah 6y ago
  > not secret Clearly, no smaller primes are secret either, nor are they so numerous that iterating over them is computationally difficult. And mathematically, anyone can discover primes. Why does it matter whether primes are secret?
  - centimeter 6y ago
    Some cryptosystems like RSA are based on secret primes. Density of primes is about 1/log(n), so there are plenty of primes to choose from. Some cryptosystems like ECDSA are based on secret elements selected from a field, and the primes there are public.
    - Blahah 6y ago
      Sorry, just to be clear, they are obscure, not secret. Anyone can compute primes. No prime is secret.
      - ifdefdebug 6y ago
        Like in: anyone can combine characters. No password is secret?
      - grifball 6y ago
        I guess I don't fully understand this, but RSA works so there MUST be "secret" primes (as in, then can be randomly generated like a symmetric key can).
      - segfaultbuserr 6y ago
        They are secret. "Secret key" is a technical term in cryptography, and there are thousands of research papers published with this term [0], including a paper by Eli Biham and Adi Shamir on "Differential fault analysis of secret key cryptosystems". Using you believe that you are more knowledgeable in crypto than Adi Shamir (The "S" in "RSA") and insist on using an alternative definition of "secret" not accepted by cryptographers and infosec researchers, there should be no problem using the word "secret". Otherwise, reductio ad absurdum, Following the same line of logic, all cryptography is "security through obscurity" because there exists a secret key, which is not incorrect. The practice of hiding the design of a system is obscurity, the practice of hiding a specific key to a ciphertext is security, not obscurity, as long as the method of generating and using it is publicly available. If there's nothing to reverse engineer, there can be no obscurity. The method of finding a symmetric key or finding a RSA key is well-known, not obscured, it's simply the size of the problem is not computationally tractable in practice by today's computers. [0] https://scholar.google.com/scholar?q=secret+key https://scholar.google.com/scholar?q=secret+key
lkbm 6y ago
Looking at the recent history: 2020-11-27 All exponents below 99 million tested at least once. 2020-11-17 All exponents below 98 million tested at least once. 2020-11-17 All exponents below 97 million tested at least once. 2020-11-09 All exponents below 96 million tested at least once. 2020-11-03 All exponents below 95 million tested at least once. 2020-10-24 All exponents below 94 million tested at least once. 2020-10-09 All exponents below 93 million tested at least once. 2020-10-04 All exponents below 92 million tested at least once. 2020-06-20 All exponents below 91 million tested at least once. 2020-04-09 All exponents below 90 million tested at least once. 2020-03-01 All exponents below 89 million tested at least once. What happened in June/July that caused it to stop, and in October to make it suddenly restart? Did they just switch from sequential to a grouping that checked all but a small portion of each million undone until November? September 17, 2020 All tests below 53 million verified. Makes me think part of it is them spending extra time verifying old tests. Just curious 1. if that's all it is and 2. why / whether this was triggered by something. Was there a bug found that raised doubt in previous tests? EDIT: Formatting
- barkingcat 6y ago
  I'm only tangencially related to the project, but I do have a spare machine running the software. Yes, there was a big push to re-verify old abandoned tests. First, understand that the project requires multiple tests results from each exponent - I believe it needs a triplicate confirmation (ie 3 different computers have to run the same test and all have to match) At some point, they developed a new, different algorithm that can do the check in one go (but it's more expensive computationally). However, most of the pre-existing work was done using the type of calculation that needed the triplicate check. There were a lot of exponents where some computer claimed one of the "verification tests" (ie it was already rejected as a prime, but we needed 2 more computers to verify), but then stopped mid way (it's pretty common since these primality tests take about 3-5 days on a modern fast threadripper - so it could take up to a month on slower machines from years ago). It's very unlikely that these exponents signified primes (since they were already verified to NOT be prime by 1 computer, and it's just the rechecks that are pending) These abandoned exponents formed a huge amount of "leftovers" that people didn't want as work units because they are most likely not prime, and if you were hunting for primes, these are not the work you want to do. So at some point, the project said they wanted a big push into picking up abandoned re-verifications and giving them a much higher priority to computers that could complete the test in a few days [either by finishing off what was left of the triplicate check, or by using the new algorithm that just needed one pass] - thus getting them out of the queue once and for all for good. If you have a fast computer (ie modern day i9, threadripper, xeon, anything with AVX512, etc) chances are you were assigned this type of rechecking task unless you rejected the work units. It's not just the gap you noticed in June, this whole project of looking for and verifying old exponents has been ongoing for the bulk of 2020. Another idea is that the project is always trying out new number techniques and algorithms and always looking for new instruction sets to use etc - a change or tweek in algorithm could cause this kind of "pause" as well, the client computers don't make the shift all at once (there's likely some verification, where a small subset of clients run both algorithms in parallel to see if the results are the same, etc) and then machines are moved onto the new algorithm as verifications are complete, etc. EDIT: As I wrote this post, I started remembering more about the different algorithms the projects used. All of the text above can be check with the prime95 forums, where they discuss these algorithm changes, the push to re-verify, etc.

101 points by potiuper 6y ago

deleted 6y ago

[deleted]

stillbourne 6y ago

I think it got hugged to death.

imglorp 6y ago
https://webcache.googleusercontent.com/search?q=cache:https://www.mersenne.org/report_milestones/ https://webcache.googleusercontent.com/search?q=cache:https:... https://web.archive.org/web/*/https://www.mersenne.org/report_milestones/ https://web.archive.org/web/*/https://www.mersenne.org/repor...

schoen 6y ago

When I was at EFF, I helped run the Cooperative Computing Awards project (https://www.eff.org/awards/coop/ https://www.eff.org/awards/coop/), which was funded decades ago by an individual donor and provides cash rewards for finding prime numbers of certain sizes. Because of EFF's advocacy for cryptography, people always thought that there was a more direct connection between the Mersenne prime search and cryptographic techniques, but the connection is at best distant and tenuous. The record primes that GIMPS finds and that can receive EFF's awards are * much (much much) bigger than the primes that we use for cryptography * too big to do almost any kind of practical computation with * not secret, so couldn't be used as part of a secret key The distribution or explicit values of Mersenne primes (and, correspondingly, perfect numbers) also don't really help in our assessment of the difficulty of the RSA problem or the security of public-key cryptography, because they aren't closely related to any of the fastest factorization algorithms that apply to arbitrary numbers. (Mersenne primes are much easier to deterministically test for primality than numbers in general, which is why the record primes that GIMPS finds are Mersenne primes. The runtime complexity of primality-testing algorithms for special-form numbers is sometimes much less than algorithms for an arbitrary number, and this is a great example.) I think the main contribution of projects like GIMPS to cryptography and computer security lies in getting people more interested in number theory and mathematics in general. Hopefully that will lead to faster improvements in humanity's knowledge of mathematics in ways that lead to more secure public-key algorithms or to better public assessments of the algorithms that we have now. (Although a lot of the important current research on public-key cryptography is not about factorization but rather about elliptic-key systems and post-quantum systems.) I always felt I had a hard time explaining to people that the awards existed in order to publicize the idea of cooperative distributed computing projects, which were quite novel when EFF's awards were first created, and which were a demonstration of the power of the Internet to help people who've never even met each other work together. (The awards, contrary to the hopes and dreams of math enthusiasts and cranks around the world, didn't anticipate progress through new research or ideas so much through more volunteer computer time.) Probably today we have ample other demonstrations of that power, and that concept is no longer in much doubt, and the GIMPS project probably no longer even registers for most people as a particularly impressive example. But it is impressive in continuing to set multiple world records on one of the simplest, purest, most basic mathematical problems.

Blahah 6y ago
> not secret Clearly, no smaller primes are secret either, nor are they so numerous that iterating over them is computationally difficult. And mathematically, anyone can discover primes. Why does it matter whether primes are secret?
- centimeter 6y ago
  Some cryptosystems like RSA are based on secret primes. Density of primes is about 1/log(n), so there are plenty of primes to choose from. Some cryptosystems like ECDSA are based on secret elements selected from a field, and the primes there are public.
  - Blahah 6y ago
    Sorry, just to be clear, they are obscure, not secret. Anyone can compute primes. No prime is secret.
    - ifdefdebug 6y ago
      Like in: anyone can combine characters. No password is secret?
    - grifball 6y ago
      I guess I don't fully understand this, but RSA works so there MUST be "secret" primes (as in, then can be randomly generated like a symmetric key can).
    - segfaultbuserr 6y ago
      They are secret. "Secret key" is a technical term in cryptography, and there are thousands of research papers published with this term [0], including a paper by Eli Biham and Adi Shamir on "Differential fault analysis of secret key cryptosystems". Using you believe that you are more knowledgeable in crypto than Adi Shamir (The "S" in "RSA") and insist on using an alternative definition of "secret" not accepted by cryptographers and infosec researchers, there should be no problem using the word "secret". Otherwise, reductio ad absurdum, Following the same line of logic, all cryptography is "security through obscurity" because there exists a secret key, which is not incorrect. The practice of hiding the design of a system is obscurity, the practice of hiding a specific key to a ciphertext is security, not obscurity, as long as the method of generating and using it is publicly available. If there's nothing to reverse engineer, there can be no obscurity. The method of finding a symmetric key or finding a RSA key is well-known, not obscured, it's simply the size of the problem is not computationally tractable in practice by today's computers. [0] https://scholar.google.com/scholar?q=secret+key https://scholar.google.com/scholar?q=secret+key

lkbm 6y ago

Looking at the recent history: 2020-11-27 All exponents below 99 million tested at least once. 2020-11-17 All exponents below 98 million tested at least once. 2020-11-17 All exponents below 97 million tested at least once. 2020-11-09 All exponents below 96 million tested at least once. 2020-11-03 All exponents below 95 million tested at least once. 2020-10-24 All exponents below 94 million tested at least once. 2020-10-09 All exponents below 93 million tested at least once. 2020-10-04 All exponents below 92 million tested at least once. 2020-06-20 All exponents below 91 million tested at least once. 2020-04-09 All exponents below 90 million tested at least once. 2020-03-01 All exponents below 89 million tested at least once. What happened in June/July that caused it to stop, and in October to make it suddenly restart? Did they just switch from sequential to a grouping that checked all but a small portion of each million undone until November? September 17, 2020 All tests below 53 million verified. Makes me think part of it is them spending extra time verifying old tests. Just curious 1. if that's all it is and 2. why / whether this was triggered by something. Was there a bug found that raised doubt in previous tests? EDIT: Formatting

barkingcat 6y ago
I'm only tangencially related to the project, but I do have a spare machine running the software. Yes, there was a big push to re-verify old abandoned tests. First, understand that the project requires multiple tests results from each exponent - I believe it needs a triplicate confirmation (ie 3 different computers have to run the same test and all have to match) At some point, they developed a new, different algorithm that can do the check in one go (but it's more expensive computationally). However, most of the pre-existing work was done using the type of calculation that needed the triplicate check. There were a lot of exponents where some computer claimed one of the "verification tests" (ie it was already rejected as a prime, but we needed 2 more computers to verify), but then stopped mid way (it's pretty common since these primality tests take about 3-5 days on a modern fast threadripper - so it could take up to a month on slower machines from years ago). It's very unlikely that these exponents signified primes (since they were already verified to NOT be prime by 1 computer, and it's just the rechecks that are pending) These abandoned exponents formed a huge amount of "leftovers" that people didn't want as work units because they are most likely not prime, and if you were hunting for primes, these are not the work you want to do. So at some point, the project said they wanted a big push into picking up abandoned re-verifications and giving them a much higher priority to computers that could complete the test in a few days [either by finishing off what was left of the triplicate check, or by using the new algorithm that just needed one pass] - thus getting them out of the queue once and for all for good. If you have a fast computer (ie modern day i9, threadripper, xeon, anything with AVX512, etc) chances are you were assigned this type of rechecking task unless you rejected the work units. It's not just the gap you noticed in June, this whole project of looking for and verifying old exponents has been ongoing for the bulk of 2020. Another idea is that the project is always trying out new number techniques and algorithms and always looking for new instruction sets to use etc - a change or tweek in algorithm could cause this kind of "pause" as well, the client computers don't make the shift all at once (there's likely some verification, where a small subset of clients run both algorithms in parallel to see if the results are the same, etc) and then machines are moved onto the new algorithm as verifications are complete, etc. EDIT: As I wrote this post, I started remembering more about the different algorithms the projects used. All of the text above can be check with the prime95 forums, where they discuss these algorithm changes, the push to re-verify, etc.