A New Factoring Algorithm
A new approach to factoring
Lofa Polir is an unknown–until now–undergraduate working for a strong advisor. I do not yet have her picture, nor am I allowed to say any more about her or her advisor. They have sent me a rough draft of her new paper. Her result is nothing less than a new approach to factoring. If correct, it will break factoring based crypto-system in random polynomial time. Amazing. I have been able to get through some of the paper, and at least half seems fine. The last part uses a non-trivial amount of computer calculation plus some deep number theory, and will take a while to check. At this point I say the chances are definitely non-zero that this will all work.
The key definition is the following:
Definition: Call an integer matrix a -special matrix provided the following are true:
- The matrix is invertible modulo ;
- The matrix is not symmetric modulo ;
- The matrix is symmetric modulo ;
- The matrix satisfies and ;
- Finally, divides and divides . (Note, it is important, that these condition are not the same.)
She then claims the following two theorems:
Theorem 1: Suppose that where and are primes. Suppose also that is a -special matrix. Then, there is an algorithm that can factor given only and , and it runs in time .
Theorem 2: Suppose that where and are primes. Also assume that divides and divides . There is a random algorithm that given , and produces a matrix in time . Moreover, with probability at least the matrix is a -special matrix.
The second theorem relies on the Generalized Riemann Hypothesis. Clearly, together these theorems yield an attack on based crypto-systems. The attack goes like this. Pick a and “hope” that divides and . If that is true, then generate matrices and hope that they are -special. If they are, then you can factor . If they are not try another matrix. Note, even if was the only value that worked, then this would break many instances, since and are usually randomly selected.
The first theorem is fairly simple, and I will supply her proof in detail. The second, “proof” is much harder and I have not yet worked through it.
Proof of Theorem 1
Suppose that is a -special matrix for . The algorithm is incrediblely simple. Compute the following:
- Compute ;
- Then, compute the gcd’s of and for all .
She claims that this will factor . More precisely, that one of the greatest common divisor (gcd) calculations will yield a factor of . Clearly, the algorithm runs in the time required; the key question is solely one of correctness.
The key is to look at and also . Let’s look at . By definition this is equal to . By the definition of special, is equal to . Again by the definition of special, divides . Then, is equal to
and so is equal to a symmetric matrix modulo . Note, while the product of symmetric matrices are not always symmetric, they are if they commute. Since powers of any matrix commute with each other, equals a symmetric matrix modulo .
What happens to ? The trick is that it is not a symmetric matrix. We see why in a moment. But, for now assume that was true. Then, there must be so that entries at and are different. Then, by the Chinese Remainder Theorem will be divisible by but not by . This shows that the algorithm factors .
Thus, the key question is why is not a symmetric matrix modulo . As before is equal to . But again by the definition of special, for some . Then, is equal to
Thus, is where again is symmetric. Since was assumed to not be symmetric the following simple lemma finishes the argument.
Lemma 4 Suppose that and are square matrices of the same dimension. Suppose that they commute and that and are both symmetric. Also suppose that is invertible. Then, is also symmetric.
Proof: The transpose of a matrix is denoted by . Recall that by a standard fact about transpose, for any matrices and . Now,
The last uses that is symmetric. Now since is symmetric it also follows that
The last step uses that and commute. Thus, it follows that . Finally, is invertible so that .
“Proof” of Theorem 2
This is the part of her paper that I least understand. She needs to construct a -special matrix given only and and . She only shows any details for the special case and . As state earlier, even this restricted case, would break many instances of systems that use randomly generated and .
Her approach to theorem 2 is to write down the formal equations that define the properties of being a special matrix. The main ones that she has to worry about are that must not be symmetric and yet is symmetric modulo . The Fermat conditions: the matrix satisfies and are handled by an indirect argument.
The formal system is a set of equations in unknowns and equations. One equation is used to force the matrix not to be symmetric and equations are used to make the power symmetric. These are, of course, non-linear equations modulo . In general such equations are equivalent to factoring. However, there is special structure in her equations that she exploits.
After some Gröbner basis argument she reduces the solvability of these equations to the solvability of one high degree equation in two unknowns modulo . Then, she uses a Pollard-Schnorr type descent argument to prove that with high probability this equation has a solution.
The problem with checking this is first the Gröbner basis step involves a fair amount of equation manipulation, which needs to be checked carefully. Also the descent argument is a clever variation of the famous one due to John Pollard and Claus Schnorr and seems plausible, but again must be carefully checked.
The obvious open problem is: does her proof work? A potentially exciting time. I will get back soon with more details.