Re: Surrogate factoring, complete theory

jstevh_at_msn.com
Date: 03/06/05 

Date: 6 Mar 2005 09:39:02 -0800

Here we go again...should be it though...

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)

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

Now since x = zr, then x = zn/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)

as the x must have 1/r as a factor, so

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

and I want to focus on the denominator as that has 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

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

and

(2g_2 - 2j^2), and now let g_2 = f_1 d_2/d_1, so

2(f_1 - j^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

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

so

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.

Now focusing again on

2(f_1 - j^2 d_1)

since f_1 f_2 = Tj^2 it's possible that f_1 shares prime factors with
j^2.

Letting h_1 be shared factors, and *assume* f_1 is coprime to d_1, I
have

f_1/h_1 - j^2 d_1/h_1 = d

now looking at the negative solution above where indices shift, and
there is a sign change, I have

-f_2/h_2 - j^2 d_2/h_2 = d

and letting

c_1 = f_1/h_1, and c_2 = f_2/h_2

and letting

m_1 = j^2/h_1 and m_2 = j^2/h_2

I have

c_1 - m_1 d_1 = -c_2 - m_2 d_2

and now using d_2 = d/d_1, I have

c_1 d_1 - m_1 d_1^2 = -c_2 d_1 - m_2 d,

so

m_1 d_1^2 - (c_1 + c_2)d_1 - m_2 d = 0

and solving for d_1

d_1 = (c_1 + c_2 +/- sqrt((c_1 + c_2)^2 + 4dj^2))/2g_2

where I have a sign problem, but meaning that either d, c_1 or c_2 is
negative, but more importantly,

c_1 c_2 = T, with the assumption that d_1 and d_2 are coprime to T.

But that would force d = T, but with n a prime factor of M,

n-d is coprime to T

so d cannot equal T. Therefore the assumption of coprimeness between
f_1 and d_1, also made between f_2 and d_2 but not specifically stated,
is false, proving that d must share prime factors with T.

Further since c_1 c_2 only have prime factors of Tj^2, it must be true
that d is a factor of T.

Ok, so where's a possible hole? Well I'm looking at

sqrt((c_1 + c_2)^2 + 4dj^2)

and saying that because c_1 and c_2 are factors of Tj^2 that d must be
as well, as that's what fits.

I think I'm right, but I want to think some more on that point.

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, ... substituting out x, I have ...
    (sci.math)
  • 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: Basic argument, algebraic integers
    ... > what are the constant terms? ... > where the v's and w's are algebraic integers in each case coprime to ... You are wrong that finding such a factorization is "irrelevant ...
    (sci.math)
Quantcast