Re: Surrogate factoring, complete theory

jstevh_at_msn.com
Date: 03/06/05 

Date: 6 Mar 2005 13:05:03 -0800

Surrogate factoring is what I call methods that try to factor a target
M by using the factorization of another number I call the surrogate,
which I usually label T.

I've been looking for a perfect surrogate factoring algorithm that
will always factor a target M.

The two main quadratics in this approach are

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
coprime to M that is 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.

I wish to focus on Az because there must exist some integer Az that
has a single prime factor of M, which follows from

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

so let

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

so that

x = zr

where r is a prime factor of M, then using my starting quadratics, and
substituting out x, I have

yr^2 z^2 + Arz - M^2 = 0

with

yz^2 + Az - j^2 = 0

so multiplying the second by r^2, I have

yr^2 z^2 + Arz - M^2 = 0

with

yr^2 z^2 + r^2 Az - r^2 j^2 = 0

and subtracting the first from the second gives

(r^2 - r)Az = r^2 j^2 - M^2

assume that r = n/d, where n and d are coprime integers, then

(n^2 - nd)Az/d^2 = (n^2 j^2 - d^2 M^2)/d^2

which is

(n^2 - nd)Az = (n^2 j^2 - d^2 M^2)

and use j^2 = M^2 - T, to get

(n^2 - nd)Az = (-n^2 T + n^2 M^2 - d^2 M^2),

so

n(n-d)Az = (-n^2 T + (n-d)(n+d) M^2)

so

Az = (-n T/(n-d) + M^2 (n+d)/n)

proving that n-d must be a factor of T.

Now since x = zr, then x = zn/d, so

Ax = Azn/d.

From

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

I know that d must share prime factors with 2j^2 - 2Az, so it must be

coprime to Az except possibily factors shared with 2 or j^2.

Now I can use

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

to get

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

and I want to focus on the denominator as that must have d as a factor.

Well, let's look at *rational* g_1 and g_2 such that

g_1 g_2 = Tj^2

and consider the positive solution of the square root so then

Ax = g_1 - g_2 + 2j^2, so

substituting into

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

and taking the positive of the square root, I have

(-g_1 + g_2 - 2j^2 + g_1 + g_2)

which gives 2g_2 - 2j^2

and now let g_2 = f_1 d_2/d_1,

where f_1 is an integer factor of Tj^2, with f_2 being the other factor
and d_1 is a factor of d with d_2 being the other factor where d_1 is
coprime to d_2, so then

g_1 = f_1(d_2)/d_1 and g_2 = f_2(d_1)/d_2

so that

g_1 g_2 = f_1 f_2 = Tj^2

as required.

Then substituting gives

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

        (f_1 d_2^2 - f_2 d_1^2 - 2j^2 d_1 d_2)/d_1 d_2.

showing that that d_1 d_2 does equal d.

Now substituting into

2g_2 - 2j^2

I have

2f_1 d_2/d_1 - 2j^2, which is

2(f_1 d_2 - 2j^2 d_1)/d_1

and that d_1 in the denominator will multiply up so that I have

x = z(d_1 d_2M^2 - (f_1 d_2^2 - f_2 d_1^2 - 2j^2 d_1 d_2))/d_2(f_1 d_2
- 2j^2 d_1)

and since d_2 is coprime to d_1 that requires that d_1 be a factor of
f_1 for the denominator to have d as a factor.

But f_1 is a factor of Tj^2, so d_1 and therefore d_2 is a factor of
Tj^2.

Going back to

Az = (-n T/(n-d) + M^2 (n+d)/n)

and concentrating on T/(n-d), I can use d_1 d_2 = Tj^2, to have

T/(n - d_1)

and multiplying top and bottom by d_2, I have

Td_2/(d_2 n - Tj^2)

and now multiplying the top by d_1, I have that

T^2 j^2/(d_2 n - Tj^2)

must include cases where n is given as you consider integers f_1 and
f_2, such that

f_1 f_2 = T^2 j^2, and take the gcd of

f_1 + Tj^2

with M, to get a prime factor.

James Harris

Relevant Pages

  • Re: Surrogate factoring approach, analysis
    ... >> It turns out that the analysis behind my surrogate factoring ... Each is the product of two primes whose length is up to ... Each factorization is taken a few minutes now... ... the target, which I call M. ...
    (sci.math)
  • Re: Surrogate factoring approach, analysis
    ... >> It turns out that the analysis behind my surrogate factoring ... Each is the product of two primes whose length is up to ... Each factorization is taken a few minutes now... ... the target, which I call M. ...
    (sci.crypt)
  • Re: Surrogate factoring, complete theory
    ... Surrogate factoring is what I call methods that try to factor a target ... M by using the factorization of another number I call the surrogate, ... assume that r = n/d, where n and d are coprime integers, then ...
    (sci.crypt)
  • Re: Surrogate factoring, complete theory
    ... Surrogate factoring is what I call methods that try to factor a target ... M by using the factorization of another number I call the surrogate, ... substituting out x, I have ...
    (sci.crypt)
  • Re: Surrogate factoring, complete theory
    ... Surrogate factoring is what I call methods that try to factor a target ... M by using the factorization of another number I call the surrogate, ... assume that r = n/d, where n and d are coprime integers, then ...
    (sci.math)