Simple answer, surrogate factoring

jstevh_at_msn.com
Date: 03/04/05 

Date: 3 Mar 2005 17:18:44 -0800

The main issue for me in showing that surrogate factoring is practical
is in finding a perfect algorithm which will factor a target M for any
non-zero j coprime to M.

I think the answer is a simple one.

Starting as usual with

yx^2 + Ax - M^2 = 0

and

yz^2 + Az - j^2 = 0

where M is the target to be factored, j is some non-zero natural
usually chosen to be less than M, and

T = M^2 - j^2.

Then

y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2

and you can substitute out y to get

x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)

and

z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

where the square roots relate Ax to the factorization of T and j, and
Az is related to the factorization of T and M.

The problem has been that if you find the integer Ax values that follow
from that second expression, you may find that all the solutions for Ax
that are not coprime to M, have M itself as a factor.

So it helps to split A and x up, which is already done for you, as the
expression is actually a relationship between z and x, but z and x are
asymmetrical with regard to factors in common with M.

For instance, if x has p_1^2 as a factor where p_1 is a factor of M,
then z must have p_1 as a factor, but not p_1^2.

You can kind of see that with

y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2

but it's also easy to rigorously prove it.

So the full algorithm, which splits up A and x requires that you solve
for Ax, and if it has M as a factor, you go ahead and finish out

z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

by solving

(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

and canceling out common factors between the numerator and the
denominator.

And then for at least one case, it must be true that the denominator
has a single prime factor of M left to divide out from x so that z has
the proper factor of M.

The proof that Ax must for one case involve A having prime factors of M
and x having the others is all that remains.

Going back to

yx^2 + Ax - M^2 = 0

it is trivial to replace Ax using

Ax = M^2 - yx^2

in

z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

to get

z = x(-Ax +/- sqrt((M^2 - yx^2 - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

so if Ax has M as a factor then yx^2 must as well.

But y = (M^2 - Ax)/x^2, so if x has a single prime factor of M, then A
must as well for y to have that factor.

So, can x have a single prime factor of M?

Assume it can and call that factor g, so x = g^2.

Then

yg^4 + Ag^2 - M^2 = 0, so y = (M^2 - Ag^2)/g^4

and now substituting for y in

yz^2 + Az - j^2 = 0, after solving for z, gives

z = g^4(-A +/- sqrt(A^2 + 4j^2(M^2 - Ag^2)/g^4))/2(M^2 - Ag^2)

and the real issue is whether or not z can be rational in this case so
concentrating on the square root, I have

sqrt(A^2 g^4 + 4j^2 M^2 - 4j^2 g^2 A)

where collecting and completing the square gives

sqrt(g^4 A^2 - 4j^2 g^2 A + 4j^2 + 4j^2 M^2 - 4j^4 )

which is

sqrt((g^2 A - 2j)^2 + 4j^2 T)

so any A that makes that rational will work.

Notice that A may be a fraction with g^2 in the denominator, so let's
look back at

yg^4 + Ag^2 - M^2 = 0

and notice that all that matters is that Ag^2 be an integer, and then
yg^4 must be an integer as well, meaning it is captured in the integer
cases for

z = g^4(-A +/- sqrt(A^2 + 4j^2(M^2 - Ag^2)/g^4))/2(M^2 - Ag^2)

so it must be true that by solving out the full expression you can for
at least one case split up the factor of M, for the case where Ax has M
as a factor, and factor M, for any non-zero j coprime to M.

So the full perfect algorithm can be easily derived now from

z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

as you solve for Ax using

Ax = +/-(f_1 - f_2) + 2j^2

where f_1 f_2 = Tj^2, and you iterate through all possible integer f_1
and f_2, and take the gcd of Ax with M.

If Ax has M as a factor, then you calculate that ratio of z to x.

The numerator is just

(+/-(f_1 - f_2) + 2j^2 +/- (f_1 + f_2))

while the denominator is

2M^2 - 2(+/-(f_1 - f_2) + 2j^2

and you divide out any factors in common between them, and then take
the gcd of the denominator with M, and for at least one case for any
non-zero j coprime to M, you will have a prime factor of M.

The basic algorithm is now perfect. I think there are far faster more
elegant algorithms out there, but at this point, it's proof of concept
time.

James Harris

Relevant Pages
Loading