Harristotelian Logic

While writing a long post about the current state of the art on surrogate factoring, I found myself talking about an equation that constrains a variable I call z, where

z^2 = y^2 + nT

and T is a target to be factored, while n is a free integer variable.

Seemed like a minor thing to me at the time but soon I found myself consumed with properly defining what I called the z constraint, and just figured out the full theory today, as the motivation has been to have a complete surrogate factoring theory.

That constraint is that for any factorizations of T into two positive integers f_1 and f_2, where there exists an odd prime p less than both, or if f_1 is the smaller factor p - f_1 is less than f_1, where also exists an α such that

k^2 = (1 + α^2)^{-1}(nT) mod p

then

z = (1 + 2α^2)k/(2α)

in general when nT mod 3 = 2, but conditionally if not, as then z is coprime to 3, and the z constraint applies only if also x exists as an integer where

x^2 = y^2 mod p

and z = x + αk.

The requirement that p be less than the smaller factor f_1, or that p - f_1 be less than f_1 comes from solutions for the factors modulo p, as if you have positive integer factors f_1 and f_2 where f_1*f_2 = nT:

f_1 = αk mod p

and

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

(Oh yeah, that's cool in and of itself. If you play with these equations at all you'll find that with z divisible by 3, you can always find an odd prime p for which those hold.)

As an example of the conditional case when z is not divisible by 3, consider, n=1, T = 23(29)=667, p=17, so I can directly calculate tha= t z = (23 + 29)/2 = 26.

Notice that k^2 = (1 + α^2)^{-1}(667) mod 17 = (1 + α^2)^{-1}(4) mo= d 17

so α = 1 works to give k^2 = 2 mod 17, so k = 6 mod 17 is a solution= .

And notice then that f_1 = αk mod p = 6 mod 17, corresponding to the solution 23.

And f_2 = α^{-1}(1 + α^2)k mod p = 12 mod 17, giving the residue modulo 17 of 29.

But intriguingly enough

z = (1 + 2α^2)k/(2α)

is not valid for any integers k and α.

And if you dig deeply into the surrogate factoring equations you find that x cannot exist as an integer where

x^2 = y^2 mod 17

and z = x + αk. Note that y is given by (29-23)/2, so y=3, for this example.

As x is part of the full derivation it follows that x is not rational, and further as no integers k and α can give z, it follows that both of them are non-rational as well. because

k^2 = (1 + α^2)^{-1}(nT) mod p

so α = 1 mod 17, is what is actually happening, but it's not rational.

So you factored with the help of non-rationals, as well as the helper prime 17.

For more mundane examples and to see the z constraint in action, either use T = 2 mod 3, or if T = 1 mod 3, let n=5 or n=11 to force = nT mod 3 = 2, or any other n that you choose though I do stay away from n=2, as I stay away from even nT.