Harristotelian Logic

An initial presentation of a prior version of this algorithm had a fatal error. The underlying equations are the same but I was using them wrong. Here is the corrected algorithm.

It defies conventional wisdom by showing a congruence based factoring method that allows you to pick a large enough prime p, and solve for f_1 and f_2, where f_1*f_2 = T, where T is the target composite to be factored mod p.

With all positive integers, given a target composite T to be factored, first find a prime number p greater than sqrt(T). Then set a variable I call 'a', to a=2 and calculate a variable I call k, with the following congruence relationship:

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

where if it does not exist, you increment 'a' by 1 and try again. There is a 50% chance that any particular 'a' will work as there are (p-1)/2 quadratic residues modulo p.

If you get a k then you check for a solution for f_1 and f_2,where

f_1*f_2 = T

with

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

If ak is greater than p, and you've succeeded when you take ak modulo p, you will have a factor of T. If it is less than p, see if a(p-k) is greater than p, and check that mod p if it is. However, f_1 may be the larger factor so also check f_2, as then it will give the smaller factor exactly or p - f_2 will.

A key equation is

T - k^2 - f_1^2 = 0 mod p

so if T - f_1^2 is not a quadratic residue modulo p, no k will exist, so if you find an 'a' and k that fit the criteria above but do not factor T, then change p. (It can be shown that instead you've factored T mod p greater than 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(T - (1 + a^2)k^2)

is a minimum, as a k that will factor T 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 T. 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.

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.