Factoring idea

jstevh@msn.com · science forum Guru Joined: 21 Jan 2006 Posts: 951

After years of effort with lots of failures I noticed something
remarkably simple, and this time the math is all worked out, and there
are few places for errors to hide.

Was doodling, playing around with some simple equations and noticed
that with

x^2 - a^2 = S + T

and

x^2 - b^2 = S - k*T

I could subtract the second from the first to get

b^2 - a^2 = (k+1)*T

which is, of course, a factorization of (k+1)*T:

(b - a)*(b+a) = (k+1)*T

with integers for S and T, where T is the target composite to factor,
so you have to pick this other integer S, and factor S+T.

Really simple.

But how do you find all the variables?

Well, if you pick S, and have a T you want to factor, then using

f_1*f_2 = S+T

it must be true that

a = (f_1 - f_2)/2

And

x=(f_1 + f_2)/2

so, you need the sum of factors of (S-k*T)/4 to equal the sum of the
factors of (S+T)/4, so I introduce j, where

S - k*T = (f_1 + f_2 - j)*j

and now you solve for k, to get

k = (S - (f_1 + f_2 - j)*j)/T

so you also have

S - (f_1 + f_2 - j)*j = 0 mod T

so

j^2 - (f_1 + f_2)*j + S = 0 mod T

and completing the square gives

j^2 - (f_1 + f_2)*j + (f_1 + f_2)^2/4 = ((f_1 + f_2)^2/4 - S) mod T

so

(2*j - (f_1 + f_2))^2 = ((f_1 + f_2)^2 - 4*S) mod T

so you have the quadratic residue of ((f_1 + f_2)^2 - 4*S) modulo T, to
find j, which is kind of neat, while it's also set what the quadratic
residue is, so there's no search involved.

The main residue is a trivial result that gives k=-1, but you have an
infinity of others found by adding or subtracting T.

And then you can find b, from

b^2 = x^2 - S + kT

and you have the factorization:

(b-a)*(b+a) = (k-1)*T.

It is possible to generalize further using

j = z/y

and then the congruence equation becomes

(2*z - (f_1 + f_2)y)^2 = ((f_1 + f_2)^2*y^2 - 4*S*y^2) mod T.

If you're skeptical you may consider the question of finding k when you
already have the factorization of T.

James Harris

jstevh@msn.com · science forum Guru Joined: 21 Jan 2006 Posts: 951

jstevh@msn.com wrote:

Ben Young · science forum beginner Joined: 15 Jun 2006 Posts: 9

you are not a mathematician, nor could you tell one were it right in front of you

Frederick Williams · science forum addict Joined: 19 Nov 2005 Posts: 97

jstevh@msn.com wrote:

Jeremy Watts · science forum Guru Wannabe Joined: 24 Mar 2005 Posts: 239

"Ben Young" <djfray@gmail.com> wrote in message
news:17646181.1152193874282.JavaMail.jakarta@nitrogen.mathforum.org...

Google