Harristotelian Logic

I've found that you can solve directly for f_1 and f_2 when f_1*f_2 = T, where T is a composite to be factored.

With all positive integers:

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

and 'a' is related to k mod p by

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

where p is what I call a helper prime.

Notice that because f_1 = ak mod p, ak must be greater than p, if f_1 is less than p, if k is coprime to T.

Note that a^{-1} mod p is the modular inverse mod p, as is (k^2)^{-1} mod p.

To get the direct solution you pick p a prime where p>sqrt(T) and pick for k a positive integer near p, coprime to p, if you accidentally have a factor in common with T then you have factored it, which I mention only because in programming the algorithm you need to check for that case.

You then find if 'a' exists for your k and if it does you check if ak is greater than p, if it is, then you solve for f_1, if not you decrement k, and try again. There is a 50% chance of success for each k that 'a' exists.

Example: Let T=119. Then p=11 is greater than sqrt(119), and trying k=10 gives

a^2 = (119)(10^2)^{-1} - 1 mod 11 = 8 mod 11,

but 8 is not a quadratic residue modulo 11, so no 'a' exists for this case. Trying now k=9, gives

a^2 = (119)(9^2)^{-1} - 1 mod 11 = 4 mod 11

so a=2 is a solution. And ak = 18, which is greater than 11, so

f_1 = ak = 18 mod 11 = 7 mod 11.

And you have a non-trivial factorization, as 7 is a factor of 119.

The algorithm you'll note is polynomial time and uses residues when conventional wisdom was that you couldn't solve for integer factors with residues, but the key here appears to be quadratic residues, where you get an interlocking mechanism.