Discrete Algebraic Methods
Description
The idea behind this book is to provide the mathematical foundations for assessing modern developments in the Information Age. It deepens and complements the basic concepts, but it also considers instructive and more advanced topics. The treatise starts with a general chapter on algebraic structures; this part provides all the necessary knowledge for the rest of the book. The next chapter gives a concise overview of cryptography. Chapter 3 on number theoretic algorithms is important for developping cryptosystems, Chapter 4 presents the deterministic primality test of Agrawal, Kayal, and Saxena. The account to elliptic curves again focuses on cryptographic applications and algorithms. With combinatorics on words and automata theory, the reader is introduced to two areas of theoretical computer science where semigroups play a fundamental role.The last chapter is devoted to combinatorial group theory and its connections to automata.
Contents:
Algebraic structures
Cryptography
Number theoretic algorithms
Polynomial time primality test
Elliptic curves
Combinatorics on words
Automata
Discrete infinite groups
Reviews / Votes
"This extremely reader-friendly textbook covers a broad range of practical topics in the intersection of abstract algebra and computer science. [...] Each chapter ends with a well-chosen set of approachable problems, valuable to instructors and students alike. [...] Overall, authors Diekert, Kufleitner, Rosenberger, and Hertrampf have given us an excellent book on a fascinating area of mathematical practice. I warmly recommend it to readers interested in these topics."James A. Swenson in: MAA November 2017 https://www.maa.org/press/maa-reviews/discrete-algebraic-methods
More details
Other editions
Additional editions
Persons
Content
- 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
