### Wednesday, February 06, 2008

## JSH: Factoring and information theory

Surprisingly to me, wrapped up in common information about the factoring problem was a simple way to see that an easy solution had to exist, as can be seen with one of my new favorite examples:

I'm thinking of a number, and all I tell you is T = 9 mod 11 and T = 2 mod 13, what might the number be?

Well those choices constrain what T can be, and it's easy to solve, as you can use a little congruence result:

T = r_1 + j*n_1 mod n_1*n_2

where j = (r_2 - r_1)*n_1^{-1} mod n_2.

So with n_1 = 11, n_2 = 13, and r_1 = 9 and r_2 = 2, I have

T = 9 + 11j mod 143, where j = (2 - 9)*11^{-1} mod 13 = (-7)(6) mod 13 = 10 mod 13, so

T = 9 + 11(10) mod 143 = 119 mod 143

so the minimum size for the absolute value of that number is 119 and that is the number I was thinking of, so somehow the two primes together gave more information! And put limits on what the number could be.

So there is information wrapped up in the intersection of residues modulo primes.

Moving that to factoring is straightforward, once you go looking for a way to do so, though it does involve a use of logic:

You can get residues for factors of T modulo primes easily enough, as if you have f_1*f_2 = T mod p, then you have p-1 residues, where one is the one you want, but, for instance, with 119 mod 11 = 9, there isn't enough information in there to say WHICH of the 10 factorizations of 9 modulo 11 is the one you want as the math doesn't know that 119 is the target.

But what if you use two primes again?

And then use the following important result:

if f_1 = r_1 mod p_1 and f_2 = r_2 mod p_2, then

(f_1 - r_1)(f_2 - r_2) = 0 mod p_1*p_2

and you can multiply out and get

f_1*f_2 - r_1*f_2 - r_2*f_1 + r_1*r_2 = 0 mod p_1*p_2

and you get something crucial in its importance, as you have f_1*f_2, which is the factorization you want!!!

But you don't know your factors! So are you stuck? What can you do?

Well, why not guess? If you guess and just assume that you have the right f_1 and f_2 you can keep going with

T - r_1*f_2 - r_2*f_1 + r_1*r_2 = 0 mod p_1*p_2

which is ONLY TRUE if you guessed right!!!

So you have a bit of logic to the rescue. If you just guess at a solution, then you can make a substitution which is only true if you guessed right! And now you can proceed further, as you can solve for f_2 mod p_1*p_2:

f_2 = r_1^{-1}(T - r_2*f_1 + r_1*r_2) mod p_1*p_2

and then you can do another neat thing and just substitute back into

f_1*f_2 = T mod p_2

and solve for f_1 mod p_2 and get

f_1^2 - (T*r_2^{-1}+ r_1)*f_1 = -T*r_1*r_2^{-1} mod p_2

which is only true if you picked f_1 and f_2 correctly where remember f_1 is a factor from T mod p_1 while f_2 is a factor of T mod p_2 as the trick is to mix them up together so that the math is using information from the intersection of the primes, with a touch of logic for it all to make sense.

Here's an example of what happens if you get it wrong, where I'll use

1(9) = 119 mod 11, and take r_1 = 1, and 2(1) = 119 mod 13 and take 1 again for r_2 as it's easy.

Then I have

f_1^2 - (119(1)^{-1} + 1)*f_1 = -119(1)(1)^{-1} mod 13

so

f_1^2 - 3*f_1 + 2 = 0 mod 13

and

(f_1 - 2)(f_1 - 1) = 0 mod 13

where one answer works as you do get 2, but you have two answers where the other does not, so there is a contradiction as all answers must be true, and you get a contradiction with two answers where there should be only one as you did something wrong, and said f_1*f_2 = T, when

f_1 = 1 mod 11 and f_2 = 1 mod 13, and T = 119

so the math looked for that answer and didn't find it and kind of threw up its hands and gave you two answers, where there can be only one. I think it's kind of asking are you confused, did you mean the trivial factorization? So it hands you 2 and 1.

Oh, what happens if you use the correct 7,6 and 7,4?

Then r_1 = 7, and r_2 = 4. So

f_1^2 - (119(4)^{-1} + 7)*f_1 = -119(7)(4)^{-1} mod 13

which is

f_1^2 - f_1 = 3 mod 13

and multiplying through by 4, adding 1 to both sides and simplifying gives

(2f_1 - 1)^2 = 0 mod 13

and f_1 = 2^{-1} mod 13 = 7 mod 13.

So now the math knows what you want and gives you one answer: the right one.

A simple exercise in logic and information theory shows the way.

I'm thinking of a number, and all I tell you is T = 9 mod 11 and T = 2 mod 13, what might the number be?

Well those choices constrain what T can be, and it's easy to solve, as you can use a little congruence result:

T = r_1 + j*n_1 mod n_1*n_2

where j = (r_2 - r_1)*n_1^{-1} mod n_2.

So with n_1 = 11, n_2 = 13, and r_1 = 9 and r_2 = 2, I have

T = 9 + 11j mod 143, where j = (2 - 9)*11^{-1} mod 13 = (-7)(6) mod 13 = 10 mod 13, so

T = 9 + 11(10) mod 143 = 119 mod 143

so the minimum size for the absolute value of that number is 119 and that is the number I was thinking of, so somehow the two primes together gave more information! And put limits on what the number could be.

So there is information wrapped up in the intersection of residues modulo primes.

Moving that to factoring is straightforward, once you go looking for a way to do so, though it does involve a use of logic:

You can get residues for factors of T modulo primes easily enough, as if you have f_1*f_2 = T mod p, then you have p-1 residues, where one is the one you want, but, for instance, with 119 mod 11 = 9, there isn't enough information in there to say WHICH of the 10 factorizations of 9 modulo 11 is the one you want as the math doesn't know that 119 is the target.

But what if you use two primes again?

And then use the following important result:

if f_1 = r_1 mod p_1 and f_2 = r_2 mod p_2, then

(f_1 - r_1)(f_2 - r_2) = 0 mod p_1*p_2

and you can multiply out and get

f_1*f_2 - r_1*f_2 - r_2*f_1 + r_1*r_2 = 0 mod p_1*p_2

and you get something crucial in its importance, as you have f_1*f_2, which is the factorization you want!!!

But you don't know your factors! So are you stuck? What can you do?

Well, why not guess? If you guess and just assume that you have the right f_1 and f_2 you can keep going with

T - r_1*f_2 - r_2*f_1 + r_1*r_2 = 0 mod p_1*p_2

which is ONLY TRUE if you guessed right!!!

So you have a bit of logic to the rescue. If you just guess at a solution, then you can make a substitution which is only true if you guessed right! And now you can proceed further, as you can solve for f_2 mod p_1*p_2:

f_2 = r_1^{-1}(T - r_2*f_1 + r_1*r_2) mod p_1*p_2

and then you can do another neat thing and just substitute back into

f_1*f_2 = T mod p_2

and solve for f_1 mod p_2 and get

f_1^2 - (T*r_2^{-1}+ r_1)*f_1 = -T*r_1*r_2^{-1} mod p_2

which is only true if you picked f_1 and f_2 correctly where remember f_1 is a factor from T mod p_1 while f_2 is a factor of T mod p_2 as the trick is to mix them up together so that the math is using information from the intersection of the primes, with a touch of logic for it all to make sense.

Here's an example of what happens if you get it wrong, where I'll use

1(9) = 119 mod 11, and take r_1 = 1, and 2(1) = 119 mod 13 and take 1 again for r_2 as it's easy.

Then I have

f_1^2 - (119(1)^{-1} + 1)*f_1 = -119(1)(1)^{-1} mod 13

so

f_1^2 - 3*f_1 + 2 = 0 mod 13

and

(f_1 - 2)(f_1 - 1) = 0 mod 13

where one answer works as you do get 2, but you have two answers where the other does not, so there is a contradiction as all answers must be true, and you get a contradiction with two answers where there should be only one as you did something wrong, and said f_1*f_2 = T, when

f_1 = 1 mod 11 and f_2 = 1 mod 13, and T = 119

so the math looked for that answer and didn't find it and kind of threw up its hands and gave you two answers, where there can be only one. I think it's kind of asking are you confused, did you mean the trivial factorization? So it hands you 2 and 1.

Oh, what happens if you use the correct 7,6 and 7,4?

Then r_1 = 7, and r_2 = 4. So

f_1^2 - (119(4)^{-1} + 7)*f_1 = -119(7)(4)^{-1} mod 13

which is

f_1^2 - f_1 = 3 mod 13

and multiplying through by 4, adding 1 to both sides and simplifying gives

(2f_1 - 1)^2 = 0 mod 13

and f_1 = 2^{-1} mod 13 = 7 mod 13.

So now the math knows what you want and gives you one answer: the right one.

A simple exercise in logic and information theory shows the way.