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 one-time 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
Quotient Space Based Problem Solving
Quotient Space Based Problem Solving provides an in-depth treatment of hierarchical problem solving, computational complexity, and …
book
Design and Analysis of Algorithms, 2nd Edition by Pearson
This second edition of Design and Analysis of Algorithms continues to provide a comprehensive exposure to …
book
Special Theory of Relativity
Special Theory of Relativity is primarily intended as a textbook for the students of physics at …
book
Algebra: Abstract and Modern
Algebra: Abstract and Modern, spread across 16 chapters, introduces the reader to the preliminaries of algebra …