> 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.
I'm absolutely dumbfounded (and awestruck) that there are people who dedicate this much compute power to solving these tasks.
EDIT: reading a wiki page, this sounds like recreational mathematics, not actual research math, which is a shame really
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).
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.
I'll have to read up on the certification/verification process to comment any further though.
See https://en.wikipedia.org/wiki/Certificate_%28complexity%29 if you're interested in learning more.
You could probably design a supercomputer specifically for prime searches, but it would be a weird one.
GPU __shared__ memory is 64kB. A 1024-wide workgroup would be able to store 4096 bytes per register, if the whole workgroup was just working on one number. So ~6 registers x 1024 shader workgroup to store the full 20kB number.
__shared__ memory would allow for very quick shader-to-shader communications.
I think... it can work. But its difficult for me to visualize the full program. Its going to be complex, but probably doable. Its also not really a design pattern that a lot of GPU code (ex: Thrust) works in very well, you'd have to use harder to use libraries like CUB instead.
That's why GIMPS is the way it is: with volunteers offering computers that are separated and do a siloed calculation.
But the fact that this was done on a Threadripper 3990x, a high-core count (but slow interconnect / core-to-core communication) kind of computer, makes me believe that there's a degree of parallelism in this problem.
Otherwise, another computer (ie: higher GHz / less core count) could have been used instead.
---------
I really don't know this specific algorithm: ECPP. It comes down to how that works... especially its parallelization.
I'm guessing there just isn't a good CUDA implementation out there.
[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.
What sort of AI are you referring to? A deep neural network? Why should this be better than our current techniques?
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%).
def is prime(n):
return False
The issue is without 100% certainty, there's not really any use for a "this is very likely probably prime" checker.
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 (citing 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 .
Your comment therefore comes across as very ill-informed, and your doubling down doesn't help.
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).
Primes have lots of order and patterns, so references to chaos and "no such order exists" aren't really relevant.
As to "why" - this is recreational mathematics. It's because people find it fun or engaging. And it isn't special - recreational mathematics covers far more than just primes. There's a lot of people who love calculating digits of pi, as one clear example.
Right... that's what I meant about irrational numbers. I'm not trying to rain on the parade of the hobby of it all, but if there were an actual pattern, primes would not be useful in cryptography. The hobby of trying to find "the pattern" is Sunday morning armchair alchemy. Nothing wrong with it, and maybe there's a pattern to be found one day. Great. Whether there is or isn't is only relevant given that we don't know what that pattern is yet. It doesn't, as some imagine, imply the existence of a higher order intelligence.
0.1234567891011121314151617181920212223...
Yet it has so much structure that you can easily figure out what any digit 'n' will be.
> The hobby of trying to find "the pattern" is
I have no idea what you are talking about with "the pattern".
> if there were an actual pattern, primes would not be useful in cryptography
Why do you think there are no patterns and that all of the following people are wrong?
* "Patterns in prime numbers" - https://mathsreach.org/Patterns_in_prime_numbers
* "Patterns in the Primes" - https://www.maa.org/meetings/calendar-events/patterns-in-the...
* "Math Mornings at Yale: The Patterns in the Primes, with Andrew Granville" - https://www.youtube.com/watch?v=pO7Egc5Dtqs
* "New Pattern Found in Prime Numbers" - https://phys.org/news/2009-05-pattern-prime.html
* '"Patterns in the Primes" by Stephanie Hanson - Week 5 - MathSoc Public Lecture' - https://www.youtube.com/watch?v=VkbPhjU-S9Q
Note that none of these refer to a definite "the pattern."
Primes are useful in the RSA cryptosystem because modulo exponentiation is cheap while in general factoring the product of two large prime numbers is far less tractable - as far as we know.
There are so many patterns in primes that cryptosystems have been broken by choosing the initial primes poorly. See https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_... .