<story><title>Mathematicians Seal Loophole to Breaking RSA Encryption</title><url>https://www.quantamagazine.org/mathematicians-seal-back-door-to-breaking-rsa-encryption-20181217/</url></story><parent_chain></parent_chain><comment><author>wbhart</author><text>The title and the article are severely misleading. One can easily try the method described in the article and find that empirically, it doesn&amp;#x27;t work for large numbers. That implies that no one is seriously taking such a naive approach. You don&amp;#x27;t need a mathematical proof either way to know this.&lt;p&gt;But even so, the paper doesn&amp;#x27;t show that all polynomials are irreducible. It doesn&amp;#x27;t even show most are, just ones of a very special form (with 0 and 1 coefficients, randomly chosen in a certain way). Therefore, the paper doesn&amp;#x27;t rule out other kinds of polynomials, even if this were a serious approach.&lt;p&gt;Furthermore, even if the paper showed that all kinds of polynomials were almost always irreducible, that wouldn&amp;#x27;t rule out the existence of a very clever algorithm for writing the integers as values of polynomials that aren&amp;#x27;t irreducible.&lt;p&gt;Consider the following analogy: there are exceedingly many possible prime factors of 6000 digit numbers; far too many to practically test them all one after the other. I can produce a mathematical proof that shows that I&amp;#x27;ll never test primality of a 6000 digit number by trying all possible prime factors in order. But that doesn&amp;#x27;t prevent the existence of algorithms that can quite quickly tell you whether the number is prime or composite (such algorithms actually exist). Just because something looks hard or it can be proven that some naive approach is computationally infeasible, doesn&amp;#x27;t mean there isn&amp;#x27;t a very clever algorithm that makes it easy.&lt;p&gt;The authors of the actual math paper really asked for any unwanted attention they get from this news article, though. They actually give the integer factorisation problem as a motivation in their paper!</text></comment>
<story><title>Mathematicians Seal Loophole to Breaking RSA Encryption</title><url>https://www.quantamagazine.org/mathematicians-seal-back-door-to-breaking-rsa-encryption-20181217/</url></story><parent_chain></parent_chain><comment><author>segfaultbuserr</author><text>This is the actual paper.&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;arxiv.org&amp;#x2F;abs&amp;#x2F;1810.13360&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;arxiv.org&amp;#x2F;abs&amp;#x2F;1810.13360&lt;/a&gt;&lt;p&gt;It&amp;#x27;s worth noticing that Riemann Hypothesis is assumed in the proof, as I layman, I think it means the proof merely gives us more &lt;i&gt;confidence&lt;/i&gt; about the difficulty of integer factorization. But integer factorization itself still remains an open question.&lt;p&gt;&amp;gt; &lt;i&gt;Abstract. We consider random polynomials with independent identically distributed coefficients with a fixed law. Assuming the Riemann hypothesis for Dedekind zeta functions, we prove that such polynomials are irreducible and their Galois groups contain the alternating group with high probability as the degree goes to infinity. This settles a conjecture of Odlyzko and Poonen conditionally on RH for Dedekind zeta functions.&lt;/i&gt;&lt;p&gt;Page 2, &lt;i&gt;Section 1.1, Motivation&lt;/i&gt; has a summary.&lt;p&gt;&amp;gt; &lt;i&gt;Beyond its intrinsic interest, the problem of irreducibility of random polynomials of high degree is motivated by some other problems, which we now briefly discuss. It is believed to be computationally difficult to determine the prime factorization of integers. On the other hand, polynomial time algorithms are known for computing the factorization of polynomials in Z[x]. Given an integer N ∈ Z_{&amp;gt;0}, we can write it as N=P(2) for a unique polynomial P with 0,1-coefficients. By computing the factorization of P in Z[x] and evaluating the factors at 2, we can obtain a factorization of N.&lt;/i&gt;&lt;p&gt;&amp;gt; &lt;i&gt;The only weakness of this approach is that the polynomial P may be irreducible and thus the factorization of N obtained may be trivial. The problem we study in this paper thus asks for the probability that this procedure returns only a trivial factorization. Therefore, it is desirable to have results, such as those of this paper, proving that this probability converges to 1 very fast. We will discuss our method in Section 1.3. The method links the problem of irreducibility of random polynomials with mixing times of certain Markov chains, which are &amp;quot;mod p&amp;quot; analogues of the Bernoulli convolutions we had studied in earlier work.&lt;/i&gt;&lt;p&gt;&amp;gt; &lt;i&gt;In this paper, we use results available for the Markov chains to study random polynomials, but this can be reversed. In particular, in a forthcoming paper, we will use the results of this paper to obtain new results about the Markov chains. Our results on irreducibility assume the Riemann hypothesis for Dedekind zeta functions, or at least some information on the zeros. In our last theorem, Theorem 7, we show that conversely irreducibility of random polynomials has (modest) implications about the zeros of Dedekind zeta functions.&lt;/i&gt;</text></comment>