Harristotelian Logic

Oddly enough a simple approach to factoring comes from not attacking the problem directly, but by instead taking a back door approach, where you start with two important relations:

z^2 = y^2 + T

and

x^2 = y^2 mod p

where T is the target composite to be factored and p is an odd prime to be determined, where notice that for a non-trivial factorization, there are an infinity of values for x, so at first blush this approach may seem naive, until you start whittling that infinity down.

The most clever approach I've found is to use k=2ax mod p, as the two new variables allow me to find that:

x^2 = y^2 + T - (1 + a^2)k^2 mod p

and now I have a way to narrow that infinity down!!! As let T - (1+a^2)k^2 = 0 mod p, and I have a smaller set of solutions, and even can have cases where no solutions exist, as:

k^2 = (1+a^2)^{-1}(T) mod p

so if (1+a^2)^{-1}(T) is not a quadratic residue modulo p, there is no integer k.

Remarkably enough I can now actually solve for z and y mod p:

z = (2a)^{-1}(1 + 2a^2)k mod p

and

y = (2a)^{-1}k mod p

So when does all that work? Well, remember that there are an INFINITY of solutions for x at first, but I narrowed that down with:

T - (1+a^2)k^2 = 0 mod

So if THAT relation holds then presumably you should have solutions, EXCEPT notice that with the solutions for z and y, the variable k is in both, and it can occur that k is a factor in both—which is a block unless T has k as a factor!!! The situation is actually even more complicated as with z and y, you can get solutions for factors f_1 and f_2 where f_1*f_2 = T:

f_1 = ak mod p

and

f_2 = a^{-1}(1 + a^2)k mod p

and again k provides a possible block, as for instance with a=1, if k is less than p, and z is less than p, then those relations would require that f_1 and z have the same factor, which would force it into f_2, and into T, as:

z = (f_1 + f_2)/2

And similar problems happen with y, as y = (f_1 - f_2)/2, and I call the first situation the z constraint, while the second is the y constraint.

But if none of the 4 constraining equations, the z, y, f_1 and f_2 equations give a conflict, and T - (1+a^2)k^2 = 0 mod p, then this approach MUST give solutions.

But then, how do you use it?

Here's a quick example of a factorization using all of the machinery above:

Let T=341. Then p=17 is the greatest prime less than sqrt(341) and starting with a=1, gives

k^2 = (2)^{-1}(341) mod 17 = 9(1) mod 17 = 9 mod 17.

so it does exist and k=3 or k=14 are possible, but with the first f_1 = ak = 3 is not a factor and 14 is not either. So next check f_2, f_2 = a^{-1}(1 + a^2)k = 2(3) = 6 which is not a factor but 17-6=11, and 11 is a factor. Success!

And you have a non-trivial factorization, as 341 = 11(31).

Notice that z=(11+31)/2 = 21, so no conflict, y = (31-11)/2 = 10, so no conflict.

And the equations escape conflict with the f's by going to the negative residues, so checking p - f_1 and p - f_2 is a necessity.

So there HAD to be a solution in this case. So once k existed, without conflict from any of the 4 constraints, a factorization had to be found.

The method represents a back door into factoring which allows you to leverage an infinity to factor a composite. Your factoring engine is infinity itself. And infinity is a powerful tool!!!

You can scan through p's to find a large one, though notice you can't just pick too huge a p, as then you're likely to get a conflict with one of the 4 constraints, and you can choose the variable 'a' to try and adjust around the constraints as well, as notice if a=1, like with my example and k is even, then with:

y = (2a)^{-1}k mod p, you have y = k/2 mod p, so if k is close to p, so k/2 < p, then you conflict with f_1 = ak = k, with a=1

So when k is even you already know that a=1 will probably not work well, but then you can use a=2, or a=3, or a=6, or some other.

So what is the Big O time complexity of this approach?

It cannot be calculated, as if none of the 4 constraints conflict, and k exists it is 100% success rate, but if one of the constraints blocks it just doesn't work. AND you have to solve for k, so finding a quadratic residue is important!

But some of you may know this approach leads to a method for solving quadratic residues as well, simply by reversing it, as importantly you have:

k^2 = (1+a^2)^{-1}(T) mod p and z = (2a)^{-1}(1 + 2a^2)k mod p

but z = (f_1 + f_2)/2, so you have

f_1 + f_2 = (a)^{-1}(1 + 2a^2)k mod p

So if you have a quadratic residue q, you can just let T = (1+a^2)q mod p, and factor T, to get f_1 and f_2, which gives you k, from:

k = a(1 + 2a^2)^{-1}(f_1 + f_2) mod p

So you can use this approach in the opposite direction to solve for quadratic residues! And again, if none of the 4 constraints block it MUST work. It must work. Perfection.

How do you know? Because given an integer y, x^2 = y^2 mod p has an INFINITY of solutions. I narrowed that infinity down with the critical relation:

T - (1+a^2)k^2 = 0 mod p

Trying to factor T, you have to find a p for which k exists, but going the other way to find a quadratic residues you BUILD T, so you know k exists if q is a quadratic residue modulo p, so if none of the 4 constraints are in the way, there is no way for a subset of that infinity not to work. Infinity has no choice, it has to solve the quadratic residue for you then.

So you have mathematically knowledge of a perfect method for factoring and for finding quadratic residues which reveals itself by going at factoring indirectly.

It is a perfect method.