Mathematics for Computer Science
8.9. Multiplicative Inverses and Cancelling 273 8.9.4 Breaking Turing’s Code (Version 2.0) The Germans didn’t bother to encrypt ...
Chapter 8 Number Theory274 However, Turing remained a puzzle to the very end. His mother was a devout woman who considered suici ...
8.10. Euler’s Theorem 275 The Riemann Hypothesis The formula for the sum of an infinite geometric series says: 1 CxCx^2 Cx^3 C ...
Chapter 8 Number Theory276 Things get simpler when we rephrase Euler’s Theorem in terms ofZn. Definition 8.10.2.LetZnbe the int ...
8.10. Euler’s Theorem 277 Proof. (of Euler’s Theorem 8.10.3 forZn) Let PWWDk 1 k 2 k.n/.Zn/ be the product inZnof all the n ...
Chapter 8 Number Theory278 8.10.1 Computing Euler’sFunction RSA works using arithmetic modulo the product of two large primes, ...
8.11. RSA Public Key Encryption 279 Corollary 8.10.11.For any numbern, ifp 1 ,p 2 ,... ,pj are the (distinct) prime factors ofn, ...
Chapter 8 Number Theory280 The RSA Cryptosystem AReceiverwho wants to be able to receive secret numerical messages creates a pri ...
8.12. What has SAT got to do with it? 281 Why is RSA thought to be secure? It would be easy to figure out the private keydif you ...
Chapter 8 Number Theory282 Let’s begin with the observation from Section 3.2 that a digital circuit can be described by a bunch ...
8.13. References 283 Problems for Section 8.1 Practice Problems Problem 8.1. Prove that a linear combination of linear combinati ...
Chapter 8 Number Theory284 (a)What is gcd.x;y/? (b)What is lcm.x;y/? (lcm isleast common multiple.) Problem 8.5. Use the Well Or ...
8.13. References 285 Problem 8.9. (a)Use the Pulverizer to find gcd.84;108/ (b)Find integersx,ywith 0 y < 84such that x 84 ...
Chapter 8 Number Theory286 Homework Problems Problem 8.12. Here is a game you can analyze with number theory and always beat me. ...
8.13. References 287 Problem 8.14. Prove that the smallest positive integersabfor which, starting in state.a;b/, the Euclidean ...
Chapter 8 Number Theory288 statesWWDN^3 start stateWWD.a;b;1/ transitionsWWDif min.x;y/ > 0;then.x;y;e/! .x=2;y=2;2e/ (if 2 j ...
8.13. References 289 To see how to update the coefficients when at least one ofaandbis odd and uaCvbis even, show that eitheruan ...
Chapter 8 Number Theory290 Pour the big bucket into the little bucket. You should have two cases defined in terms of the state. ...
8.13. References 291 Problems for Section 8.3 Homework Problems Problem 8.22. TBA: Chebyshvev lower bound in prime density, base ...
Chapter 8 Number Theory292 On the other hand, the number 3 is still a “prime” even inZŒ p 5ç. More pre- cisely, a numberp 2 ZŒ p ...
«
10
11
12
13
14
15
16
17
18
19
»
Free download pdf