Discrete algebraic methods. Arithmetic, cryptography, automata and groups (Q2840673)

Discrete Algebraic Methods have several applications such as cryptography or the theory of automata. This book on this topic comes out of several lectures of the authors given at the Universities of Stuttgart and Dortmund. The intended audience consists of advanced students of mathematics or computer science. Every chapter ends with a lot of interesting exercises and a valuable summary of the notions and methods and results from the chapter in a short enumeration. The solutions to the exercises are included at the end of the book, which makes the book also very suitable for self-study.NEWLINENEWLINEIn the first chapter the authors develop the basics about groups, rings and fields. The choice of topics is driven by the application in Cryptography. So for example in the theory of fields the emphasis is on finite fields.NEWLINENEWLINEThe second chapter treats cryptography from classical substitution to asymmetric cryptosystems as RSA, Rabin and the Merkle-Hellman system together with the successful attack by Shamir. A short treatment on cryptographic hash functions, digital signatures and secret sharing.NEWLINENEWLINEIt follows a chapter on number theoretic algorithms in connection to applications to the cryptographic systems. Besides the probabilistic prime tests by Miller-Rabin or Solvay-Strassen the Pollard-rho-factorization algorithms is treated. Baby-step-Giant-step and Pollards-rho-method is described for solving the discrete logarithm problem. The chapter concludes with a treatment of discrete Fourier transform and its application to the fast multiplication of numbers by the Schoenhage-Strassen algorithm.NEWLINENEWLINEChapter 4 develops the AKS-test, a deterministic polynomial algorithm to test the primality of primes.NEWLINENEWLINEThe discrete logarithm problem on points on an elliptic curve leads to another cryptosystem, which is described in the fifth chapter. The authors do not confine to write down formulas for the addition of points on the curve but also to give the explanation on the addition law through the notion of divisors without relying on prior knowledge of algebraic geometry.NEWLINENEWLINEThe last three chapters are dedicated to the combinatorics on words, theory of automata and discrete infinite groups. The authors present a new proof of Schützenbergers characterization of starfree languages and of the Krohn-Rhodes decomposition theorem.