# Reverse engineering surrogate factoring

Discussion in 'Recreational Math' started by jstevh, Mar 3, 2005.

1. ### jstevhGuest

There actually is a direct way to research surrogate factoring and
answer questions quickly, which is basically reverse engineering.

The basic equations are

yx^2 + Ax - M^2 = 0

and

yz^2 + Az - j^2 = 0

so

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

and you can solve 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)

and in each case multiplying both sides by A gives you

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

and

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

and you can pick an M for which you know the prime factors, and solve
for Az.

Then you just use that with

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

as I've just divided my equation for y above through by A^2

and focusing on

y/A^2 = (j^2 - Az)/A^2 z^2

you can just look at the denominator after dividing off shared factors
in the numerator and denominator.

There are three possibilities:

1. The prime factors are all related in some way to M

2. The prime factors are all related to the particular prime factor of
M that you are using, so it's crap.

3. There is no relationship between the prime factors of the
denominator of y besides the prime factor of M that you are using.

If 1. then there should be some way to generalize to a full, perfect
algorithm.

If 2. then bad news, surrogate factoring needs to know the prime
factor of M already to work consistently, so it's crap.

If 3. then surrogate factoring provides the first known perfect random
number generator.

Those are the only possibilities, and notice that there MUST be an
integer solution for Az that contains prime factors of M in whatever
combination you want, so you can check.

It looks kind of like a statistical thing to me, and I don't like doing
statistics, so I've concentrated on an upfront approach, which
basically assumes that 1. is the correct choice, and that the prime
factors of the denominator of y are either factors of M, j or T^6.

Those algorithms actually do factor at lot at small M, like under 60
bits, but for some reason they get worse and worse as you get over 60
bits, and I have to figure that some other primes are in there.

They are either related to M, individual prime factors of M, or are
random.

So you have 1., 2. or 3., and the person who can crack the code, if
it's 1., can basically factor anything. If it's 2. then that's just
it, surrogate factoring can't work. If it's 3. then it *may* still
work, but heavily probabilistically, but the world has its first
perfect random number generator outside of quantum.

That basically covers things in a nutshell. If someone has done the
reverse engineering then they may already know. I've looked curious to
see if anyone might post on this topic, and I haven't seen anything,
which lead me and my paranoid self to believe that 1. is the case, and
that someone out there in this wide world has the full solution, and is

If I liked statistics more I might explore the reverse engineering
myself, but I just don't. I'm still mostly thinking about surrogate
factoring from the theoretical side, with a few factorizations here and
there with my test programs.

James Harris

jstevh, Mar 3, 2005

2. ### Tim PetersGuest

[JSH]
I already reported on computer experiments that ignored M entirely when
picking a T, instead always adding one small prime at a time to T (first 2,
then 3, then 5, ...), then checking gcd(f-g, M) across all integer f*g=T^6
with f >= g >= 1. In all, that worked better than random-gcd in terms of
number of gcds needed, and (by the same measure) better than any method
tested to date that tried to choose T as a function of M. For products of
randomly chosen 20-bit primes, across 1000 trials it never needed to go
beyond T=2*3*5*7*11*13*17*19 to find a factor.
#3 doesn't follow.

Tim Peters, Mar 3, 2005

3. ### boattugGuest

** SF plonk! **

boattug, Mar 3, 2005
4. ### oðinGuest

There are three possibilities:
What is a perfect algorithm? You mean one that always works and terminates
in poly-time? If that is what you mean, you have never proved this, which
makes you a liar. If it is not what you mean, then it is crap, and again,
you are a liar..
And if it is crap that means that you are a liar.
That is nonsense. You have been told many times that any algorithm executing
on a deterministic computer cannot generate random numbers. You are an
idiot.
But how fast? There are already plenty of ways to factor anything given
enough time.
No idiot...

oðin, Mar 3, 2005
5. ### C. BondGuest

Note that you do not answer any significant questions in your post.

[snip]...
You still have no idea what a *perfect random number generator* is. Add
that lapse to the growing list of things you make stupid comments about.
Item 3. was not a possibility. It should have read, 3. I am an ineducable
moron.

C. Bond, Mar 3, 2005
6. ### Felix RawlingsGuest

Really? By algorithmic methods? Boy, you are even more ignorant than I
thought. How do you manage to remain so thoroughly ignorant? How come you
are not embarrassed to make a public display of your ignorance, time and
again? Are you ill?

Felix Rawlings, Mar 3, 2005
7. ### mensanatorGuest

That's why he's considered a troll. He's only pretending to be ignorant
to see how many responses he gets.

mensanator, Mar 3, 2005