Mathematics for Computer Science
8.2. The Greatest Common Divisor 253 Pour all the water in the 21-gallon jug into the 26-gallon jug. If at any time the 26-gall ...
Chapter 8 Number Theory254 Fill the smaller jug. Pour all the water in the smaller jug into the larger jug. If at any time the ...
8.3. Prime Mysteries 255 The best algorithm known is the “number field sieve,” which runs in time proportional to: e1:9.lnn/ 1=3 ...
Chapter 8 Number Theory256 apparently made in 1791 at age 15. (You have to feel sorry for all the otherwise “great” mathematicia ...
8.4. The Fundamental Theorem of Arithmetic 257 8.4 The Fundamental Theorem of Arithmetic There is an important fact about primes ...
Chapter 8 Number Theory258 8.4.1 Proving Unique Factorization The Fundamental Theorem is not hard to prove, but we’ll need a cou ...
8.5. Alan Turing 259 Figure 8.1 Alan Turing Sincen=q 1 < n, this can’t be true, so we conclude thatp 1 < q 1. Since thepi’ ...
Chapter 8 Number Theory260 before any electronic computer actually existed. The word “Entscheidungsproblem” in the title refers ...
8.5. Alan Turing 261 Beforehand The sender and receiver agree on asecret key, which is a large primek. EncryptionThe sender encr ...
Chapter 8 Number Theory262 Primality Testing It’s easy to see that an integernis prime iff it is not divisible by any number fro ...
8.6. Modular Arithmetic 263 8.5.2 Breaking Turing’s Code (Version 1.0) Let’s consider what happens when the sender transmits ase ...
Chapter 8 Number Theory264 wherer 1 ;r 22 Œ0::n/. Subtracting the second equation from the first gives: abD.q 1 q 2 /nC.r 1 r 2 ...
8.7. Remainder Arithmetic 265 according to whether their remainders on division by 3 are 0, 1, or 2. The upshot is that when ari ...
Chapter 8 Number Theory266 General Principle of Remainder Arithmetic To find the remainder on division bynof the result of a ser ...
8.7. Remainder Arithmetic 267 What a win! Powers of 6 are even easier because rem.6^2 ; 36/D 0 , so 0’s keep repeating after the ...
Chapter 8 Number Theory268 The set of integers in the rangeŒ0::n/together with the operationsCnandnis referred to asZn, thering ...
8.8. Turing’s Code (Version 2.0) 269 plies brought across the north Atlantic from the United States by convoys of ships. These c ...
Chapter 8 Number Theory270 is theremainderwhenmkis divided byn. So dividingbmbykmight not even give us an integer! This decoding ...
8.9. Multiplicative Inverses and Cancelling 271 8.9.1 Relative Primality Integers that have no prime factor in common are called ...
Chapter 8 Number Theory272 8.9.2 Cancellation Another sense in which real numbers are nice is that it’s ok to cancel common fact ...
«
9
10
11
12
13
14
15
16
17
18
»
Free download pdf
