Harristotelian Logic

Contrary to conventional wisdom I've found a congruence based way to factor a target composite T, which thankfully is also very simple as in challenging orthodox views I've found that simple is best.

With all positive integers, given a target composite T to be factored, first find a prime number p near to, or less than sqrt(T). Then pick k such that k = p-1. Make sure k is coprime to T.

Next you calculate positive integer 'a', with n=1, using

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

where if it does not exist, you can change n and try again, or decrement k, and try again, where there should be a 50% probability for each try that it will exist as there are (p-1)/2 quadratic residues mod p. The ambiguity there in process has to do with the apparent equivalence of either approach.

That is the one key equation which you'll notice relies on quadratic residues, but then also you are considering nT mod p, so the issue of focusing on factoring nT has to be addressed.

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

If you find 'a', you check ak to see if it is greater than p and if not, you decrement k, and try again.

If it is greater than p you check for a factorization into f_1 and f_2,where

f_1*f_2 = nT

with

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

If you've succeeded when you take ak modulo p, you will have a factor of T.

Note there is an existence condition, where you can find a value I call k_0, which is determined by finding k such that

abs(nT - (1 + a^2)k^2)

is a minimum, as a k that will factor nT non-trivially must be within floor(k_0/2p) steps from k_0 where each step is in increments of 2ap, so if you find that you do not have a solution you can check to see how close you were, which is how the focus is on nT. The k_0 result is a remarkable and surprising one where I will try to show some of the theory and the underlying equations at the end.

The algorithm will factor nT mod p, so the goal is to have it factor nT, where n is a minimum, as the algebra is using n mod p as well, and key to that I'd hypothesize is finding a small 'a' with a large k, where of course =E1k is greater than p.

So no matter what, if you get to f_1 you are factoring nT mod p, but your hope is to factor nT and it's not completely clear to me how hard it is to get that happening.

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 equations result trivially from considering a simple system of equations:

z^2 = y^2 + nT

where n is some non-zero integer, you can introduce z = x+ak, and substitute out:

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

multiplying out and simplifying I then have

x^2 = y^2 + nT - 2axk - a^2*k^2

and you could could factor nT - 2axk - a^2*k^2 to get y, but the problem with that is that you don't know x, so I use a trick:

2ax = k + p*r.

Then the above becomes

x^2 = y^2 + nT - (1 + a^2)k^2 - k*p*r

which removes x, and that's the point, as now I can move modulo a prime p of my choice. If k = 2ax, then

x^2 = y^2 + nT - (1 + a^2)k^2.

And finally

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

Existence of k_0 is found by considering

x^2 = y^2 + nT - (1 + a^2)k^2 - k*p*r

as r = 0 at the correct k, as let k = k_0 + p*j, where j is an integer, then

x^2 = y^2 + nT - (1 + a^2)(k_0^2 + 2p*j*k_0 + p^2*j^2) - (k_0 + p*j)p*r

and as k_0 is constant as is x, y, a and nT, as you move k either forward or back from k_0 the p^2*j^2 term will tend to dominate so that r will tend to be negative, assuming k is positive, to counterbalance it.

It can be shown that the k_0 is the minimum value for k.

It is my hope that I've generated some interest in evaluating this congruence algorithm for factoring. According to the theory it scales well with the only additional time with increasing size of T coming from finding p and calculating 'a' which requires finding a quadratic residue modulo p.

I would appreciate comments or criticisms on this approach and apologize if it's not close to some standard form. I am cutting and pasting from several sources.