xii Contents Words to Numbers 371 Cryptography and the Law 373 Recap 373 Exercises 373 44 Public Key Cryptography ll:Rabin's Method 373 Square Roots Modulo n 374 The Encryption and Decryption Procedures 378 Recap 379 Exercises 379 45 Public Key Cryptography Ill:RSA 380 The RSA Encryption and Decryption Functions 381 Security 383 Recap 384 Exercises 384 Chapter 8 Self Test 385 9 Graphs 389 46 Fundamentals of Graph Theory 389 Map Coloring 389 Three Utilities 391 Seven Bridges 391 What Is a Graph? 392 Adjacency 393 A Matter of Degree 394 Further Notation and Vocabulary 396 Recap 397 Exercises 397 47 Subgraphs 399 Induced and Spanning Subgraphs 400 Cliques and Independent Sets 402 Complements 403 Recap 404 Exercises 404 48 Connection 406 Walks 406 Paths 407 Disconnection 410 Recap 411 Exercises 411 49 Trees 413 Cycles 413 Forests and Trees 413xii Contents Words to Numbers 371 Cryptography and the Law 373 Recap 373 Exercises 373 44 Public Key Cryptography II: Rabin's Method 373 Square Roots Modulo n 374 The Encryption and Decryption Procedures 378 Recap 379 Exercises 379 45 Public Key Cryptography Ill: RSA 380 The RSA Encryption and Decryption Functions 381 Security 383 Recap 384 Exercises 384 Chapter 8 Self Test 385 9 Graphs 389 46 Fundamentals of Graph Theory 389 Map Coloring 389 Three Utilities 391 Seven Bridges 391 What Is a Graph? 392 Adjacency 393 A Matter of Degree 394 Further Notation and Vocabulary 396 Recap 397 Exercises 397 47 Subgraphs 399 Induced and Spanning Subgraphs 400 Cliques and Independent Sets 402 Complements 403 Recap 404 Exercises 404 48 Connection 406 Walks 406 Paths 407 Disconnection 410 Recap 411 Exercises 411 49 Trees 413 Cycles 413 Forests and Trees 413