Discrete Algebraic Methods : Arithmetic, Cryptography, Automata and Groups.

Intro -- Contents -- Preface -- 1. Algebraic structures -- 1.1 Groups -- 1.2 Regular polygons -- 1.3 Symmetric groups -- 1.4 Rings -- 1.5 Modular arithmetic -- 1.5.1 Euclidean algorithm -- 1.5.2 Ideals in the integers -- 1.5.3 Chinese remainder theorem -- 1.5.4 Euler's totient function -- 1.6 Polynomials and formal power series -- 1.7 Hilbert's basis theorem -- 1.8 Fields -- 1.9 Finite fields -- 1.10 Units modulo n -- 1.11 Quadratic reciprocity -- Exercises -- Summary -- 2. Cryptography -- 2.1 Symmetric encryption methods -- 2.2 Monoalphabetic cipher -- 2.3 Polyalphabetic cipher -- 2.4 Frequency analysis and coincidence index -- 2.5 Perfect security and the Vernam one-time pad -- 2.6 Asymmetric encryption methods -- 2.7 RSA cryptosystem -- 2.8 Rabin cryptosystem -- 2.9 Diffie-Hellman key exchange -- 2.10 ElGamal cryptosystem -- 2.11 Cryptographic hash functions -- 2.12 Digital signatures -- 2.13 Secret sharing -- 2.14 Digital commitment -- 2.15 Shamir's attack on the Merkle-Hellman cryptosystem -- Exercises -- Summary -- 3. Number theoretic algorithms -- 3.1 Runtime analysis of algorithms -- 3.2 Fast exponentiation -- 3.3 Binary GCD -- 3.4 Probabilistic recognition of primes -- 3.4.1 Fermat primality test and Carmichael numbers -- 3.4.2 Solovay-Strassen primality test -- 3.4.3 Miller-Rabin primality test -- 3.4.4 Applications of the Miller-Rabin scheme -- 3.4.5 Miller-Rabin versus Solovay-Strassen -- 3.5 Extracting roots in finite fields -- 3.5.1 Tonelli's algorithm -- 3.5.2 Cipolla's algorithm -- 3.6 Integer factorization -- 3.6.1 Pollard's p - 1 algorithm -- 3.6.2 Pollard's rho algorithm for factorization -- 3.6.3 Quadratic sieve -- 3.7 Discrete logarithm -- 3.7.1 Shanks' baby-step giant-step algorithm -- 3.7.2 Pollard's rho algorithm for the discrete logarithm -- 3.7.3 Pohlig-Hellman algorithm for group order reduction -- 3.7.4 Index calculus.

3.8 Multiplication and division -- 3.9 Discrete fourier transform -- 3.10 Primitive roots of unity -- 3.11 Schönhage-Strassen integer multiplication -- Exercises -- Summary -- 4. Polynomial time primality test -- 4.1 Basic idea -- 4.2 Combinatorial tools -- 4.3 Growth of the least common multiple -- 4.4 Of small numbers and large orders -- 4.5 Agrawal-Kayal-Saxena primality test -- Summary -- 5. Elliptic curves -- 5.1 Group law -- 5.1.1 Lines -- 5.1.2 Polynomials over elliptic curves -- 5.1.3 Divisors -- 5.1.4 Picard group -- 5.2 Applications of elliptic curves -- 5.2.1 Diffie-Hellman key exchange with elliptic curves -- 5.2.2 Pseudocurves -- 5.2.3 Factorization using elliptic curves -- 5.2.4 Goldwasser-Kilian primality certificates -- 5.3 Endomorphisms of elliptic curves -- Exercises -- Summary -- 6. Combinatorics on words -- 6.1 Commutation, transposition and conjugacy -- 6.2 Fine and Wilf's periodicity lemma -- 6.3 Kruskal's tree theorem -- Exercises -- Summary -- 7. Automata -- 7.1 Recognizable sets -- 7.2 Rational sets -- 7.3 Regular languages -- 7.4 Star-free languages -- 7.5 Krohn-Rhodes theorem -- 7.6 Green's relations -- 7.7 Automata over infinite words -- 7.7.1 Deterministic Büchi automata -- 7.7.2 Union and intersection -- 7.7.3 Omega-rational languages -- 7.7.4 Recognizability of omega-regular languages -- 7.7.5 Monadic second-order logic over infinite words -- 7.8 Presburger arithmetic -- 7.9 Solutions of linear Diophantine systems -- Exercises -- Summary -- 8. Discrete infinite groups -- 8.1 Classical algorithmic problems -- 8.2 Residually finite monoids -- 8.3 Presentations -- 8.4 Rewriting systems -- 8.4.1 Termination and confluence -- 8.4.2 Semi-Thue systems -- 8.5 Solving the word problem in finitely presented monoids -- 8.6 Free partially commutative monoids and groups -- 8.7 Semidirect products.

8.8 Amalgamated products and HNN extensions -- 8.9 Rational sets and Benois' theorem -- 8.10 Free groups -- 8.11 The automorphism group of free groups -- 8.12 The special linear group SL(2, Z) -- Exercises -- Summary -- Solutions to exercises -- Chapter 1 -- Chapter 2 -- Chapter 3 -- Chapter 5 -- Chapter 6 -- Chapter 7 -- Chapter 8 -- Bibliography -- Index.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2024. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.