54
$\begingroup$

Quanta Magazine reports:

Two mathematicians have uncovered a simple, previously unnoticed property of prime numbers [...]. Prime numbers, it seems, have decided preferences about the final digits of the primes that immediately follow them.

Among the first billion prime numbers, for instance, a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9.

Do these insights make breaking keys based on primes more mathematically plausible in a shorter amount of time?

|improve this question
$\endgroup$

migrated from security.stackexchange.com Mar 15 '16 at 21:55

This question came from our site for information security professionals.

  • 7
    $\begingroup$ Is this a duplicate of this: mathoverflow.net/questions/233633/… ? $\endgroup$ – childofsoong Mar 14 '16 at 23:09
  • $\begingroup$ @childofsoong duplicates only happen inside same-site. It is perfectly OK to ask similar questions on different SE sites, so long the asker clearly states the focus on the site's expertise. Even if the question is not a security question, it would be a candidate for close or migrate, not duplicate. $\endgroup$ – Mindwin Mar 15 '16 at 15:36
  • $\begingroup$ @Mindwin good to know - I'm going to leave the comment up, though, because anyone wanting to read up on this would probably find that one useful, as well. $\endgroup$ – childofsoong Mar 15 '16 at 16:31
  • $\begingroup$ The phenomenon is IMHO reminiscent of Benford's Law in another context. $\endgroup$ – Mok-Kong Shen Mar 17 '16 at 14:40
42
$\begingroup$

No, because these new insights only affect the discovery and patterns regarding finding new prime numbers. In order to break existing encryption algorithms that rely on primes such as RSA, you'd have to have a breakthrough in discovering how to factor integers into primes.

Primes are used in encryption keys as the basis of their generation: two large primes are multiplied together to form a very large number. The difficulty of factoring this large number to discover its prime roots is essentially the protection the cryptosystem offers. Since you already have the primes (the private key, essentially), you need not factor the number and can immediately decrypt it.

Since the new discovery only relates to patterns prime numbers take which may assist a search for even larger prime numbers than already known, and not in factoring multiples of prime numbers, this discovery should be inconsequential for cryptography.

|improve this answer
$\endgroup$
21
$\begingroup$

No, because that "discovery" produces nothing of value.

They examined prime numbers up to one billion. In that range, about one in eight numbers ending in 1, 3, 7 or 9 are prime numbers, and which ones are primes is quite unpredictable.

Now if a prime p ends in a digit 9, then the numbers p + 2, p + 4, p + 8, p + 10, p + 12 etc. each have about a one in 8 chance to be primes (p + 6, p + 16 etc. cannot be primes because they end in a five).

However, p + 2 has a one-in-eight chance of being the next prime. p + 4 has a chance of (7/8) * 1/8 of being the next prime, because it cannot be the next prime if p + 2 is prime. p + 8 has a chance of (7/8)^2 * 1/8 of being the next prime, because it cannot be the next prime if p + 2 or p + 4 is, and so on.

So their claim may very well be true, but it is a really trivial and obvious result and of no consequence whatsoever. They also published it 16 days too early.

Take a deck of cards and shuffle it properly. Take the first card, then find the next card of the same color. It is most likely that the second card is the first card of the same color, less likely that the third one is the first card of the same color, and so on.

Now throw a coin, then throw another coin repeatedly until that coin comes with the same face up. 50% chance that it happens at the first throw, 25% chance that it happens at the second throw, 12.5% that it happens on the third throw, etc.

(Now what I said about the primes is not quite precise, because there is an obvious relation between consecutive numbers possible being prime. If p is prime, then p is not divisible by 3, which makes p + 6 also not divisible by 3 and therefore more likely to be prime, while p + 2 and p + 4 have a higher chance than a random number to be divisible by 3, and therefore less likely to be primes. Similar for divisibility by 7; if p is prime then p + 14, p + 28, p + 42 are all not divisible by 7 and therefore slightly more likely to be primes, while the other numbers are not. But that is also long known

And this bit should calm down those who figured that the article went beyond what things would like for random numbers. You can look it all up if you search for "Hardy, Littlewood", and correlations between primality of nearby numbers were known in detail in the mid of the 20th century).

PS. You absolutely, absolutely don't use nearby primes for RSA for example, because a product pq of two primes can be trivially factored if the difference between p and q is not large compared to the square root of p or q.

|improve this answer
$\endgroup$
  • 15
    $\begingroup$ In response to the accepted answer (I don't have reputation to comment or downvote) – the article linked to in the question specifically states that the 'explanation' you give does not explain the results that they found. > But the pair of mathematicians soon realized that this potential explanation couldn’t account for the magnitude of the biases they found. $\endgroup$ – aPaulT Mar 15 '16 at 11:02
  • 14
    $\begingroup$ 'No, because that "discovery" is absolute rubbish.' It should not be relevant to information security, but to call it absolute rubbish seems more indicative of a lack of knowledge on your side than anything else. Did you have a look at the actual paper or on what exactly did you base your evaluation? It seems on a snippet from from a pop-science article. (For one detail among many things, the one billion is an illustrative example not the full data as is even explained in the pop-science article.) $\endgroup$ – quid Mar 15 '16 at 11:09
  • 7
    $\begingroup$ @NewWorld Mainly, I asked on what OP even based their evaluation, rather than to contradict anything. Another comment (in the form of an answer) points quite succinctly to a problem with this answer. It does not seem to understand what the point of the paper it trashes even is but it seems just based on a snippet from a pop-science description of it, not even the full pop-science article. (If I find time I will write up an answer to explain what the paper is actually about.) $\endgroup$ – quid Mar 15 '16 at 11:36
  • 20
    $\begingroup$ @NewWorld aPaulT had made the case, why repeat it? But okay: "Lemke Oliver and Soundararajan’s first guess for why this bias occurs was a simple one: Maybe a prime ending in 3, say, is more likely to be followed by a prime ending in 7, 9 or 1 merely because it encounters numbers with those endings before it reaches another number ending in 3. [...] But the pair of mathematicians soon realized that this potential explanation couldn’t account for the magnitude of the biases they found. " This answer just doesn't even address the reported discovery. And even pop-sci version makes this clear. $\endgroup$ – quid Mar 15 '16 at 13:05
  • 14
    $\begingroup$ To sum it up: it is written that the explanation offered in this answer that supposedly shows why 'the "discovery" is absolute rubbish' was considered by the authors and was in fact not able to explain the data contrary to what this answer implies. This is the discovery. Either OP should explain why it still does, rather than to merely repeat this attempt at explaining it as if it were news, or retract their claims. The "discovery" they talk about is just not the discovery in question. @NewWorld $\endgroup$ – quid Mar 15 '16 at 13:13
6
$\begingroup$

Not really - the frequency of primes doesn't change, and it's not a certainty that any given prime isn't followed by another with the same final digit. You'd still have to check all possible primes in the appropriate range, but you could slightly optimise the order of checks. However, given the number of digits in primes used in key based ciphers, there are a lot of potential numbers to look at.

It's a slight improvement, but not enough of one to break the algorithms.

However, it could lead to renewed mathematical interest in large primes, which might produce some more "useful" results in terms of predicting primes.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.