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.

### Like this:

Like Loading...

*Related*

This is the best idea about integer factorization, written here is to let more people know and participate.

A New Way of the integer factorization

1+2+3+4+……+k=Ny,(k<N/2),"k" and "y" are unknown integer,"N" is known Large integer.

True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).

How do I know "k" and "y"?

"P" is a factor of "N",GCD(k,N)=P.

Two Special Presentation:

N=5287

1+2+3+…k=Ny

Using the dichotomy

1+2+3+…k=Nrm

"r" are parameter(1;1.25;1.5;1.75;2;2.25;2.5;2.75;3;3.25;3.5;3.75)

"m" is Square

(K^2+k)/(2*4)=5287*1.75 k=271.5629(Error)

(K^2+k)/(2*16)=5287*1.75 k=543.6252(Error)

(K^2+k)/(2*64)=5287*1.75 k=1087.7500(Error)

(K^2+k)/(2*256)=5287*1.75 k=2176(OK)

K=2176,y=448

GCD(2176,5287)=17

5287=17*311

N=13717421

1+2+3+…+k=13717421y

K=4689099,y=801450

GCD(4689099,13717421)=3803

13717421=3803*3607

The idea may be a more simple way faster than Fermat's factorization method(x^2-N=y^2)!

True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).

More details of the process in my G+ and BLOG.