Part II. COMPUTER ALGEBRA

Table of Contents

5. Algebra
5.1. 5.1 Fields, vector spaces, and polynomials
5.1.1. 5.1.1 Ring theoretic concepts
5.1.2. 5.1.2 Polynomials
5.2. 5.2 Finite fields
5.3. 5.3 Factoring polynomials over finite fields
5.3.1. 5.3.1 Square-free factorisation
5.3.2. 5.3.2 Distinct degree factorisation
5.3.3. 5.3.3 The Cantor-Zassenhaus algorithm
5.3.4. 5.3.4 Berlekamp's algorithm
5.4. 5.4 Lattice reduction
5.4.1. 5.4.1 Lattices
5.4.2. 5.4.2 Short lattice vectors
5.4.3. 5.4.3 Gauss' algorithm for two-dimensional lattices
5.4.4. 5.4.4 A Gram-Schmidt orthogonalisation and weak reduction
5.4.5. 5.4.5 Lovász-reduction
5.4.6. 5.4.6 Properties of reduced bases
5.5. 5.5 Factoring polynomials in
5.5.1. 5.5.1 Preparations
5.5.2. 5.5.2 The Berlekamp-Zassenhaus algorithm
5.5.3. 5.5.3 The LLL algorithm
6. Computer Algebra
6.1. 6.1 Data representation
6.2. 6.2 Common roots of polynomials
6.2.1. 6.2.1 Classical and extended Euclidean algorithm
6.2.2. 6.2.2 Primitive Euclidean algorithm
6.2.3. 6.2.3 The resultant
6.2.4. 6.2.4 Modular greatest common divisor
6.3. 6.3 Gröbner basis
6.3.1. 6.3.1 Monomial order
6.3.2. 6.3.2 Multivariate division with remainder
6.3.3. 6.3.3 Monomial ideals and Hilbert's basis theorem
6.3.4. 6.3.4 Buchberger's algorithm
6.3.5. 6.3.5 Reduced Gröbner basis
6.3.6. 6.3.6 The complexity of computing Gröbner bases
6.4. 6.4 Symbolic integration
6.4.1. 6.4.1 Integration of rational functions
6.4.2. 6.4.2 The Risch integration algorithm
6.5. 6.5 Theory and practice
6.5.1. 6.5.1 Other symbolic algorithms
6.5.2. 6.5.2 An overview of computer algebra systems
7. Cryptology
7.1. 7.1 Foundations
7.1.1. 7.1.1 Cryptography
7.1.2. 7.1.2 Cryptanalysis
7.1.3. 7.1.3 Algebra, number theory, and graph theory
7.2. 7.2 Diffie and Hellman's secret-key agreement protocol
7.3. 7.3 RSA and factoring
7.3.1. 7.3.1 RSA
7.3.2. 7.3.2 Digital RSA signatures
7.3.3. 7.3.3 Security of RSA
7.4. 7.4 The protocols of Rivest, Rabi, and Sherman
7.5. 7.5 Interactive proof systems and zero-knowledge
7.5.1. 7.5.1 Interactive proof systems and Arthur-Merlin games
7.5.2. 7.5.2 Zero-knowledge protocol for graph isomorphism
8. Complexity Theory
8.1. 8.1 Foundations
8.2. 8.2 NP-completeness
8.3. 8.3 Algorithms for the satisfiability problem
8.3.1. 8.3.1 A deterministic algorithm
8.3.2. 8.3.2 A randomised algorithm
8.4. 8.4 Graph isomorphism and lowness
8.4.1. 8.4.1 Reducibilities and complexity hierarchies
8.4.2. 8.4.2 Graph isomorphism is in the low hierarchy
8.4.3. 8.4.3 Graph isomorphism is in SPP