Introduction to Cryptology: T5 Remarks

• A.3.07. There are many ways to prove this one. You can use induction or the identities that \sum_{i=1}^{N}i=N(N+1)/2 and \sum_{i=1}^{N}i^2=N(N+1)(2N+1)/6. But a more elegent proof is to use Cauchy-Schwartz over the two vectors (1,2,...n) and you_think_what_it_should_be. You can look at this problem from another perspective. Noticing that f(x)=x^2 is a convex function, we can use Jensen's inequality to reach the conclusion instantly. It's a good time to recall what you learned in Calculus why f(x) is convex.
• A.4.01. The matrix is rank-deficient. You know this because either 1) the determinant is 0 or 2) the two rows (columns) are linear dependant.
• A.4.05. Don't forget to prove your conclusion, using induction.
• 7.1.03. How are you sure you found all factors of 90? You can't just say "I tried every possible numbers" or "I wrote a program that ...". For former, you basically say "It's right because I know it's right"; for latter, you'll have to prove your program does what it's intended to do, which is not an easy thing. Either way, you have to have a rigorous mathematical argument.
• 7.1.14, 7.1.17, 7,3.09. Euclidean algorithm.
• 7.1.19. Read Section 7.2. See how \phi(n) can be computed.
• 7.1.20. This one's not easy. You can think along the same line as how \phi(n) is computed: use inclusion-exclusion principle (Page 115). The answer is \zeta(2), where \zeta(x) is the famous Riemann function.
• 7.2.08. Think about when x^n+1 can be factored.