Home Page Icon
Home Page
Table of Contents for
Title Page
Close
Title Page
by Ulrich Hertrampf, Gerhard Rosenberger, Manfred Kufleitner, Volker Diekert
Discrete Algebraic Methods
Cover
Title Page
Copyright Page
Preface
Contents
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, ℤ)
Exercises
Summary
Solutions to exercises
Chapter 1
Chapter 2
Chapter 3
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Bibliography
Index
Footnotes
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Prev
Previous Chapter
Front Matter
Next
Next Chapter
Copyright Page
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset