## Introduction to Cryptology: T10 Remarks

 Check the errata list before you do the problems. I won't give the right answers here. If you want to know the right answers, come to see me.
• 13.3.03, 13.3.06. You can follow the recipe in Section 13.3. But I personally feel that the way the book uses Sun Ze's theorem is not crisp. For these two problems, which have only two moduli, it's okay. But if there are more than 2, the method given by the book is cubersome. Instead of using the, quote, "goofy", formula, I'd use the theorem in Page 218. To show how it can be done, I use the same example in Section 13.3.  13 17 29 M_i 17x29=493 13x29=377 13x17=221 T_i 12 6 21 f^{-1}(r1,r2,r3)=5916r1+2262r2+4641r3 Roots +/-5 +/-4 +/-12
f^{-1} is the inverse of f defined in Sun Ze's theorem. We can then substitute the roots to f^{-1} and we'll get all 8 roots.
• 13.4.01 Only one of you actually used Hensel's lemma and he got a 20% bonus for that. What Hensel's lemma gives us is starting with a low power of p, e.g., p^1, we can proceed to find the root of a polynomial modula a higher power of p, e.g., p^5. For this problem, the polynomial is f(x)=x^2-2.
• 13.4.06 You could discuss why the polynomail doesn't have a root in Z/2 using even-odd-ness analysis. But that doesn't answer the question that why the quadratic formula fails. Some of you said it's because the root is complex: there is \sqrt(-3) in it. But \sqrt(-3) is well defined in the field of Z/2. \sqrt(-3) = 1 (mod 2). So the real reason is ...
• 13.6.01 Very few of you got this totally right. Common mistakes: gcd(6,15)=gcd(5,30)=1; gcd(1,30)!=1;
• 13.8.* Don't forget to use the fast exponential algorithm.