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
 Cover
 Title Page
 Copyright Page
 Preface
 Contents
 1 Algebraic structures

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 onetime pad
 2.6 Asymmetric encryption methods
 2.7 RSA cryptosystem
 2.8 Rabin cryptosystem
 2.9 Diffie–Hellman key exchange
 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.5 Extracting roots in finite fields
 3.6 Integer factorization
 3.7 Discrete logarithm
 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
 5 Elliptic curves
 6 Combinatorics on words
 7 Automata

8 Discrete infinite groups
 8.1 Classical algorithmic problems
 8.2 Residually finite monoids
 8.3 Presentations
 8.4 Rewriting 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, ℤ)
 Exercises
 Summary
 Solutions to exercises
 Bibliography
 Index
 Footnotes
Product information
 Title: Discrete Algebraic Methods
 Author(s):
 Release date: May 2016
 Publisher(s): De Gruyter
 ISBN: 9783110416329
You might also like
book
Elementary Number Theory with Programming
A highly successful presentation of the fundamental concepts of number theory and computer programming Bridging an …
book
Discrete Structures, Logic, and Computability, 4th Edition
Following the recent updates to the 2013 ACM/IEEE Computer Science curricula, Discrete Structures, Logic, and Computability, …
book
Introduction to Probability
Developed from celebrated Harvard statistics lectures, Introduction to Probability provides essential language and tools for understanding …
book
An Introduction to Formal Languages and Automata, 6th Edition
The Sixth Edition of An Introduction to Formal Languages and Automata provides an accessible, studentfriendly presentation …