Mathematicians have proven polynomials will not help crack RSA

Quanta recently published a story in which the author talked about a phenomenon that was surprising from the point of view of inexperienced readers and proved by mathematicians. Its essence is that almost all polynomials of a certain type are irreducible, that is, they cannot be decomposed. This proof is applied in many areas of pure mathematics. But it is also good news for one of the pillars of modern life - digital encryption.

Encryption using the RSA algorithm is widely used to securely store digital information. This is a pumped-up version of the scheme, which even a seventh grader can come up with to exchange messages with friends: each letter is assigned its own number, which is multiplied by some secret key, previously agreed upon. To decrypt a message, simply divide it into a secret key.

RSA encryption works in a similar way. We give a strongly simplified explanation. The user creates a message and performs certain mathematical operations on it, including multiplication by a very large number (several hundred digits long). The only way to decrypt the message is to find the prime factors of the result *.

The security of RSA encryption is based on the fact that fast ways to find prime factors of very large numbers are unknown to mathematics. And if the encrypted message was not meant for you, and you do not have a key to decrypt it, then attempts to find this key can take a good thousand years. And this is true for the most modern computers, with the help of which it is still impossible to find the correct prime factors.

But there is a workaround. Each number can be represented as a unique algebraic equation. And, in contrast to the search for simple factors of a number, the search for simple factors of a polynomial is much easier. And as soon as the polynomial will be decomposed into such prime factors, this information can be used to search for prime factors of the original number.

Here is how it works.

Step One: Choose any number whose prime factors you need to know. For simplicity, take the number 15.

Step two: 15 is transferred to the binary system:

1111.

Step Three: This binary expression becomes a polynomial by converting all binary numbers to the coefficients of a polynomial:



(Note: this polynomial is equal to 15 if x = 2. The number 2 is the base of the binary system.)

Step Four: The polynomial factorizes:



Step five: x = 2 is substituted into each of these factors:



Conclusion: 5 and 3 are prime factors of the number 15.

Yes, this is an unnecessarily complicated way of searching for simple factors of a small number, like 15, which can be easily calculated in the mind. However, when it comes to large numbers consisting of hundreds of digits, this polynomial method provides an amazing advantage. There is no fast algorithm for decomposing primes. But for the decomposition of large polynomials there are such algorithms. Therefore, as soon as you manage to turn a large number into a large polynomial, you can get very close to finding the prime factors of a number.

Does this mean that RSA encryption is at risk? Not really. And the new, recently proved regularity about polynomials is connected with this.

Mathematicians Emmanuel Brulya and Peter Warew of the University of Cambridge proved that as the polynomials with coefficients 0 and 1 are lengthened, the probability that they can be expanded completely becomes lower and lower. And if the polynomial cannot be expanded, it means that it cannot be used to find prime factors of the number to be calculated.

The proof of Brulya and Warju actually suggests that a workaround for breaking RSA encryption leads to nowhere. The very large numbers used in RSA correspond to very long polynomials. Cambridge scientists argue that it is almost impossible to find polynomials of that length that can be decomposed. Both cryptographers and mathematicians have long suspected that this is so. However, when global cybersecurity depends on the impossibility of using some mathematical technique, it is always good to have proof that this technique does not really work.