5 ms·

> The certification took 20 months on an AMD 3990x computer (64 cores); and verification took about 13 hours. I'm absolutely dumbfounded (and awestruck) that t

> The certification took 20 months on an AMD 3990x computer (64 cores); and verification took about 13 hours. I'm absolutely dumbfounded (and awestruck) that there are people who dedicate this much compute power to solving these tasks.

noduerme 4y ago
I'm equally dumbfounded that with all this computing power no one has written an AI that can identify primes 99.999% of the time for quicker testing. Train that thing and reverse its logic. I'm not one of those people who think primes are the keys to the universe. I'm not sure how one day people realized there's no pattern, just a form of embedded randomness, behind any irrational number like Pi... yet still think the prime sequence is more important than that. [edit] it's as if we're so desperate for order to arise out of chaos that we'll bend reality to find the order in any sequence. Seems like our own problem, not God's. [edit2] I am eagerly awaiting any response to know why this is such an unpopular comment! I'm excited to have my mind changed. Tell me.
- pushedx 4y ago
  Prime numbers are the basis of most practical cryptosystems (including ones which you used to make your comment), and other applications of number theory, and are the heart of number theory itself.
- l33t233372 4y ago
  I believe this is an unpopular comment because “training an AI to identify primes” is pretty much technobabble. What sort of AI are you referring to? A deep neural network? Why should this be better than our current techniques?
  - noduerme 4y ago
    Really? It's not techno babble. Encode the first few thousand primes in QR codes and pictures of ducks, throw 2000 GPUs at it and see how long it takes to train a model to pick them out of the other similarly encoded integers. Tune for success rate with the next few thousand primes. Even if it's only right 20% of the time you've vastly increased the efficiency of finding new prime numbers.
    - tiagod 4y ago
      You're making a lot of generic guesses and assumptions. Do you really think nobody has ever thought of this?
- calebrob6 4y ago
  I'm not sure this is an application where using AI makes sense. For example, there are a large number of algorithmic ways to determine if a number of probably prime -- https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...
- jxf 4y ago
  > I am eagerly awaiting any response to know why this is such an unpopular comment! I'm excited to have my mind changed. Tell me. I suspect it's because "an artificial intelligence that can identify primes for quicker testing" is a phrase that would probably be recognized by experienced developers in this space as a bad idea. There are already very good ways to identify prime candidates; no artificial intelligence is needed. They just take a while because even though they're very efficient, it takes a long time to operate on staggeringly huge numbers. For a more relatable example, you can build an artificial intelligence that understands what you mean when you type "2 + 2". But this is a fantastically inefficient and expensive way to compute the value "4". Therefore, no one does this in a serious way. Even GPT-3, one of the more advanced commercially available models with hundreds of millions of parameters, struggles with multiplying two-digit numbers together (one study found a success rate of 20%).
  - noduerme 4y ago
    How do you know you can't train a large image model to lean toward preferring large embedded primes?
- squeaky-clean 4y ago
  If we consider prime numbers above 1000 digits def is prime(n): return False Would be 99.99% accurate. The issue is without 100% certainty, there's not really any use for a "this is very likely probably prime" checker.
  - noduerme 4y ago
    over a few million digits if you were trying for the Guinness book, wouldn't it be handy to have something that narrowed it down?
    - tiagod 4y ago
      The time you spent writing this you could've googled mersenne primes and how candidates are selected. You would've found out there are loads of techniques to narrow them down, and that we're looking for specific types of primes as the first step in this. Then you would've avoided coming off as a dunning-kruger know-it-all...
- eesmith 4y ago
  Why unpopular? You wrote "can identify primes 99.999% of the time for quicker testing", which shows several fundamental and basic flaws in your understanding. We've had approximate primarily testing methods for a long time and they are quite effective. See https://primes.utm.edu/notes/prp_prob.html https://primes.utm.edu/notes/prp_prob.html (citing https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-198... ), for a 100,000-digit number the odds of Fermat's test for compositeness being a false is 1.3E-10584, which is 99.9999999999999{insert 560 nines here}999999999%. This is why, in the AMS paper cited as [1] in this link, Dubner wrote "it is virtually certain that R49081 is prime." The full context is: > In September 1999, it was discovered that R49081 is a probable prime. This was verified on several different computers with different software. Although it is virtually certain that R49081 is prime, it is necessary to prove rigorously that it is prime. A 99.999%-likely test is far less virtually certain than the test used, and in any case doesn't achieve the goal of rigorously proving it's prime. Even worse, these standard primality testing methods have a 0% false negative rate, while your hypothetical AI might miss actual repunits even with a 0.000001% rate. > just a form of embedded randomness, behind any irrational number like Pi This doesn't makes sense. There are irrational numbers with no randomness, like Liouville's constant and the Champernowne constant. And there are plenty of patterns in primes - the Ulam spiral Wikipedia entry even compares the clearly apparent structure of that spiral to a random distribution, at https://en.wikipedia.org/wiki/Ulam_spiral https://en.wikipedia.org/wiki/Ulam_spiral . Your comment therefore comes across as very ill-informed, and your doubling down doesn't help.
  - noduerme 4y ago
    It wasn't my contention that an AI could identify every single prime on the number line or that it could prove whether a number was prime. I was saying that an AI could increase the efficiency in finding candidates for testing. I'm not going to triple down and say I know God exists or doesn't, I just made the observation that humans find order in chaos where no such order exists. A lot of algorithms generate the appearance of a pattern while having no real pattern and I don't see why primes are special. (practical usefulness of proof in crypto aside, which could also be done less elegantly with any set of irrational numbers calculated to a sufficiently difficult number of digits).
incompatible 4y ago
Certification is the creation of a proof that the number is prime (consisting of some related numbers), while the verification checks that the certification is correct?
- saghm 4y ago
  I was thinking that "certification" referred to ensuring that the program they wrote to test it was correct, and then verifying was running it, but your interpretation makes sense too
- segfaultbuserr 4y ago
  Yes. In particular, "certification" refers to the fact that the proof is computationally difficult to create, but once it's created, it's easy for a third-party to check its correctness (insert your P/NP reference here). https://en.wikipedia.org/wiki/Primality_certificate https://en.wikipedia.org/wiki/Primality_certificate
noobermin 4y ago
I'm more surprised, assuming their algorithm is somewhat parallelizable, that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months. EDIT: reading a wiki page, this sounds like recreational mathematics, not actual research math, which is a shame really
- dspillett 4y ago
  > that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months I am assuming that is how the result was verified much faster - >1,000x the computer power used. Without looking deeper (like actually reading the article!) I couldn't say way that would be in this particular case, but such a disparity between power used to make a finding and power used to verify it by repetition is often the case when the initial result is discovered by a recreational researcher or small group, not a better funded group. Not unlike the human scaling seen when one individual or a small group publishes a proof that could be significant, and many others poor over it to see if they can find a flaw before it is generally accepted as a genuine new finding (an order of magnitude or more of human brains to check, than to initially find).
  - cedilla 4y ago
    The results aren't verfied by running the same calculations again. Rather, there's a verification method used along with some information from the original solution - that's the certificate they mention. Imagine factoring a non-prime number. It would take you quite long to factor 695587 with nothing but a cheap calculator, but you could very quickly verify my factorization if I give you the information that it is divisible by 71 and 101.
    - dspillett 4y ago
      Though the factor-checking like verification won't work for “this number is prime” the same as it will for “this number is not prime”. A test that results in saying a number is prime doesn't output any factors to test because if such existed the number would not be prime. I'll have to read up on the certification/verification process to comment any further though.

noduerme 4y ago

I'm equally dumbfounded that with all this computing power no one has written an AI that can identify primes 99.999% of the time for quicker testing. Train that thing and reverse its logic. I'm not one of those people who think primes are the keys to the universe. I'm not sure how one day people realized there's no pattern, just a form of embedded randomness, behind any irrational number like Pi... yet still think the prime sequence is more important than that. [edit] it's as if we're so desperate for order to arise out of chaos that we'll bend reality to find the order in any sequence. Seems like our own problem, not God's. [edit2] I am eagerly awaiting any response to know why this is such an unpopular comment! I'm excited to have my mind changed. Tell me.

pushedx 4y ago
Prime numbers are the basis of most practical cryptosystems (including ones which you used to make your comment), and other applications of number theory, and are the heart of number theory itself.
l33t233372 4y ago
I believe this is an unpopular comment because “training an AI to identify primes” is pretty much technobabble. What sort of AI are you referring to? A deep neural network? Why should this be better than our current techniques?
- noduerme 4y ago
  Really? It's not techno babble. Encode the first few thousand primes in QR codes and pictures of ducks, throw 2000 GPUs at it and see how long it takes to train a model to pick them out of the other similarly encoded integers. Tune for success rate with the next few thousand primes. Even if it's only right 20% of the time you've vastly increased the efficiency of finding new prime numbers.
  - tiagod 4y ago
    You're making a lot of generic guesses and assumptions. Do you really think nobody has ever thought of this?
calebrob6 4y ago
I'm not sure this is an application where using AI makes sense. For example, there are a large number of algorithmic ways to determine if a number of probably prime -- https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...
jxf 4y ago
> I am eagerly awaiting any response to know why this is such an unpopular comment! I'm excited to have my mind changed. Tell me. I suspect it's because "an artificial intelligence that can identify primes for quicker testing" is a phrase that would probably be recognized by experienced developers in this space as a bad idea. There are already very good ways to identify prime candidates; no artificial intelligence is needed. They just take a while because even though they're very efficient, it takes a long time to operate on staggeringly huge numbers. For a more relatable example, you can build an artificial intelligence that understands what you mean when you type "2 + 2". But this is a fantastically inefficient and expensive way to compute the value "4". Therefore, no one does this in a serious way. Even GPT-3, one of the more advanced commercially available models with hundreds of millions of parameters, struggles with multiplying two-digit numbers together (one study found a success rate of 20%).
- noduerme 4y ago
  How do you know you can't train a large image model to lean toward preferring large embedded primes?
squeaky-clean 4y ago
If we consider prime numbers above 1000 digits def is prime(n): return False Would be 99.99% accurate. The issue is without 100% certainty, there's not really any use for a "this is very likely probably prime" checker.
- noduerme 4y ago
  over a few million digits if you were trying for the Guinness book, wouldn't it be handy to have something that narrowed it down?
  - tiagod 4y ago
    The time you spent writing this you could've googled mersenne primes and how candidates are selected. You would've found out there are loads of techniques to narrow them down, and that we're looking for specific types of primes as the first step in this. Then you would've avoided coming off as a dunning-kruger know-it-all...
eesmith 4y ago
Why unpopular? You wrote "can identify primes 99.999% of the time for quicker testing", which shows several fundamental and basic flaws in your understanding. We've had approximate primarily testing methods for a long time and they are quite effective. See https://primes.utm.edu/notes/prp_prob.html https://primes.utm.edu/notes/prp_prob.html (citing https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-198... ), for a 100,000-digit number the odds of Fermat's test for compositeness being a false is 1.3E-10584, which is 99.9999999999999{insert 560 nines here}999999999%. This is why, in the AMS paper cited as [1] in this link, Dubner wrote "it is virtually certain that R49081 is prime." The full context is: > In September 1999, it was discovered that R49081 is a probable prime. This was verified on several different computers with different software. Although it is virtually certain that R49081 is prime, it is necessary to prove rigorously that it is prime. A 99.999%-likely test is far less virtually certain than the test used, and in any case doesn't achieve the goal of rigorously proving it's prime. Even worse, these standard primality testing methods have a 0% false negative rate, while your hypothetical AI might miss actual repunits even with a 0.000001% rate. > just a form of embedded randomness, behind any irrational number like Pi This doesn't makes sense. There are irrational numbers with no randomness, like Liouville's constant and the Champernowne constant. And there are plenty of patterns in primes - the Ulam spiral Wikipedia entry even compares the clearly apparent structure of that spiral to a random distribution, at https://en.wikipedia.org/wiki/Ulam_spiral https://en.wikipedia.org/wiki/Ulam_spiral . Your comment therefore comes across as very ill-informed, and your doubling down doesn't help.
- noduerme 4y ago
  It wasn't my contention that an AI could identify every single prime on the number line or that it could prove whether a number was prime. I was saying that an AI could increase the efficiency in finding candidates for testing. I'm not going to triple down and say I know God exists or doesn't, I just made the observation that humans find order in chaos where no such order exists. A lot of algorithms generate the appearance of a pattern while having no real pattern and I don't see why primes are special. (practical usefulness of proof in crypto aside, which could also be done less elegantly with any set of irrational numbers calculated to a sufficiently difficult number of digits).

incompatible 4y ago

Certification is the creation of a proof that the number is prime (consisting of some related numbers), while the verification checks that the certification is correct?

saghm 4y ago
I was thinking that "certification" referred to ensuring that the program they wrote to test it was correct, and then verifying was running it, but your interpretation makes sense too
segfaultbuserr 4y ago
Yes. In particular, "certification" refers to the fact that the proof is computationally difficult to create, but once it's created, it's easy for a third-party to check its correctness (insert your P/NP reference here). https://en.wikipedia.org/wiki/Primality_certificate https://en.wikipedia.org/wiki/Primality_certificate

noobermin 4y ago

I'm more surprised, assuming their algorithm is somewhat parallelizable, that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months. EDIT: reading a wiki page, this sounds like recreational mathematics, not actual research math, which is a shame really

dspillett 4y ago
> that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months I am assuming that is how the result was verified much faster - >1,000x the computer power used. Without looking deeper (like actually reading the article!) I couldn't say way that would be in this particular case, but such a disparity between power used to make a finding and power used to verify it by repetition is often the case when the initial result is discovered by a recreational researcher or small group, not a better funded group. Not unlike the human scaling seen when one individual or a small group publishes a proof that could be significant, and many others poor over it to see if they can find a flaw before it is generally accepted as a genuine new finding (an order of magnitude or more of human brains to check, than to initially find).
- cedilla 4y ago
  The results aren't verfied by running the same calculations again. Rather, there's a verification method used along with some information from the original solution - that's the certificate they mention. Imagine factoring a non-prime number. It would take you quite long to factor 695587 with nothing but a cheap calculator, but you could very quickly verify my factorization if I give you the information that it is divisible by 71 and 101.
  - dspillett 4y ago
    Though the factor-checking like verification won't work for “this number is prime” the same as it will for “this number is not prime”. A test that results in saying a number is prime doesn't output any factors to test because if such existed the number would not be prime. I'll have to read up on the certification/verification process to comment any further though.