Harristotelian Logic

After my latest miss-steps I went back, looked everything over again and finally noticed something that was bizarrely, simply obvious and staring me in the face.

Here's the factoring algorithm that results.

Given an odd target composite T, for a test odd prime p, iterate through non-zero integers k until

T - k^2 mod p

is a quadratic residue. If no k will work, discard that prime p and try another. If one does work then get á from

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

Then you have residues of your factors modulo p from

f_1 = ák mod p

and

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

where f_1*f_2 = T.

Trivial factorizations if they are given can be discarded by noting that your residues is the same as T, though one caveat is that for a given prime p, one of your factors may equal the residue of the target composite T.

Also if with r^2 = T - k^2 mod p, r^2 = k^2, then that result should be discarded, though it may indicate that one of your factors equals the residue of T for that particular prime.

The sign of the correct k and á that work seems to correlate with the sign of the factors as long as neither factor is less than p.

The simplification occurred to me after noticing a few obvious things. It should work well though I guess maybe I'm still missing something so out it goes to see if someone will test it.

If it does work well then factoring a target composite T is just about getting enough primes that will work.

For example, if 80 primes are found then a target at least as large as 80! would topple even if you took primes starting at 3 and working your way up, so assuming about 50% would work then using only primes under 1000, you could factor a number greater than 7.1569457046263802294811533723187e+118.