Harristotelian Logic

The usefulness of the factoring equations in terms of how effective they are against large numbers still remains to be determined, however, a fairly simple algorithm using them is readily apparent.

Given a target composite T to be factored, first find a prime number p greater than sqrt(T). Then pick a positive integer 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.

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.

If you wish more criteria before you check you can find k such that

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

is a minimum, which is what I call k_0. A k that will factor non-trivially must be within (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.

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 ak 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, with n=1 gives

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

so it does not exist. Trying now k=9, gives

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

so a=2.

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.

Note that k_0, from using

abs(119 - 5k^2)

is k_0 = 5, as that is the value of k that gives the minimum value, and 5 is within 0 steps in increments of 44 of 9, as the steps are floor(5/22).

To be 1 step away the k that factored would have had to be greater than or equal to 49.

And that completes a demonstration of the factoring algorithm that follows from the prior results. It's rather remarkable to me to have my own factoring algorithm and also odd that I can't say exactly how well it works!

Nothing succeeds like success.

Antagonism from the mathematical and cryptographic communities to this research is not about its value but about politics and human weakness: guys who think that people like me are beneath them so they refuse to acknowledge research they think puts someone like me higher.

It's all about a pecking order.