Contrary to what just about every mathematician on Earth will tell you, prime numbers can be predicted, according to researchers at City University of Hong Kong (CityUHK) and North Carolina State University, U.S.
Contrary to what just about every mathematician on Earth will tell you, prime numbers can be predicted, according to researchers at City University of Hong Kong (CityUHK) and North Carolina State University, U.S.
The research team comprises Han-Lin Li, Shu-Cherng Fang, and Way Kuo. Fang is the Walter Clark Chair Professor of Industrial and Systems Engineering at North Carolina State University. Kuo is a Senior Fellow at the Hong Kong Institute for Advanced Study, CityU.
This is a genuinely revolutionary development in prime number theory, says Way Kuo, who is working on the project alongside researchers from the U.S. The team leader is Han-Lin Li, a Visiting Professor in the Department of Computer Science at CityUHK.
We have known for millennia that an infinite number of prime numbers, i.e., 2, 3, 5, 7, 11, etc., can be divided by themselves and the number 1 only. But until now, we have not been able to predict where the next prime will pop up in a sequence of numbers. In fact, mathematicians have generally agreed that prime numbers are like weeds: they seem just to shoot out randomly.
"But our team has devised a way to predict accurately and swiftly when prime numbers will appear," adds Kuo.
The technical aspects of the research are daunting for all but a handful of mathematicians worldwide. In a nutshell, the outcome of the team's research is a handy periodic table of primes, or the PTP, pointing the locations of prime numbers. The research is available as a working paper in the SSRN Electronic Journal.
[...] More to the point, the PTP has major applications today in areas such as cyber security. Primes are already a fundamental part of encryption and cryptography, so this breakthrough means data can be made much more secure if we can predict prime numbers, Kuo explains.
This advance in prime number research stemmed from working on systems reliability design and a color coding system that uses prime numbers to enable efficient encoding and more effective color compression. During their research, the team discovered that their calculations could be used to predict prime numbers.
More information: Han-Lin Li et al, The Periodic Table of Primes, SSRN Electronic Journal (2024). DOI: 10.2139/ssrn.4742238
(Score: 4, Insightful) by Tork on Friday April 05, @08:14PM (13 children)
🏳️🌈 Proud Ally 🏳️🌈
(Score: 3, Interesting) by sneftel on Friday April 05, @08:30PM
No. Prime numbers are useful in cryptography, but only because they possess certain useful properties, not because their primality is a secret. The question of whether a number is prime was once expected to be quite difficult to compute, but for the last couple of decades it’s been known that it’s only *kind of* hard.
(Score: 4, Interesting) by hazelnut on Friday April 05, @08:40PM (5 children)
I am somewhat cryptographically inclined, although it's been a while. If correct, this would fundamentally weaken or outright break some public key cryptography. Particularly RSA encryption. It relies on the fact that finding prime numbers is very difficult. Although it probably wouldn't affect the likes of elliptic curve. I don't believe it would have a significant effect on AES.
If I'm wrong, someone please correct me. It's been a while.
(Score: 3, Interesting) by Tork on Friday April 05, @08:49PM
🏳️🌈 Proud Ally 🏳️🌈
(Score: 5, Informative) by vux984 on Friday April 05, @11:20PM (3 children)
"It relies on the fact that finding prime numbers is very difficult."
No, It relies on the fact that factoring composite numbers to their prime factors is very difficult. Being able to find prime numbers easier potentially would speed up brute forcing the factorization up, but I'm not sure how much, really.
If you've got a 2048 bit number that you need to factor, that's two 1024 bit factors; (1024 digit binary numbers, or ~308 decimal digits each).
At that part of the integer space primes appear at about the rate of 1/ln(10^308) ==~ 0.0014. That is, roughly 0.14% of numbers with 308 digits are prime. Seems like we've just dramatically reduced our search space for factors if we could pick out all the primes to brute force test them against our composite, right? RSA is broken! but not really; we've reduced the search space from 10^308 possible factors to 10^305 possible prime factors. I mean... yes, its smaller, a lot smaller. But still not small. You've still got 10^305 primes to search, and that's still more than the number of atoms in the observable universe.
And not just a little bit more... like if every atom in the observable universe were itself a whole universe of atoms, and every single atom in each of those universes were themselves another whole universe -- than the count of all the atoms in all the universe of universes of universes would still be trillions upon trillions upon trillions of times smaller a number than the 10^305 primes we'd have to look at with 1024 binary digits. (The RSA standard doesn't actually require the two primes in a 2048 bit scheme be exactly 1024 bits either although some implementations are since there's no shortage of primes to choose from even at exactly that size.)
(Score: 1) by shrewdsheep on Saturday April 06, @11:01AM (1 child)
But the race is on. Note, that for 308 digits for the composite, only 154 digits would have to be checked for primes (square root). 3 digits off of that would be 2% efficiency gain. As we move to higher digits, that gain becomes more favorable. Also recall that not all composites are eligible. The primes must not be too small. I would say that writings for RSA are on the wall as there are additional problems (quantum factorization). I still use RSA for ssh at the moment but I consider switching to eliptic curve cryptography in my next iteration of ssh key updates.
(Score: 2) by vux984 on Monday April 08, @02:14AM
"But the race is on. Note, that for 308 digits for the composite, only 154 digits would have to be checked for primes (square root)."
No. 2048-bits is 616 decimal digits. I'd already taken the square root to get to 308, and then done the math based on 3 digits off that which is 305.
"Also recall that not all composites are eligible. The primes must not be too small."
Again, the set of 305 digit numbers already are ONLY the candiate primes. And they're all 305 digits long... so ... not too small :)
(Score: 1, Insightful) by Anonymous Coward on Sunday April 07, @01:46AM
This is not quite accurate. If you could efficiently factor large composite numbers (specifically, an N-bit number which is the product of two (N/2)-bit primes), then you can efficiently break RSA as you can simply repeat the original private key derivation. However, the reverse is not known to be true. There may be an efficient way to break RSA which does not imply an efficient solution for the problem of factoring integers.
RSA's security specifically depends on the following problem being hard (aptly named the "RSA Problem"):
In the congruence C ≡ Pe (mod N), with N semiprime, solve for P given C, e and N.
Note that "find the two prime factors of N" is not part of the problem statement. In other words, it is possible that there is an efficient solution to the RSA problem (which would represent a total break of RSA) while at the same time there being no efficient solution to the problem of factoring N.
(Score: 5, Informative) by pTamok on Friday April 05, @09:05PM (2 children)
AFAIK, it doesn't help much.
Cryptography depends on factoring composite numbers composed of large primes being difficult.
There already exist very good methods for primality testing [wikipedia.org]: that is to say, for any given number, we have a test that says with a high degree of certainty whether a number is prime or not. The certainty is not 100%.
But for the size of composite numbers cryptography deals with, it isn't possible to 'simply' generate a list of prime numbers up to the square-root of the number and check each individually to see if it is a factor. The list of primes is simply too big. RSA encryption uses keys of (typically) 2048 bits, which describes the product of two primes. This means that the primes are (roughly) 1024 bits in length. 21024 is roughly 10709. We can use the prime number theorem [wikipedia.org] to give a good estimate of how less likely it is that a number is prime the larger it is.
Using Wolfram Alpha, the number of primes less than 21024 [wolframalpha.com] is roughly 2.5x10305, and the number of primes less than 21000 is roughly 1.5x10298 [wolframalpha.com], giving the number of primes in the range 21000 to 2 1024 to be a smidgeon less than 2.5x10305.
If you test a billion billion billion billion (1036) primes per second, it would take 10269 seconds to check them all. The Universe is roughly 4.4x1017 seconds old.
So being able to generate some, or all primes quickly by fast mathematical means does not help (much) in breaking cryptography based on factorisation of large primes.
(Happy to be corrected if I am wrong)
(Score: 4, Informative) by pTamok on Friday April 05, @09:08PM
That last sentence should read:
So being able to generate some, or all primes quickly by fast mathematical means does not help (much) in breaking cryptography based on factorisation of large composite numbers that are the product of two (roughly) equal sized primes.
(Score: 5, Funny) by acid andy on Friday April 05, @10:31PM
Security through obscurity then!
If a cat has kittens, does a rat have rittens, a bat bittens and a mat mittens?
(Score: 2) by krishnoid on Friday April 05, @09:39PM (1 child)
Maybe I don't understand the math, but the logic would seem to indicate that:
So I'd suspect that predictability of primes wouldn't factor [sic] into their usability in cryptography.
(Score: 2) by bzipitidoo on Saturday April 06, @07:29PM
Even being able to look up primes or factorizations in a table would not help with the enormous quantities represented with 300 digit numbers. There is so incredibly much info to store that the storage device would have to be bigger than the observable universe. Not much good being able to look up info when that info could be billions of light years away.
(Score: 2) by driverless on Saturday April 06, @07:54AM
It's something that could only have been produced by the PR department of a university. A breakthrough implies significant progress in solving some important problem, like finding a cure for stupidity. In this case the "breakthrough" is a solution to a problem no-one has and, apart from some mathematicians, no-one really cares about.
(Score: 3, Insightful) by HiThere on Friday April 05, @08:26PM (1 child)
There are only so many prime numbers with fewer than n digits, so if you can predict where they will be, you don't need to check the other numbers. This would seem, to me, to make it easier to crack encryption of a given length.
Javascript is what you use to allow unknown third parties to run software you have no idea about on your computer.
(Score: 3, Informative) by pTamok on Friday April 05, @09:31PM
You are right, but if my calculations above are correct, then even if you have a list of all the prime numbers up to the RSA key-size of 2048 bits, you are still looking at 10200 times the lifetime of the Universe to check them as being one of the two factors of the two large primes that are multiplied together to generate the composite number that is the RSA key. Even if I'm wrong, and in fact it is only 10100 times, or 1050 times the lifetime of the Universe, I'm not overly worried.
Big numbers are big.
Given we are looking at something like 1x10300 numbers that need to be stored in their exact binary form, each number will need anything up to (say) 1024 bits, which is 128 bytes to store. Handwave some efficient compression (which is funny, as we are dealing with primes), then say on average each number is stored in 8 bits, you'll still need 1x10300 bytes of memory simply to store them. An zettabyte of memory is 1021 bytes, which is very approximately the amount of data transferred across the Internet in a year. So simply to store the list of primes, you need 10279 times the memory required to store the amount of data transferred across the Internet in a year. This is not currently practical.
So, yes, with a list of large primes, you can take the time to multiply them together to get an RSA key and see if it is the correct key to decrypt something. It'll take a while.
(Score: 5, Interesting) by Ken_g6 on Friday April 05, @10:16PM (4 children)
What they're describing appears to be a wheel sieve [t5k.org], known since ancient times.
(Score: 4, Informative) by janrinok on Friday April 05, @10:26PM (2 children)
I considered that, but the scientific paper was published in January of this year - and appears to exist and be genuine. Furthermore, the source material (phys.org) is dated 3rd or 4th of April (it is just turned midnight here so "two days ago" is a little bit vague).
(Score: 1) by khallow on Saturday April 06, @10:22AM (1 child)
(Score: 2) by kazzie on Sunday April 07, @04:30AM
But adding complexity is good for an encryption algorithm, isn't it? :)
(Score: 3, Interesting) by Mojibake Tengu on Friday April 05, @11:48PM
This method is technically realizable in analog domain, as a machine built from fixed oscillators which produces numbers as hints for followed digital check. An idea about 100 years old now.
Respect Authorities. Know your social status. Woke responsibly.
(Score: 3, Insightful) by Zoot on Saturday April 06, @02:40AM (7 children)
So, do we have any comments on this from uninvolved mathematicians? In articles like this, usually the writer will seek comments on the claims from at least one well-known mathematics person. This article just has:
"This is a genuinely revolutionary development in prime number theory, says Way Kuo, who is working on the project[...]"
which is hardly convincing.
Maybe this is something really neat, but the linked article reads exactly like bad science reporting would.
(Score: 4, Interesting) by Zoot on Saturday April 06, @02:45AM
Oh, it looks like the ENTIRE article was provided by one of the institutions involved in the research.
From my experience, the WORST source of information about some new "discovery" is the press office at the university where the announcement was made, as these are always breathlessly expansive about the potential applications, glory and profit for the university, etc. and are seemingly never written by anyone who understands the technicalities involved.
Proceeding to forget about this for now...
(Score: 2) by zocalo on Saturday April 06, @10:32AM
While there does seem to be something a bit more profound waiting to be found concerning primes and their distribution, without some independent corrorboration and more evidence as to what they've supposedly found I'm highly skepetical this is it. Great claims require great evidence, after all.
UNIX? They're not even circumcised! Savages!
(Score: 4, Funny) by stratified cake on Saturday April 06, @10:37AM
If this really is a breakthrough that allows them to predict prime numbers, maybe they should, like, I don't know, do it?
(Score: 4, Interesting) by Thexalon on Saturday April 06, @02:15PM (2 children)
Grandiose claim? Check.
Formerly obscure researchers? Check.
Lack of external verification? Check.
You know, I thought I'd come up with something pretty revolutionary at one point. I wrote it up, showed it to somebody who knew more than me ... who promptly used it to point out that my idea had made 1=0. Oops.
I wish that one day, science reporting would wait for all the cooler heads in the field to read the paper and make damn sure the proof actually is there before saying "Look! They solved everything!! Give them a major award immediately!!!" But science journalism, like most journalism, preferences being fast and wrong over being slow and right.
The only thing that stops a bad guy with a compiler is a good guy with a compiler.
(Score: 0) by Anonymous Coward on Monday April 08, @01:39PM
Internet rando who thinks he know more: Check.
(Score: 0) by Anonymous Coward on Monday April 08, @01:42PM
Wow, you really have no idea how science works, do you? Also, one can easily "prove" 1=0 with calculus. OOPS.
(Score: 5, Interesting) by Ken_g6 on Saturday April 06, @09:24PM
Most of the prime number people hang out on mersenneforum.org. They're mostly laughing at this. [mersenneforum.org] But I don't know how many are real mathematicians. If R. D. Silverman weighs in, it's all over, but he hasn't yet. I like this quote, though: