Surrogate Factoring Solution

jstevh_at_msn.com
Date: 03/10/05 

Date: 9 Mar 2005 17:45:22 -0800

My apologies up front, as I have the solution now, so it makes sense to
start a new thread, though I wonder about the sense of posting an
actual solution.

It turns out that solving for A and y is key to that solution, as
remember

yx^2 + Ax - M^2 = 0

and

yz^2 + Az - j^2 = 0,

so

A = (z^2 M^2 - x^2 j^2)/xz(z-x)

and

y = -(zM^2 - xj^2)/zx(z-x)

and focusing again on y/A^2, which I have an algorithm for calculating,
I have

y/A^2 = -xz(z-x)(zM^2 - xj^2)/(z^2 M^2 - x^2 j^2)^2

and focusing on the denominator, I wish to know what to multiply

8j^2 M^2(y/A^2)

times so that it is an integer, so assuming x has a single prime factor
of M that I'll call g_1, so x = g_1, and using g_2 = M/g_1, I have

y/A^2 = -g_1^2 z(z - g_1)(zg_2^2 - j^2)/g_1^4(z^2 g_2^2 - j^2)^2

which is

y/A^2 = -z(z - g_1)(zg_2^2 - j^2)/g_1^2(z^2 g_2^2 - j^2)^2

and now focusing on

z^2 g_2^2 - j^2, I can just let

n = z^2 g_2^2 - j^2, and solve for z, so

z = sqrt(n + j^2)/g_2^2

and notice you need to get an integer z, but you don't know what g_2
is, or you wouldn't need to try and factor, but, you do know that M^2
will handle that g_2^2, so you need

n + j^2 = k^2 M^4

where k is some arbitary natural.

The simplest solution then is n = M^4 - j^2, which you will have to
factor.

If it's hard to factor you can iterate k, and get another n.

You use that n with

sqrt((8j^2 M^2 (y/A^2) + n^2(2j^2 + T))^2 - n^4 T^2)

so the algorithm is as follows.

Given a target natural M that you wish to factor, you must first
select a non-zero integer j, such that j is coprime to M, and any such
j will work, but you wish to pick one that is large with respect to M,
like

j = M - 1

as that will make T smaller, but most importantly you want to pick j
such that T is easy to factor.

Next you calculate T, where

T = M^2 - j^2

and you factor T.

Next you find n, where simplest is to use

n = M^4 - j^2

and factor it, but if it's hard to factor you can find another n using

n = k^2 M^4 - j^2

using k an arbitrary natural number.

Now you consider integers f_1 and f_2, such that

f_1 f_2 = n^4 T^2

and you need to consider all such solutions, including seemingly
trivial ones like where f_1 = n^4 T^2, or f_1 = 1, or -1.

Then you calculate a number I call y/A^2, where the numerator num is
given by

num = +/-(f_1 + f_2) - 2n^2(2j^2 + T)

and take the gcd with M, and for at least one f_1 and f_2, you will
have a single prime factor of M.

And that is the easy answer, which is actually rather easy to derive.

I did just figure it all out, but I've had a strong feeling a simple
answer was there.

And deep down I'd hoped that someone else might find it first,
especially if it was someone who could have helped me take all of this
in-house to a friendly government agency.

I did try the NSA by direct contact a couple of months ago, but in
reply I was told that they got many claims of important mathematical
results, and they weren't interested.

And now the full answer is just out there.

Well, my dad did call me paranoid, and maybe he's right. I can keep
telling myself all kinds of scary things, but knowledge is valuable,
and I have to believe that the truth is good.

I believe that the truth is the best.

James Harris

Relevant Pages

  • Surrogate Factoring Solution
    ... though I wonder about the sense of posting an ... times so that it is an integer, so assuming x has a single prime factor ... so the algorithm is as follows. ... I believe that the truth is the best. ...
    (sci.crypt)
  • Re: Surrogate Factoring Solution
    ... > My apologies up front, as I have the solution now, so it makes sense ... > times so that it is an integer, so assuming x has a single prime ... > so the algorithm is as follows. ... > and I have to believe that the truth is good. ...
    (sci.math)
  • Re: Surrogate Factoring Solution
    ... > My apologies up front, as I have the solution now, so it makes sense ... > times so that it is an integer, so assuming x has a single prime ... > so the algorithm is as follows. ... > and I have to believe that the truth is good. ...
    (sci.crypt)
  • Re: Surrogate factoring, basic algorithm
    ... Tim Peters wrote: ... >> Well, to not be paranoid, I guess I may as well. ... of y are coprime to M, but x gives a single prime factor. ... I didn't want to complicate the algorithm, as in my opinion, that small ...
    (sci.crypt)