Algebra for Applications

Description

Modern societies are awash with data that needs to be manipulated in many different ways: encrypted, compressed, shared between users in a prescribed manner, protected from unauthorised access, and transmitted over unreliable channels. All of these operations are based on algebra and number theory and can only be properly understood with a good knowledge of these fields. This textbook provides the mathematical tools and applies them to study key aspects of data transmission such as encryption and compression. Designed for an undergraduate lecture course, this textbook provides all of the background in arithmetic, polynomials, groups, fields, and elliptic curves that is required to understand real-life applications such as cryptography, secret sharing, error-correcting, fingerprinting, and compression of information. It explains in detail how these applications really work. The book uses the free GAP computational package, allowing the reader to develop intuition about computationally hard problems and giving insights into how computational complexity can be used to protect the integrity of data. The first undergraduate textbook to cover such a wide range of applications, including some recent developments, this second edition has been thoroughly revised with the addition of new topics and exercises. Based on a one semester lecture course given to third year undergraduates, it is primarily intended for use as a textbook, while numerous worked examples and solved exercises also make it suitable for self-study. Preface to the Second Edition Preface to the First Edition Contents 1 Integers 1.1 Natural Numbers 1.1.1 Basic Principles 1.1.2 Divisibility and Primes 1.1.3 Factoring Integers. The Sieve of Eratosthenes 1.2 Euclidean Algorithm 1.2.1 Divisors and Multiples 1.2.2 Greatest Common Divisor and Least Common Multiple 1.2.3 Extended Euclidean Algorithm. Chinese Remainder Theorem 1.3 Fermat's Little Theorem and Its Generalisations 1.3.1 Congruences. Fermat's Little Theorem 1.3.2 Euler's φ-Function. Euler's Theorem 1.4 The Ring of Integers Modulo n. The Field mathbbZp 1.5 Representation of Numbers 2 Cryptology 2.1 Classical Secret-Key Cryptology 2.1.1 The One-Time Pad 2.1.2 An Affine Cryptosystem 2.1.3 Hill's Cryptosystem 2.2 Modern Public-Key Cryptology 2.2.1 One-Way Functions and Trapdoor Functions 2.3 Computational Complexity 2.3.1 Orders of Magnitude 2.3.2 The Time Complexity of Several Number-Theoretic Algorithms 2.4 The RSA Public-Key Cryptosystem 2.4.1 How Does the RSA System Work? 2.4.2 Why Does the RSA System Work? 2.4.3 Pseudoprimality Tests 2.5 Applications of Cryptology 3 Groups 3.1 Permutations 3.1.1 Composition of Mappings. The Group of Permutations of Degree n 3.1.2 Block Permutation Cipher 3.1.3 Cycles and Cycle Decomposition 3.1.4 Orders of Permutations 3.1.5 Analysis of Repeated Actions 3.1.6 Transpositions. Even and Odd 3.1.7 Puzzle 15 3.2 General Groups 3.2.1 Definition of a Group. Examples 3.2.2 Powers, Multiples and Orders. Cyclic Groups 3.2.3 Isomorphism 3.2.4 Subgroups 3.3 The Abelian Group of an Elliptic Curve 3.3.1 Elliptic Curves. The Group of Points of an Elliptic Curve 3.3.2 Quadratic Residues and Hasse's Theorem 3.3.3 Calculating Large Multiples Efficiently 3.4 Applications to Cryptography 3.4.1 Encoding Plaintext 3.4.2 Additive Diffie–Hellman Key Exchange and the ElGamal Cryptosystem 4 Fields 4.1 Introduction to Fields 4.1.1 Examples and Elementary Properties of Fields 4.1.2 Vector Spaces 4.1.3 Cardinality of a Finite Field 4.2 The Multiplicative Group of a Finite Field is Cyclic 4.2.1 Lemmas on Orders of Elements 4.2.2 Proof of the Main Theorem 4.2.3 Proof of Euler's Criterion 4.2.4 Discrete Logarithms 4.3 Elgamal Cryptosystem Revisited 5 Polynomials 5.1 The Ring of Polynomials 5.1.1 Introduction to Polynomials 5.1.2 Lagrange's Interpolation 5.1.3 Factoring Polynomials 5.1.4 Greatest Common Divisor and Least Common Multiple 5.2 Finite Fields 5.2.1 Polynomials Modulo m(x) 5.2.2 Minimal Annihilating Polynomials 5.3 Permutation Polynomials and Applications 5.3.1 Permutation Polynomials 5.3.2 Cryptosystem Based on a Permutation Polynomial 6 Secret Sharing 6.1 Introduction to Secret Sharing 6.1.1 Access Structure 6.1.2 Shamir's Threshold Access Scheme 6.2 A General Theory of Secret Sharing Schemes 6.2.1 General Properties of Secret Sharing Schemes 6.2.2 Linear Secret Sharing Schemes 6.2.3 Ideal and Non-ideal Secret Sharing Schemes 6.3 Applications of Secret Sharing 7 Error-Correcting Codes 7.1 Binary Error-Correcting Codes 7.1.1 The Hamming Weight and the Hamming Distance 7.1.2 Encoding and Decoding. Simple Examples 7.1.3 Minimum Distance, Minimum Weight. Linear Codes 7.1.4 Matrix Encoding Technique 7.1.5 Parity Check Matrix 7.1.6 The Hamming Codes 7.1.7 Polynomial Codes 7.1.8 Bose–Chaudhuri–Hocquenghem (BCH) Codes 7.2 Non-binary Error-Correcting Codes 7.2.1 The Basics of Non-binary Codes 7.2.2 Reed–Solomon (RS) Codes 7.3 Fingerprinting Codes 7.3.1 The Basics of Fingerprinting 7.3.2 Frameproof Codes 7.3.3 Codes with the Identifiable Parent Property 8 Compression 8.1 Encoding a Known Source 8.1.1 Motivating Example 8.1.2 Prefix Codes 8.1.3 Huffman's Optimal Code 8.2 Encoding an Unknown Source 8.2.1 Compressing Binary Sequences (Files) 8.2.2 Information and Information Relative to a Partition 8.2.3 Fitingof's Compression Code. Encoding 8.2.4 Fitingof's Compression Code. Fast Decoding 8.3 Information and Uncertainty 9 Appendix A: GAP 9.1 Computing with GAP 9.1.1 Starting with GAP 9.1.2 The GAP Interface 9.1.3 Programming in GAP: Variables, Lists, Sets and Loops 9.2 Number Theory 9.2.1 Basic Number-Theoretic Algorithms 9.2.2 Arithmetic Modulo m 9.2.3 Digitising Messages 9.3 Matrix Algebra 9.4 Algebra 9.4.1 Permutations 9.4.2 Elliptic Curves 9.4.3 Finite Fields 9.4.4 Polynomials 10 Appendix B: Miscellania 10.1 Linear Dependency Relationship Algorithm 10.2 The Vandermonde Determinant 10.3 Stirling's Formula 11 Solutions to Exercises 11.1 Solutions to Exercises of Chap. 1 11.2 Solutions to Exercises of Chap. 2 11.3 Solutions to Exercises of Chap. 3 11.4 Solutions to Exercises of Chap. 4 11.5 Solutions to Exercises of Chap. 5 11.6 Solutions to Exercises of Chap. 6 11.7 Solutions to Exercises of Chap.7摥映數爠eflinkchap777 11.8 Solutions to Exercises of Chap. 8 Literature Index