Previous post show the idea. The problem is that one need to find polynomials of high degree to get the number of coefficients equal to the number of monomials. Too many monomials have to be killed. Here is another way to hunt. Shor’s algorithm uses Fourier transform , and fast integer multiplication also uses discrete Fourier Transform. Let’s try it here. It is going to be only sketch here, it is neither pretended to be correct nor complete.
We have our binary represented “could be factors”
Following the fast multiplication recipe we are going to pad out binary representations with zeros, e.g. now
Now we want to apply Discrete Fourier Transform to our factors, e.g. ()
We need to keep the constraints.
The linear combinations of constraints are still constraints, so we can make another Fourier transform for the constraints. Since it is non-singular transformation we are not loosing any constraint.
Which means that each of K constraints has a single term of the first order, and exactly terms of second order. In total it contains all quadratic terms distributed across constraints such that .
Now the product is also containing linear in K number of terms because we need to take point-wise products of the transformed x
Now we are ready to construct certificate. Let say of degree 4. Moreover, we want to restrict the terms in the certificate to not exceed 2 in any variable. Therefore, we have the following components.
terms of the form – giving coefficients.
terms of the form – giving coefficients. Both of this conditions give
terms representing quadratic constraints for unknown x bits:
terms representing quadratic constraints for unknown y bits:
On the other hand there are only monomials in the certificate. Therefore, there is enough coefficients, if they are linearly independent (which have to be shown) to test feasibility of factoring.
If we would be lucky to show this linear independence, and that this linear independence holds for all not factorable n, we would have polynomial algorithm for factorization, since the degree of the certificate can be bounded by 4, independent of n.