Assuming that the results of this research paper are correct, it provides faster methods for determining whether a number is prime, for counting how many prime numbers exist in an interval and for finding all prime numbers within an interval.
This could accelerate the algorithms that depend on finding prime numbers, e.g. breaking by brute force RSA signatures or encryption.
I did not fully verify the whole paper, but I feel pretty skeptical about usefullness of this for the small numbers. All of their formula provide a linear speed-up vs naive approach, which means that the big-O complexity is not going to be changing.
So the best thing that this paper can do for determining if a number is a prime is to speed it up by some small constant factor (at most 210)... That's less than 8 bits of 2000+ bits that is currently used in RSA signatures, so basically noise.
Reading the article, many false claims can be spotted: 1) This idea is not new, the same periodicity was found previously. 2) Their idea is the extension of the well known fact any prime is either of the form 6n+1 or 6n -1 with n a Natural number. In this case, the second primorial 6 = 2x3 is used. They use the 4th primorial 210 = 2x3x5x7. The problem with these "predictive" way to recognize primes is the fact that quite soon false positive start to emerge. For example, in the case of 6 the first false positive is 25 = 6x4 +1. In fact, it is very easy to know to which extent is the scheme valid; to the square of the first predicted square, in case of 6, it is 5, therefore 25 is the limit. In their case, their system will predict 11, but it will start to fail as early as 121. Even they recognize that for "large" primes they need to incorporate 11 in the scheme, but such a new method will also start to fail at the deceptively small 169. 3) Therefore, this paper is no breakthrough as the primes are infinite, they method can't predict all primes, and they even fail to recognize the limits of their method. In the paper mentioned before, these facts are all treated and an extended symmetry among the prime numbers found.
*The Prime Numbers Hidden Symmetric Structure and its Relation to the Twin Prime Infinitude and an Improved Prime Number Theorem; https://cds.cern.ch/record/1000658?ln=es
The main claim of the manuscript is essentially that primes correspond to the numbers whose residue modulo 2x3x5x7=210 is relatively prime to the modulus, i.e., not divisible by 2, 3, 5, or 7. Two issues with this:
(1) This is false. For example: every power of 211=2x3x5x7+1 is coprime with 210, and certainly every power of 211 above the first is not prime.
(2) Even if one gives them credit and say they only claim a negative result, i.e., a number >7 that is not coprime to 210 is not prime, it is completely trivial.
The manuscript does not contain any original idea of substance but does contain numerous false claims, the irresponsibility shown by various news sites in parroting this manuscript is astounding. This would never pass a peer review by any legitimate mathematician.
While I agree that there are great chances that their proofs contain some mistakes, what you say is completely erroneous.
Their primality test is considerably more complex than what you say. Those numbers with coprime residues are just candidates for being primes and there are additional conditions that become more complex to compute for larger and larger numbers.
There is absolutely no implication from what they say that a power of 211 could be prime.
Their theorem:
"An integer a in [11,b] containing no factors of 2, 3, 5, and 7 is a prime if and only if there exists r_i coprime with 210 and a non-negative integer k so that a = r_i + 210 × k with k+1 not in L_b[i]"
"i" is in [1,48] and it is an index into an array with the 48 numbers coprime with 210 in the interval [11,211].
"L_b" is a table that must be computed from b with an algorithm given in the paper.
I have not analyzed their proofs, so they may be wrong, or perhaps the computation of the L_b table is not actually faster than the sieving methods currently used, but everything written by you is not applicable to the paper.
I was surprised they didn't discuss why there were 48 prime candidates co-prime to 2, 3, 5, 7 below 210; and 8 co-prime to 2, 3, 5 below 30; and 480 below 2310. I've been calling it the larial for years, but it's the primorial minus 1 at each step, i.e. (2-1)×(3-1)×(5-1)×(7-1) = 48. Or the fact that there will always be 1 number coprime to n (and lower primes) that is non-coprime to n+1 in the first n columns for every row on the table, which is where the Larial comes from.
I discovered this stuff independently nearly a decade ago and didn't share because it didn't seem novel to anyone I discussed it with. And I have dated Google drive documents and Gmail emails to prove it. But I suspect it isn't worth proving.
12 comments
[ 3.5 ms ] story [ 28.3 ms ] threadThis could accelerate the algorithms that depend on finding prime numbers, e.g. breaking by brute force RSA signatures or encryption.
So the best thing that this paper can do for determining if a number is a prime is to speed it up by some small constant factor (at most 210)... That's less than 8 bits of 2000+ bits that is currently used in RSA signatures, so basically noise.
There may be some error in their proofs, but it is not a prank, though that was my first thought too.
(1) This is false. For example: every power of 211=2x3x5x7+1 is coprime with 210, and certainly every power of 211 above the first is not prime.
(2) Even if one gives them credit and say they only claim a negative result, i.e., a number >7 that is not coprime to 210 is not prime, it is completely trivial.
The manuscript does not contain any original idea of substance but does contain numerous false claims, the irresponsibility shown by various news sites in parroting this manuscript is astounding. This would never pass a peer review by any legitimate mathematician.
Their primality test is considerably more complex than what you say. Those numbers with coprime residues are just candidates for being primes and there are additional conditions that become more complex to compute for larger and larger numbers.
There is absolutely no implication from what they say that a power of 211 could be prime.
Their theorem: "An integer a in [11,b] containing no factors of 2, 3, 5, and 7 is a prime if and only if there exists r_i coprime with 210 and a non-negative integer k so that a = r_i + 210 × k with k+1 not in L_b[i]"
"i" is in [1,48] and it is an index into an array with the 48 numbers coprime with 210 in the interval [11,211].
"L_b" is a table that must be computed from b with an algorithm given in the paper.
I have not analyzed their proofs, so they may be wrong, or perhaps the computation of the L_b table is not actually faster than the sieving methods currently used, but everything written by you is not applicable to the paper.
I discovered this stuff independently nearly a decade ago and didn't share because it didn't seem novel to anyone I discussed it with. And I have dated Google drive documents and Gmail emails to prove it. But I suspect it isn't worth proving.
This math does make pretty music though: https://on.soundcloud.com/juyxv