### Saturday, February 09, 2008

## JSH: Factoring may be stupid simple

I was puzzling about the latest failed factoring idea wondering where I went wrong, as I really felt that there was information wrapped up in the intersection of the residues modulo T of two primes.

So I pondered some more.

Before too long I was writing out things along these lines:

(f_1 + c_1*p_1)(f_2 + c_2*p_1) = T = (r_1 + k_1*p_1)

and

(g_1 + d_1*p_2)(g_2 + d_2*p_2) = T = (r_2 + k_2*p_2)

And I multiplied out and solved for k_1 and k_2 respectively and again pondered what if you GUESSED using f_1*f_2 = T mod p_1 and g_1*g_2 = T mod p_2, so you'd know the f's and the g's, and I realized that then you could just solve for the c's by using

(f_1 + c_1*p_1) = (g_1 + d_1*p_2)

and

(f_2 + c_2*p_1) = (g_2 + d_2*p_2)

and I realized you could solve for everything and reduce to a solution for d_1.

If it were an integer, you'd guessed right. If not, you'd try some more f's and g's, as you only have p_1 - 1 pairs of f's and p_2 - 1 pairs of g's.

And that's when I kind of freaked out which was a few minutes ago as that's stupid simple if it works. I mean STUPID simple.

If it's that freaking stupid simple then, oh, I don't know. Kind of still freaking out as if it's that stupid simple then it's all just too weird for me.

Think I'll go think about something else now for a while.

So I pondered some more.

Before too long I was writing out things along these lines:

(f_1 + c_1*p_1)(f_2 + c_2*p_1) = T = (r_1 + k_1*p_1)

and

(g_1 + d_1*p_2)(g_2 + d_2*p_2) = T = (r_2 + k_2*p_2)

And I multiplied out and solved for k_1 and k_2 respectively and again pondered what if you GUESSED using f_1*f_2 = T mod p_1 and g_1*g_2 = T mod p_2, so you'd know the f's and the g's, and I realized that then you could just solve for the c's by using

(f_1 + c_1*p_1) = (g_1 + d_1*p_2)

and

(f_2 + c_2*p_1) = (g_2 + d_2*p_2)

and I realized you could solve for everything and reduce to a solution for d_1.

If it were an integer, you'd guessed right. If not, you'd try some more f's and g's, as you only have p_1 - 1 pairs of f's and p_2 - 1 pairs of g's.

And that's when I kind of freaked out which was a few minutes ago as that's stupid simple if it works. I mean STUPID simple.

If it's that freaking stupid simple then, oh, I don't know. Kind of still freaking out as if it's that stupid simple then it's all just too weird for me.

Think I'll go think about something else now for a while.