# Integer Factorization Algorithm

1. Apr 14, 2008

### 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.

Visu

#### Attached Files:

• ###### Prime_Factoring_Algorithm_Updated_Ver1_1_2.pdf
File size:
80.8 KB
Views:
115
2. Jun 16, 2008

### math_x4

3. Jun 17, 2008

### CRGreathouse

On the bottom of the first page, you write:

1/2(d6)x2 + (d4-(1/2d6))x + d1 = y2

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?

4. Jun 17, 2008

### visu

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.

Last edited: Jun 17, 2008
5. Jun 17, 2008

### 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...

6. Jun 17, 2008

### visu

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.

7. Jun 18, 2008

### CRGreathouse

Not a problem. I'll note that $1/2\cdot d_6=1$ since d6 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}$$

Last edited: Jun 18, 2008
8. Jun 18, 2008

### visu

$$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$$.

9. Jun 19, 2008

### 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$$

Last edited: Jun 19, 2008
10. Jun 19, 2008

### 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.