16
$\begingroup$

In a recent paper a quite unexpected result about a new pattern in prime numbers emerged:

Unexpected biases in the distribution of consecutive primes
by Oliver, R. J. L.; Soundararajan, K. (Submitted on 11 Mar 2016)

While the sequence of primes is very well distributed in the reduced residue classes (mod $q$), the distribution of pairs of consecutive primes among the permissible $ϕ(q)^2$ pairs of reduced residue classes (mod $q$) is surprisingly erratic. This paper proposes a conjectural explanation for this phenomenon, based on the Hardy-Littlewood conjectures. The conjectures are then compared to numerical data, and the observed fit is very good.

My question
Could this result have any impact on the security of encryption algorithms which are based on prime numbers?

$\endgroup$
  • 4
    $\begingroup$ I am not really an expert in encryption; still I have never heard of algorithms that would depend on pairs of consecutive primes. $\endgroup$ – Mikhail Bondarko Mar 14 '16 at 17:42
  • 8
    $\begingroup$ Hard to see how. $\endgroup$ – Lucia Mar 14 '16 at 17:43
  • 2
    $\begingroup$ @Lucia: My experience tells me that most (if not all) patterns can be exploited - sometimes in the most unexpected ways... I think this one needs careful consideration. $\endgroup$ – vonjd Mar 14 '16 at 17:58
  • 4
    $\begingroup$ If there are any algorithms out there which use consecutive primes, they have a bigger problem. If $x = p_k p_{k+1}$, then $x-p_k$ is usually $\approx (1/2) \log p_k \approx (1/4) \log x$. So we can factor $x$ by trying $\log x$ divisors near $\sqrt{x}$, a polynomial algorithm. $\endgroup$ – David E Speyer Mar 14 '16 at 21:38
  • 2
    $\begingroup$ @PaulBaker the user saying this on Information Security quite clearly had not even read the pop-science description of the result. I would not assign overly much weight to this, except maybe as a warning of the dangers of half-knowledge and for other sociological reasons. $\endgroup$ – user9072 Mar 15 '16 at 19:19
19
$\begingroup$

This discovery is beautiful, but it's unlikely to have any impact on cryptography. Of course this lack of relevance is a matter of speculation/opinion, not proven mathematical fact, but these sorts of correlations between consecutive primes just haven't come up in cryptography to my knowledge, because there seems to be no value in using extremely close primes in any cryptosystem. It's basically orthogonal to what cryptographers care about. Of course it's always worth learning more about the primes, and it's hard to predict where it might lead in the future, but this paper raises no special cause for concern in cryptography.

$\endgroup$
  • 1
    $\begingroup$ If anything use of nearby primes is discouraged, since an efficient attack would consist of trying to solve $p(p+2)=n,$ say, where $n=p_i p_j$ is the RSA modulus. And random choice would give you primes of a given bitlength, which means they are typically apart by $2^{n-2}$ if your bitlength is $n$ and they're chosen independently at random en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation $\endgroup$ – kodlu Mar 16 '16 at 4:49
3
$\begingroup$

There's another discussion of the bias on math.SE. The phenomenon is not limited to consecutive primes, but its repulsion effect seems to be attenuated (or masked by noise) too quickly to have powerful consequences. Oliver and Soundararajan note there may be implications for semiprimes, which would be of cryptographic interest.

There are hints that the prime numbers are leaking information to nearby composites. It's conceivable that one might be able to factorize an arbitrary composite quickly by collecting enough information from the primes near it.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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