Contents xi 2.2 Inverses and Greatest Common Divisors 75 Solutions to Equations and Inverses mod n 75 Inverses mod n 76 Converting Modular Equations to Normal Equations 79 Greatest Common Divisors 80 Euclid's Division Theorem 81 Euclid's GCD Algorithm 84 Extended GCD Algorithm 85 Computing Inverses 88 Important Concepts,Formulas,and Theorems 89 Problems 90 2.3 The RSA Cryptosystem 93 Exponentiation mod n 93 The Rules of Exponents 93 Fermat's Little Theorem 96 The RSA Cryptosystem 97 The Chinese Remainder Theorem 101 Important Concepts,Formulas,and Theorems 102 Problems 104 2.4 Details of the RSA Cryptosystem 106 Practical Aspects of Exponentiation mod n 106 How Long Does It Take to Use the RSA Algorithm? 109 How Hard Is Factoring? 110 Finding Large Primes 110 Important Concepts,Formulas,and Theorems 113 Problems 114 CHAPTER 3 Reflections on Logic and Proof 117 3.1 Equivalence and Implication 117 Equivalence of Statements 117 Truth Tables 120 DeMorgan's Laws 123Contents xi 2.2 Inverses and Greatest Common Divisors 75 Solutions to Equations and Inverses mod n 75 Inverses mod n 76 Converting Modular Equations to Normal Equations 79 Greatest Common Divisors 80 Euclid’s Division Theorem 81 Euclid’s GCD Algorithm 84 Extended GCD Algorithm 85 Computing Inverses 88 Important Concepts, Formulas, and Theorems 89 Problems 90 2.3 The RSA Cryptosystem 93 Exponentiation mod n 93 The Rules of Exponents 93 Fermat’s Little Theorem 96 The RSA Cryptosystem 97 The Chinese Remainder Theorem 101 Important Concepts, Formulas, and Theorems 102 Problems 104 2.4 Details of the RSA Cryptosystem 106 Practical Aspects of Exponentiation mod n 106 How Long Does It Take to Use the RSA Algorithm? 109 How Hard Is Factoring? 110 Finding Large Primes 110 Important Concepts, Formulas, and Theorems 113 Problems 114 CHAPTER 3 Reflections on Logic and Proof 117 3.1 Equivalence and Implication 117 Equivalence of Statements 117 Truth Tables 120 DeMorgan’s Laws 123