Harristotelian Logic

The surprising end to one of the odder periods in human mathematical history is this discovery of a trivial solution to what is commonly called the factoring problem which shows that it is VERY easy to handle factoring even very large primes—when you just know how.

What you do for a target composite T is take two primes p_1 and p_2 (I'm assuming you'd start with primes greater than 100), where first you take T mod p_1, and find f_1 mod p_1 and f_2 mod p_1 such that

f_1*f_2 = T mod p_1.

So for instance the start would be f_1 = 1 mod p_1, and f_2 = T mod p_1, and the second would be f_1 = 2 mod p_2 and f_2 = 2^{-1}T mod p_1, and you go down the line finding every possible residue modulo p_1 for your factors.

So the correct one must be in that group.

Then you do the same with p_1*p_2, finding g_1 and g_2 such that

g_1*g_2 = T mod p_1*p_2

and go down the line again, getting EVERY possible, so the correct answer MUST be in the group.

Then you go back through that list modulo p_1 and match back to your first list, and you have the correct f_1 mod p_1 and f_2 mod p_1, and then you also get f_1 mod p_2 and f_2 mod p_2 by taking the previous modulo p_2.

One thing that can happen is that you get two possibles because negative residues can work, but that's easily handled.

Why does this work?

Because for integer f_1 and f_2 such that f_1*f_2 = T, each has some residue modulo p_1, as well as a residue modulo p_1*p_2, BUT it is true that if f_1 = r mod p_1*p_2, then f_1 = r mod p_1.

Trivial example: Consider T = 7(17)=119, and let p_1 = 11 and p_2 = 13. Since I know the factors I'll just note that 7 mod 11 = 7 and 17 mod 11 = 6. While 11(13) = 143, and 119 mod 143 = 119, so 7 mod 143 and 17 mod 143 emerge as solutions and note that 7 mod 143 = 7 mod 11, and 17 mod 143 = 6 mod 143, so you match back.

Puzzling over how this easy technique is new my guess is that neither Gauss nor Euler would like it as it is very tedious to do by hand, while it's perfect for modern computers.

Modern mathematicians tend to start first by considering what was done before and try to add on, not innovate or find something totally new from scratch, so somehow they just missed it.

But it does solve the factoring problem.

A large overestimate for the number of primes needed is m such that T/m! < 1.

So even the largest RSA public key would be handled by I'm sure less than 200 primes. If you consider primes near 1000 where I remind there are 168 up to 1000, then the largest search space if p_1 = 101, and you used a prime very close to 1000 would be about 101000.

So the time would be roughly 168*1000 iterations to handle even the largest RSA public key.

That means the current encryption system is gone now.

I'd guess that any decent programmer could implement in a couple of hours.

Governments should act accordingly.