Integer Factorization Algorithm

[visu]

I am posting an integer factorization algorithm that I have developed. I am hoping for feedback on any obvious flaws that I might have missed before writing a computer programme to test it out.

Thanks in advance

Visu

 

[math_x4]

Looks interesting. You can benchmark it with number factoring tool.

 

[CRGreathouse]

On the bottom of the first page, you write:

1/2(d₆)x² + (d₄-(1/2d₆))x + d₁ = y²

Is this
$$\frac12d_6x^2+(d_4-\frac12d_6)x+d_1=y^2$$
or
$$\frac{1}{2d_6}x^2+\left(d_4-\frac{1}{2d_6}\right)x+d_1=y^2$$
or something else?

Also, where does this quadratic come from? Does x have some value (it isn't used before the equation) or is this simply a member of R[x]? *Why* do we want the left to be a square?

 

[visu]

On the bottom of the first page, you write:

1/2(d₆)x² + (d₄-(1/2d₆))x + d₁ = y²

Is this
$$\frac12d_6x^2+(d_4-\frac12d_6)x+d_1=y^2$$
or
$$\frac{1}{2d_6}x^2+\left(d_4-\frac{1}{2d_6}\right)x+d_1=y^2$$
or something else?

Also, where does this quadratic come from? Does x have some value (it isn't used before the equation) or is this simply a member of R[x]? *Why* do we want the left to be a square?

The first of the two equations you wrote.Apologies for not being clear.

x is an unknown and so is y.What I am doing is an extension of Fermat's factoring method.In Fermat's method, we express the number to be factorised as the difference of 2 squares.Let's say the number we want to factorise is N. So we want to find a^2 - N = b^2.
If "a" doesn't work we try a+1, a+2 and so on until we find (a+n)^2 - N = b^2,so we can factorise N by the difference of squares.

Now the LHS of the equation is already a quadratic equation, so in the next step, I am applying the calculus of finite difference http://mathworld.wolfram.com/FiniteDifference.html to obtain the another quadratic equation which is the one that you mention.
Actually this is the same as expanding out (a+n)^2-N=b^2 with n and b as the unknowns and replacing a and N with their known values.

Hopefully this should also explain you other question of why we want the LHS to be square.

 

[Kittel Knight]

Your "integer factorization algorithm" depends on the "generic two integer variable equation solver", which depends on prime factoring of integers,etc...:yuck:

Six of one, half-dozen of the other...

 

[visu]

Your "integer factorization algorithm" depends on the "generic two integer variable equation solver", which depends on prime factoring of integers,etc...:yuck:

Six of one, half-dozen of the other...

Actually it doesn't depend on the "generic two integer variable equation solver".I am actually aware that this is not very clear and am working on an improved draft.

I was just using the "generic two integer variable equation solver" to illustrate the point that any semiprime has only 2 sets of solutuons for the given quadratic equation.

 

[CRGreathouse]

The first of the two equations you wrote.Apologies for not being clear.

Not a problem. I'll note that $1/2\cdot d_6=1$ since d₆ is always 2, so the equation
$$\frac12d_6x^2+\left(d_4-\frac12d_6\right)x+d_1=y^2$$
simplifies to
$$x^2+(d_4-1)x+d_1=y^2$$
which has roots
$$2y=1-d_4\pm\sqrt{d_4^2-2d_4+1-4d_1}$$

 

[visu]

Not a problem. I'll note that $1/2\cdot d_6=1$ since d₆ is always 2, so the equation
$$\frac12d_6x^2+\left(d_4-\frac12d_6\right)x+d_1=y^2$$
simplifies to
$$x^2+(d_4-1)x+d_1=y^2$$
which has roots
$$2y=1-d_4\pm\sqrt{d_4^2-2d_4+1-4d_1}$$

$$2y=1-d_4\pm\sqrt{d_4^2-2d_4+1-4d_1}$$

Referring to this equation I think you mean 2x on the LHS which is the quadratic formula. You can't use the quadratic formula in this case because both x and y are unknown whereas in the case where you can use the quadratic formula only x is unknown. The equation I have given is a 2nd order Diophantine equation.In other words what you are doing is correct only if
$$x^2+(d_4-1)x+d_1=0$$.

 

[CRGreathouse]

Must have been confusing it with one of the other problems on the boards, sorry.

I found it useful when looking over this problem to define $\epsilon=\sqrt n-\lceil\sqrt n\rceil+1\in(0,1].$ Then many of the terms can drop out of the equations, and the magnitude of each term is more clear.

So
$$a_1=\sqrt n+\epsilon$$
$$k_1=2\epsilon\sqrt n+\epsilon^2$$
$$d_1=2(\epsilon+1)\sqrt n+(\epsilon+1)^2$$
$$d_2=2(\epsilon+2)\sqrt n+(\epsilon+2)^2$$
$$d_3=2(\epsilon+3)\sqrt n+(\epsilon+3)^2$$
$$d_4=\sqrt n+2\epsilon+3$$
$$d_5=\sqrt n+2\epsilon+5$$
$$d_6=2$$
$$y^2=x^2+(d_4-1)x+d_1=x^2+(\sqrt n+2\epsilon+2)x+d_1=x^2+(\sqrt n+2\epsilon+2)x+2(\epsilon+1)\sqrt n+(\epsilon+1)^2$$

 

[CRGreathouse]

You won't be able to find an analytical square in R[x, y], since if you could it would be of the form $$x^2+2\alpha x+\alpha^2$$ and you could equate coefficients:
$$\sqrt n+2\epsilon+2=2\alpha$$
$$2(\epsilon+1)\sqrt n+(\epsilon+1)^2=\alpha^2$$

$$4\alpha^2=8(\epsilon+1)\sqrt n+4(\epsilon+1)^2=n+(4\epsilon+4)\sqrt n+(2\epsilon+2)^2$$
$$8(\epsilon+1)\sqrt n=n+(4\epsilon+4)\sqrt n$$
$$(4\epsilon+4)\sqrt n=n$$
$$n=(4\epsilon+4)^2$$

Not that this really tells you anything.