Mathematics for Computer Science

8.2. The Greatest Common Divisor 193 machine and then verified using an invariant that is an extension of the one used for Eucli ...

Chapter 8 Number Theory194 At the end of this process, we must have have emptied the 26-gallon jug exactly t^0 times. Here’s why ...

8.3. The Fundamental Theorem of Arithmetic 195 Pour all the water in the smaller jug into the larger jug. If at any time the la ...

Chapter 8 Number Theory196 The Prime Number Theorem Let.x/denote the number of primes less than or equal tox. For example, .10 ...

8.4. Alan Turing 197 Proof. One case is if gcd.a;p/Dp. Then the claim holds, becauseais a multiple ofp. Otherwise, gcd.a;p/¤p. I ...

Chapter 8 Number Theory198 Figure 8.1 Alan Turing At age 24, Turing wrote a paper entitledOn Computable Numbers, with an Ap- pli ...

8.4. Alan Turing 199 signature schemes, cryptographic hash functions, and electronic payment systems. Furthermore, military fund ...

Chapter 8 Number Theory200 There are a couple of questions that one might naturally ask about Turing’s code. How can the sender ...

8.5. Modular Arithmetic 201 The greatest common divisor of the two encrypted messages,m 1 andm 2 , is the secret keyk. And, as ...

Chapter 8 Number Theory202 So we can also see that 29 15 .mod7/ because rem.29;7/D 1 Drem.15;7/: Notice that even though “(mod ...

8.5. Modular Arithmetic 203 Proof. We have thatndivides.ba/which is equal to.bCc/.aCc/, so aCcbCc .modn/: Also,ndivides.dc/, so ...

Chapter 8 Number Theory204 Governments are always tight-lipped about cryptography, but the half-century of official silence abou ...

8.6. Arithmetic with a Prime Modulus 205 The sole exception is that 0 does not have an inverse. On the other hand, over the inte ...

Chapter 8 Number Theory206 8.6.2 Cancellation Another sense in which real numbers are nice is that one can cancel multiplicative ...

8.6. Arithmetic with a Prime Modulus 207 For example, supposepD 5 andkD 3. Then the sequence: rem„ ..1ƒ‚
3/;5/... D 3 ; rem„ ..2 ...

Chapter 8 Number Theory208 where the’s are modulo 17. Therefore, 615 3 .mod17/. Sure enough, 3 is the multiplicative inverse o ...

8.7. Arithmetic with an Arbitrary Modulus 209 arrested him—that is, they arrested Alan Turing—because homosexuality was a Britis ...

Chapter 8 Number Theory210 The Riemann Hypothesis The formula for the sum of an infinite geometric series says: 1 CxCx^2 Cx^3 C
...

8.7. Arithmetic with an Arbitrary Modulus 211 have, but rather modulo the product oftwolarge primes. Thus, we’ll need to know a ...

Chapter 8 Number Theory212 is a permutation of the sequence: k 1 ; k 2 ;:::; kr: Proof. We will show that the remainders in the ...