Factoring Numbers Using Polynomials

Consider a number such as \(45\) and suppose we have no idea how to factor it. Let's convert \(45_{10}\) to its binary equivalent \(101101_2\). From this binary number, let's form a polynomial using the indices of the placeholder values \(2^5, 2^4, 2^3, 2^2, 2^1, 2^0\) as the indices of an associated polynomial, namely \(x^5 + x^3 + x^2 + 1\). This polynomial factorises as follows:$$

x^2(x^2+1)+1(x^2+1) = (x^2+1)(x^3+1) = (x+1)(x^2-x+1)(x^2+1)

$$If we now substitute \(x=2\), the result is 3 * 3 * 5 which are the prime factors of 45. Let's try another number, this time \(111\) that is \(1101111_2\) in binary form. The associated polynomial is \(x^6+x^5+x^3+x^2+x+1\) that factorises to the following:$$

x^5(x+1)+x^2(x+1)+1(x+1) = (x+1)(x^5+x^2+1)

$$Substituting \(x=2\) gives 3 * 37, the prime factors of \(111\).

The useful idea behind such a technique is that it can be applied to factor very large composite numbers. I came across the idea in a Quanta Magazine article titled: Mathematicians Seal Back Door to Breaking RSA Encryption. The article states:

This seems like a complicated way to find the prime factors of a small number like 15, whose factors are easy to spot straightaway. But with very large numbers — numbers with hundreds of digits — this polynomial method gives you a remarkable advantage. There’s no fast algorithm for factoring large numbers. But there are fast algorithms for factoring large polynomials. So once you convert your large number to a large polynomial, you’re very close to finding the number’s prime factors.

Does this mean RSA encryption is in trouble? Actually, no. The reason for this has to do with the new proof about polynomials. The mathematicians Emmanuel Breuillard and Péter Varjú of the University of Cambridge proved that as polynomials with only 0 and 1 as coefficients get longer, they’re less and less likely to be factorable at all. And if a polynomial can’t be factored, it can’t be used to identify the prime factors of the number it’s based on. 

Breuillard and Varjú’s proof effectively slams shut the polynomial back door for breaking RSA encryption. The very large numbers used in RSA encryption correspond to very long polynomials. Breuillard and Varjú proved that it’s nearly impossible to find polynomials of that length that can be factored. Mathematicians and cryptographers alike have long suspected this is the case. But when the cybersecurity of the entire world depends on some mathematical hack not working, it’s good to have proof that it doesn’t. 

Regardless of RSA encryption, the key point for me was the fact that every number can be represented as a unique polynomial. For example:

45 -->  \(x^5 + x^3 + x^2 + 1\) and 111 --> \(x^6+x^5+x^3+x^2+x+1\)

All such polynomials have coefficients that are either 0 or 1. This makes the factorisation, if possible, fairly straightforward as can be seen in examples chosen. Of course, a unique polynomial can be created in any base. In base 3:

45 --> \(x^3+2x^2=x^2(x+2)\) and 111 --> \(x^4+x^3+x=x \,(x^3+x^2+1)\)

Substituting \(x=3\) into the above factorised expressions gives the factorisation as before. However, in some bases, the polynomials do not factorise. For example, in base 5:

45 --> \(x^2+4x=x \, (x+4) \) but 111 --> \(4x^2+2x+1\) which doesn't factorise.