Discrete Mathematics: Elementary and Beyond

14.5 Latin Squares 231 the same as the row and column sums. From which orthogonal Latin squares can we make perfect magic square ...

232 14. Finite Geometries, Codes,Latin Squares,and Other Pretty Creatures thenthese two Latin squares will be orthogonal!(This i ...

14.6 Codes 233 How can we cope with these errors and recover the original message? Of course, a lot depends on the circumstances ...

234 14. Finite Geometries, Codes,Latin Squares,and Other Pretty Creatures (since then any error would result in another possible ...

14.6 Codes 235 Second, suppose that the two planes intersect in two points. For example, the “black” plane and the “bottom” plan ...

236 14. Finite Geometries, Codes,Latin Squares,and Other Pretty Creatures 111 0 0 0 0 0 0 0 1 1 1 1 FIGURE 14.11. Three errors a ...

14.6 Codes 237 Review Exercises 14.6.3Verify that the Tictactoe plane is the same as the affine plane over the 3-element field. ...

238 14. Finite Geometries, Codes,Latin Squares,and Other Pretty Creatures 14.6.11 Describe the code you get from the projective ...

15 A Glimpse of Complexity and Cryptography 15.1 A Connecticut Class in King Arthur’s Court......... In the court of King Arthur ...

240 15. A Glimpse of Complexity and Cryptography these knights?” and when all said “No!” Merlin said, “Oh King, how can you comm ...

15.1 A Connecticut Class in King Arthur’s Court 241 you really want to know, NP is the abbreviation ofNondeterministic Poly- nom ...

242 15. A Glimpse of Complexity and Cryptography applied in one of the most important areas of theoretical computer science, nam ...

15.2 Classical Cryptography 243 First, he has to convert it to 0’s and 1’s. It is not clear that medieval kings had the knowledg ...

244 15. A Glimpse of Complexity and Cryptography 15.2.2At one time, Arthur made the mistake of using the one-time pad shifted: T ...

15.3 How to Save the Last Move in Chess 245 Next, Alice extends the four digits describing her move to a prime number p= 1163... ...

246 15. A Glimpse of Complexity and Cryptography 15.3.2Alice modifies her suggestion as follows: instead of the random 0-1 se- q ...

15.6 Public Key Cryptography 247 11630000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000 ...

248 15. A Glimpse of Complexity and Cryptography e, herpublic key(the numberspandqshe may even forget; they will not be needed t ...

15.6 Public Key Cryptography 249 How to do all this computation.We already discussed how to find primes, and Alice can follow th ...

250 15. A Glimpse of Complexity and Cryptography You know the remainderr(this is the intercepted message). You also know Alice’s ...