SF: Refresher course

Without hearing the overall picture of what SF is, it can be easy to
get confused or worse, think it is just about the mindless ramblings of
some Usenet crackpot, when the actual ideas are fairly straightforward
and sensible.

First off "SF" stands for surrogate factoring, where the idea is to
factor a target composite, which I usually call T, by first factoring
some other number I call the surrogate, found off of T.

It has been pointed out to me before in replies on Usenet that while I
invented the term "surrogate factoring" the most effective modern
factoring techniques can be said to use surrogate factoring.

My ideas for using surrogate factoring have focused on what I now call
classical techniques, where I took simple quadratics and tried to
figure out creative ways to get practical surrogate factoring
techniques--which all ultimately failed to be practical--and my new
surrogate factoring equations derived from my own algebraic number
theory research that I call non-polynomial factorization.

The first set of equations I gave from that research were not
practical, while it's not clear to me that the second set cannot be
made practical, while there have been posters who have claimed it's
not.

Here are those equations:

T = (x+y+vz)(vz-x)

where x, y and z are defined by

x^2 + xy + k_1 y^2 = k_2 z^2

so the equation that defines x, y and z is a hyperbloid

and

(2(v^2 - k_2)z + vy)^2 = ((1-4k_1)y^2+4T)v^2 + 4k_2(k_1y^2 - T)

where you pick y, k_1 and k_2.

First off, there is no debate about correctness. Those equations are
perfect, and if you plug in all the numbers, you do get a factorization
of T, but of course, you may not have all rationals, or you could have
a trivial factorization.

Notice that you have a LOT of variables, which to me isn't surprising
for what may be a solution to the factoring problem! Getting a lot of
variables is also a symptom of my algebraic number theory research of
non-polynomial factorization.

In this case, there are 7 variables. You pick T, as the composite to
be factored, so that drops you down to 6. And you pick y, k_1 and k_2,
which then drops you down to 3, but you have only two constraining
equations, as notice, importantly,

T = (x+y+vz)(vz-x)

is a resultant and NOT a constraining equation.

That is, given

x^2 + xy + k_1 y^2 = k_2 z^2

and

(2(v^2 - k_2)z + vy)^2 = ((1-4k_1)y^2+4T)v^2 + 4k_2(k_1y^2 - T)

it must be true that

T = (x+y+vz)(vz-x).

To my knowledge there is no way known to get such equations outside of
my techniques and they are unique in the factoring field.

No one has ever seen anything like them before my research.

And no one can replicate anything like them without using my research
techniques.

There is no debate about those points, interestingly enough, as people
simply dodge around them like ignoring the elephant in the room!!!

So there are only two equations constraining 3 variables, but
importantly with


(2(v^2 - k_2)z + vy)^2 = ((1-4k_1)y^2+4T)v^2 + 4k_2(k_1y^2 - T)

you factor k_2(k_1y^2 - T) to get v and then z and then x, where the
assumption is that you will factor that into integers which gives the
final constraint.

Oddly enough, now we can talk about Cantor, as looking at the
relationship between the variables, your picking of y is just some
human thing and k_1 and k_2 are not part of the factorization but are
part of the equation defining the hyperbloid, where there is no mention
of T:

x^2 + xy + k_1 y^2 = k_2 z^2

The target composite is actually kind of buried in there where it's
hard to see how it ends up being factored!

But that's surrogate factoring.

So back to Cantor and the question of mapping of the infinite set of
rational solutions versus the infinite set of non-rational solutions,
as importantly there are no simplifying equations that relate the
variables to factors of T.

As a sidenote, previous surrogate factoring equations of mine failed in
this area as simplifying relations could be found, where you could just
find a way to relate factors of T to the variables, and then show that
the odds were long that you'd get a solution and that the bigger T was
the less likely you were to get a solution.

In contrast, with these equations, if you try to generally solve them
in terms of factors of T, you get quintics.

There was a burst of debate about the significance of that as I said
you can't generally solve quintics and others noted that you can and
the proper answer here is that you cannot generally solve quintics
using radicals, which prevents you from using a general solution to
figure out how to pick variables so that you guarantee getting
rationals.

But if you can't guarantee rationals are you then more likely to get
non-rationals?

Think carefully here. There are an infinite number of both. If you
believe Cantor you might say that there is in some sense a bigger
infinity of the non-rationals, but if so, are not the odds of rational
solutions then 0?

Fun stuff. Sorry to digress that way but I found it fascinating.

The actual open research question is, why would the system pick
rational or non-rational?

Can equations be found that would tend to push the probability towards
non-rationals, or is that impossible and the system does not care?

If it does not care then it will, over infinity, tend to give either
equally.

But, oddly enough, you can still factor with non-rational solutions!

I'll close with a demonstration of a simple factorization using the
given equations, where 119 is factored, though x is non-rational:

T = 119 = 17(7)

so my main equation is

(2(v^2 - k_2)z + vy)^2 = ((1-4k_1)y^2 + 476)v^2 + 4k_2(k_1 y^2 - 119)

next step is to make

((1-4k_1)y^2 + 476)

a square and I'll let

((1-4k_1)y^2 + 476) = 9

and let y=1, so I have

1-4k_1 + 476 = 9

which gives k_1 = 117, so now I have

(2(v^2 - k_2)z + vy)^2 = 9v^2 - 8k_2

and letting k_2 = 4, I can just use v=3, so I have

(2(9 - 4)z + 3)2 = 9(9) - 8(4) = 49

so 10z + 3 = 7, and z = 2/5.

Now I go to the second equation

x^2 + xy + k_1y^2 = k_2 z^2

and making the substitutions I have

x^2 + x + 117 = 16/25

so

25x^2 + 25x + 2909 = 0

which gives

x = (-25 +/- sqrt(625 - 4(2909)(25)))/50 = (-25 +/- sqrt(-290275))/50

and, l have an irrational x:

x = (-25 + sqrt(-290275))/50

so x+y+vz = (-25 + sqrt(-290275))/50 + 1 + 3(2/5)

and

x+y+vz = (85 + sqrt(-290275))/50

and dividing out shared algebraic integer factors should mean the
numerator is an algebraic integer factor of 119, which it is!

(17 + sqrt(-11611))(17 - sqrt(-11611))/100 = 119.

Here the factorization split off 17 and only non-rationally factored 7,
showing how you can still factor with non-rational solutions.

So that's kind of an overview of my surrogate factoring. Hope it was
informative.

Oh, as an important sidenote, I think the research is kind of scary, so
I don't do more with the equations like trying to make them practical,
while I find it bizarre that researchers in the field think it just
safe to completely ignore them.

If they do work, and someone finds out how to make them practical, then
that decision could have sweeping economic and political impact around
the entire world.

Think about it--if it can be made practical--some math people with that
kind of power, making decisions at that level, where politicians don't
matter, militaries don't matter, where because of accidents of history,
they are the most powerful people in the world, with one of the most
important decisions ever known.


James Harris

.

Relevant Pages

  • Re: surrogate factoring
    ... quality "SF time" than anyone other than James ... ... "surrogate factoring" doesn't really mean anything specific. ... since the set of all non-zero rationals constituted the search space ...
    (sci.math)
  • Proper evaluation of surrogate factoring
    ... Surrogate factoring is just kind of a wild idea that means you have to ... I am being very serious here, modern mathematicians lie a lot. ...
    (sci.crypt)
  • Re: SF: Areas of confusion, infinity
    ... > notably the set of rationals. ... choosing any integer is the same as the probability of any other ... That's what make the factoring problem interesting, i.e., not ... > is naive with the surrogate factoring theorem. ...
    (sci.crypt)
  • JSH: Results that are much more fun
    ... It's almost a relief now to have the results around residues as so ... used them with no success against the factoring problem. ... It's like taking over the definition of mathematical proof ... Ok, so I worked on surrogate factoring for years with little success, ...
    (sci.math)
  • Re: Results that are much more fun
    ... used them with no success against the factoring problem. ... It's like taking over the definition of mathematical proof ... Ok, so I worked on surrogate factoring for years with little success, ... and found that I could solve quadratic residues mod p. ...
    (sci.math)