Harristotelian Logic

Previously I've noted the easy derivation of some remarkably simple congruences that give f_1 mod p and f_2 mod p, 75% of the time, when f_1*f_2 = nT, where T is a composite you wish to factor, p is a prime of your choice and n is a non-zero integer of your choice:

f_1 = ak mod p

and

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

where

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

I've been challenged to come up with a practical factoring algorithm, based on them as there is no doubt about correctness and show that it is an advance on current factoring methods.

While I think there are multiple ways to use those congruences practically for factoring, I've settled on a simple approach relying on what is called the Chinese Remainder theorem, where if you get solutions for a succession of primes, p_1, p_2, p_2,…, p_m, where m has as an upper bound m such that T/m! < 0, you can use it to get exact values for f_1 and f_2.

There are two steps in an algorithm that relies on the Chinese Remainder theorem where the first step is making certain you have f_1 mod p and f_2 mod p, for your target composite, which involves first solving for them with n=1, and then solving for them again with n=2, and checking to see if you get the same values by using

g_1 = 2^{-1} f_1 mod p, or g_2 = 2^{-1} f_2 mod p

as of course 2 being a prime can attach itself to only one factor, or you can do that with any other prime you might choose. If two tries doesn't get you the answer then you can try 3 or 4 different n's, or even 5, just to be sure where you get a lot of leeway as you will need so few primes for even a very large number.

(My understanding at this time is that under 200 primes would be enough for even the largest currently available RSA public key.)

The final step then is figuring out which factor you have as you MUST have f_1 and f_2 be the same down the line with each prime.

To accomplish that task there is a simple procedure to follow:

If f_1 = r_1 mod p_first, and f_2 = r_2 mod p_first, while

f_1 = r_1' mod p_second, and f_2 = r_2' mod p_second

then you can just multiply

f_1 - r_1 = 0 mod p_first times f_2 - r_2' = 0 mod p_second

to get

T - f_2*r_1 - f_1*r_2' = 0 mod p_first*p_second

where you assume you have them in the right order, and you can now solve for
f_1, to get

f_1 = (T - f_2*r_1)r_2'^{-1} mod p_first*p_second.

f_1 = (T - f_2*r_1)r_2'^{-1} mod p_first*p_second

which is

f_1 = (T - f_2*r_1)r_2'^{-1} mod p_second

And now, since f_1*f_2 = T, you can just substitute out f_1, and get

(T - f_2*r_1)r_2'^{-1} f_2 = T mod p_second

so

r_1*r_2'^{-1} f_2^2 - T*f_2 - T = 0 mod p_second

which is

f_2^2 - T*r_1^{-1}*r_2*f_2 - r_1^{-1}*r_2*T = 0 mod p_second

where you now complete the square, which will allow you to solve for f_2 mod p_second when you resolve a quadratic residue.

If that residue is NOT resolvable then you know that f_1 with p_first is actually f_2 with p_second, but if it is resolvable and you solve for f_2 and get the same answer as you had before, then you know your ordering is correct.

And you just do that down the line, so that you have f_1 as the same number and f_2 as the same number and then you use the Chinese Remainder theorem, and you will have f_1 and f_2, exactly.