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?

Improve this question
$\endgroup$
10
  • 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
    Commented Mar 14, 2016 at 17:42
  • 8
    $\begingroup$ Hard to see how. $\endgroup$
    – Lucia
    Commented Mar 14, 2016 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
    Commented Mar 14, 2016 at 17:58
  • 5
    $\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
    Commented Mar 14, 2016 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
    Commented Mar 15, 2016 at 19:19

2 Answers 2

Reset to default
21
$\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.

Improve this answer
$\endgroup$
1
  • 2
    $\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
    Commented Mar 16, 2016 at 4:49
4
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .