# Could this unexpected bias in the distribution of consecutive primes have any impact on the security of encryption algorithms?

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?

-
I am not really an expert in encryption; still I have never heard of algorithms that would depend on pairs of consecutive primes. – Mikhail Bondarko Mar 14 at 17:42
Hard to see how. – Lucia Mar 14 at 17:43
@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. – vonjd Mar 14 at 17:58
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. – David Speyer Mar 14 at 21:38
@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. – user9072 Mar 15 at 19:19

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 – kodlu Mar 16 at 4:49