Contents
1.5.3Chinese remainder theorem
1.6Polynomials and formal power series
2.1Symmetric encryption methods
2.4Frequency analysis and coincidence index
2.5Perfect security and the Vernam one-time pad
2.6Asymmetric encryption methods
2.9Diffie–Hellman key exchange
2.11Cryptographic hash functions
2.15Shamir’s attack on the Merkle–Hellman cryptosystem
3.1Runtime analysis of algorithms
3.4Probabilistic recognition of primes
3.4.1Fermat primality test and Carmichael numbers
3.4.2Solovay–Strassen primality test
3.4.3Miller–Rabin primality test
3.4.4Applications of the Miller–Rabin scheme
3.4.5Miller–Rabin versus Solovay–Strassen
3.5Extracting roots in finite fields
3.6.1Pollard’s p − 1 algorithm
3.6.2Pollard’s rho algorithm for factorization
3.7.1Shanks’ baby-step giant-step algorithm
3.7.2Pollard’s rho algorithm for the discrete logarithm
3.7.3Pohlig–Hellman algorithm for group order reduction
3.8Multiplication and division
3.11Schönhage–Strassen integer multiplication
4Polynomial time primality test
4.3Growth of the least common multiple
4.4Of small numbers and large orders
4.5Agrawal–Kayal–Saxena primality test
5.1.2Polynomials over elliptic curves
5.2Applications of elliptic curves
5.2.1Diffie–Hellman key exchange with elliptic curves
5.2.3Factorization using elliptic curves
5.2.4Goldwasser–Kilian primality certificates
5.3Endomorphisms of elliptic curves
6.1Commutation, transposition and conjugacy
6.2Fine and Wilf’s periodicity lemma
7.7Automata over infinite words
7.7.1Deterministic Büchi automata
7.7.4Recognizability of omega-regular languages
7.7.5Monadic second-order logic over infinite words
7.9Solutions of linear Diophantine systems
8.1Classical algorithmic problems
8.4.1Termination and confluence
8.5Solving the word problem in finitely presented monoids
8.6Free partially commutative monoids and groups
8.8Amalgamated products and HNN extensions
8.9Rational sets and Benois’ theorem
8.11The automorphism group of free groups