Discrete Algebraic Methods

Discrete Algebraic Methods

by Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger, Ulrich Hertrampf
Released May 2016
Publisher(s): De Gruyter
ISBN: 9783110416329

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book 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

Table of contents

  1. Cover
  2. Title Page
  3. Copyright Page
  4. Preface
  5. Contents
  6. 1 Algebraic structures
    1. 1.1 Groups
    2. 1.2 Regular polygons
    3. 1.3 Symmetric groups
    4. 1.4 Rings
    5. 1.5 Modular arithmetic
      1. 1.5.1 Euclidean algorithm
      2. 1.5.2 Ideals in the integers
      3. 1.5.3 Chinese remainder theorem
      4. 1.5.4 Euler’s totient function
    6. 1.6 Polynomials and formal power series
    7. 1.7 Hilbert’s basis theorem
    8. 1.8 Fields
    9. 1.9 Finite fields
    10. 1.10 Units modulo n
    11. 1.11 Quadratic reciprocity
    12. Exercises
    13. Summary
  7. 2 Cryptography
    1. 2.1 Symmetric encryption methods
    2. 2.2 Monoalphabetic cipher
    3. 2.3 Polyalphabetic cipher
    4. 2.4 Frequency analysis and coincidence index
    5. 2.5 Perfect security and the Vernam one-time pad
    6. 2.6 Asymmetric encryption methods
    7. 2.7 RSA cryptosystem
    8. 2.8 Rabin cryptosystem
    9. 2.9 Diffie–Hellman key exchange
      1. 2.10 ElGamal cryptosystem
    10. 2.11 Cryptographic hash functions
    11. 2.12 Digital signatures
    12. 2.13 Secret sharing
    13. 2.14 Digital commitment
    14. 2.15 Shamir’s attack on the Merkle–Hellman cryptosystem
    15. Exercises
    16. Summary
  8. 3 Number theoretic algorithms
    1. 3.1 Runtime analysis of algorithms
    2. 3.2 Fast exponentiation
    3. 3.3 Binary GCD
    4. 3.4 Probabilistic recognition of primes
      1. 3.4.1 Fermat primality test and Carmichael numbers
      2. 3.4.2 Solovay–Strassen primality test
      3. 3.4.3 Miller–Rabin primality test
      4. 3.4.4 Applications of the Miller–Rabin scheme
      5. 3.4.5 Miller–Rabin versus Solovay–Strassen
    5. 3.5 Extracting roots in finite fields
      1. 3.5.1 Tonelli’s algorithm
      2. 3.5.2 Cipolla’s algorithm
    6. 3.6 Integer factorization
      1. 3.6.1 Pollard’s p − 1 algorithm
      2. 3.6.2 Pollard’s rho algorithm for factorization
      3. 3.6.3 Quadratic sieve
    7. 3.7 Discrete logarithm
      1. 3.7.1 Shanks’ baby-step giant-step algorithm
      2. 3.7.2 Pollard’s rho algorithm for the discrete logarithm
      3. 3.7.3 Pohlig–Hellman algorithm for group order reduction
      4. 3.7.4 Index calculus
    8. 3.8 Multiplication and division
    9. 3.9 Discrete fourier transform
    10. 3.10 Primitive roots of unity
    11. 3.11 Schönhage–Strassen integer multiplication
    12. Exercises
    13. Summary
  9. 4 Polynomial time primality test
    1. 4.1 Basic idea
    2. 4.2 Combinatorial tools
    3. 4.3 Growth of the least common multiple
    4. 4.4 Of small numbers and large orders
    5. 4.5 Agrawal–Kayal–Saxena primality test
    6. Summary
  10. 5 Elliptic curves
    1. 5.1 Group law
      1. 5.1.1 Lines
      2. 5.1.2 Polynomials over elliptic curves
      3. 5.1.3 Divisors
      4. 5.1.4 Picard group
    2. 5.2 Applications of elliptic curves
      1. 5.2.1 Diffie–Hellman key exchange with elliptic curves
      2. 5.2.2 Pseudocurves
      3. 5.2.3 Factorization using elliptic curves
      4. 5.2.4 Goldwasser–Kilian primality certificates
    3. 5.3 Endomorphisms of elliptic curves
    4. Exercises
    5. Summary
  11. 6 Combinatorics on words
    1. 6.1 Commutation, transposition and conjugacy
    2. 6.2 Fine and Wilf’s periodicity lemma
    3. 6.3 Kruskal’s tree theorem
    4. Exercises
    5. Summary
  12. 7 Automata
    1. 7.1 Recognizable sets
    2. 7.2 Rational sets
    3. 7.3 Regular languages
    4. 7.4 Star-free languages
    5. 7.5 Krohn–Rhodes theorem
    6. 7.6 Green’s relations
    7. 7.7 Automata over infinite words
      1. 7.7.1 Deterministic Büchi automata
      2. 7.7.2 Union and intersection
      3. 7.7.3 Omega-rational languages
      4. 7.7.4 Recognizability of omega-regular languages
      5. 7.7.5 Monadic second-order logic over infinite words
    8. 7.8 Presburger arithmetic
    9. 7.9 Solutions of linear Diophantine systems
    10. Exercises
    11. Summary
  13. 8 Discrete infinite groups
    1. 8.1 Classical algorithmic problems
    2. 8.2 Residually finite monoids
    3. 8.3 Presentations
    4. 8.4 Rewriting systems
      1. 8.4.1 Termination and confluence
      2. 8.4.2 Semi-Thue systems
    5. 8.5 Solving the word problem in finitely presented monoids
    6. 8.6 Free partially commutative monoids and groups
    7. 8.7 Semidirect products
    8. 8.8 Amalgamated products and HNN extensions
    9. 8.9 Rational sets and Benois’ theorem
    10. 8.10 Free groups
    11. 8.11 The automorphism group of free groups
    12. 8.12 The special linear group SL(2, ℤ)
    13. Exercises
    14. Summary
  14. Solutions to exercises
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 5
    5. Chapter 6
    6. Chapter 7
    7. Chapter 8
  15. Bibliography
  16. Index
  17. Footnotes

Product information

  • Title: Discrete Algebraic Methods
  • Author(s): Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger, Ulrich Hertrampf
  • Release date: May 2016
  • Publisher(s): De Gruyter
  • ISBN: 9783110416329