Harristotelian Logic

For years I've pursued an approach to the factoring problem that I call surrogate factoring, where you factor one number I call the surrogate in order to factor the target.

And last year I finally realize that my difficulties had come from lack of simplification, so last August I sat down and thoroughly thought about what I meant by surrogate factoring and out popped only two equations:

x^2 = y^2 mod T and k^2 = 2xk mod T

where now I've simplified even further and write as

y^2 = x^2 mod T

and

k = 2x mod T

as then it's easier to see that the second one has to exist, if y and x exist, and then it's easier to show multiplying it by k, and adding to the top one:

y^2 + k^2 = x^2 + 2xk mod T, so y^2 + 2k^2 = (x+k)^2 mod T, and reverse to get

(x+k)^2 = y^2 + 2k^2 mod T, and go explicit with

(x+k)^2 = y^2 + 2k^2 + nT

and you get x and y from factoring 2k^2 + nT, and they may be the answers to your congruence of squares

x^2 = y^2 mod T

that factor T.

I had that LAST YEAR in August after that time pondering the question and I began thinking off and on about when this should work while talking about it to mathematicians, and I informed the NSA.

Yup, I was concerned that maybe I'd found something TOO SIMPLE and hoped that I'd get some attention from people who could help in case it was too effective.

With no interest from any of the professionals I would work at the problem off and on, where I couldn't seem to get an answer on how effective this could be but recently came up with the simple idea of just assuming

T = p_1*p_2

and working through what that'd mean which is what's now on my Integer Factorization page.

I now believe that page is too long, and I contemplate editing it, now realizing that the simple answer is just so pathetically simple that it is depressing.

I have a key relation that emerges from that page:

-(k+2xp)/p < m < -(k + 2x)/p

where the absolute value of m is a count of non-trivial factorizations given by this technique, and I didn't quite realize the full significance of that for a while.

But it says that if floor(abs((k+x)/p)) is greater than 0, then you MUST have a non-trivial factorization at that point, where surrogate factoring will pull the prime factor p of your target.

So you just need to make sure that the absolute value of k+2x is greater than p, and since x can be positive or negative it makes sense oddly enough to let k=1, which means

x = k*(2)^{-1} mod T = (2)^{-1} mod T

and would have the largest residue modulo T that you can get and should hopefully be larger than a small prime factor p of T.

But you still need to pick n. There are lots of ways to guess but the last big result is that once you get abs(n) over the limit, then any n greater will work.

So that could be a big number, still hard to factor, so why is this a big deal?

Well, you can get hundreds or millions of these surrogates for ANY target T, looking for one that's easy to factor and trying out any factorizations that you can get, where on my page I show an example where a truly trivial factorization of the surrogate works!

What makes this story astounding is my inability to get the math community to pay attention to it, and it took a lot of guts to bug the NSA and try to get their attention as well, and here I am with the simple answer I thought might be there, wondering about a lot of supposedly smart people.

I feel confident in my analysis and it indicates that modern mathematicians were wrong and factoring is NOT a hard problem, and in fact, by the standards of complexity of modern mathematics it has pathetically simple answer, using just a bit of algebra.

In other words, factoring is a trivially EASY problem.

It remains to be seen why mathematicians around the world, including those at the NSA, chose to deliberately ignore a new factoring method over this last year. At this point it is a profound mystery to me how they could.