Algebra for Applications: Cryptography, Secret Sharing, Error-Correcting, Fingerprinting, Compression (Springer Undergraduate Mathematics Series)

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