This book covers discrete mathematics both as it has been established after its emergence since the middle of the last century and as its elementary applications to cryptography. It can be used by any individual studying discrete mathematics, finite mathematics, and similar subjects. Any necessary prerequisites are explained and illustrated in the book. As a background of cryptography, the textbook gives an introduction into number theory, coding theory, information theory, that obviously have discrete nature. Designed in a “self-teaching” format, the book includes about 600 problems (with and without solutions) and numerous, practical examples of cryptography.
FEATURES:
Designed in a “self-teaching” format, the book includes about 600 problems (with and without solutions) and numerous examples of cryptography
Provides an introduction into number theory, game theory, coding theory, and information theory as background for the coverage of cryptography
Covers cryptography topics such as CRT, affine ciphers, hashing functions, substitution ciphers, unbreakable ciphers, Discrete Logarithm Problem (DLP), and more.
Author(s): Alexander I. Kheyfits
Publisher: Mercury Learning and Information
Year: 2021
Language: English
Pages: 382
Cover
Title Page
Copyright
Contents
Preface
Chapter 1: A Brief Survey of Elementary Functions
1.1 Mathematical Induction
1.2 Factorials and The Stirling Formula
1.3 Recursive Definitions
1.4 Elementary Functions
1.4.1 Quadratic Functions
1.4.2 Exponential and Logarithmic Functions
1.4.3 Trigonometric Functions
1.5 Stirling Asymptotic Formula
1.6 Exercises
Chapter 2: Propositional Algebra
2.1 Propositions
2.2 Connectives: Truth Tables
2.2.1 Order of Operations
2.3 Exercises
Chapter 3: Naïve and Formal (Axiomatic) Set Theory
3.1 Classes and Sets. Axioms and Theorems
3.1.1 Classical Set Theory
3.1.2 Operations on Sets: Set Diagrams
3.2 Exercises
Chapter 4: Groups, Rings, and Fields
4.1 Groups, Rings, and Fields
4.2 Matrices and Determinants
4.3 Finite Groups
4.3.1 Cyclic Groups
4.4 The Discrete Logarithm Problem
4.5 Exercises
Chapter 5: Predicates and Quantifiers—Algebraic Theory
5.1 Predicates
5.2 Quantifiers
5.2.1 Commutativity of Quantifiers and Boolean Operations
5.3 Exercises
Chapter 6: Binary Relations and Relational Databases
6.1 Ordered Totalities and Cartesian Products
6.2 Relations
6.2.1 Special Classes of Relations
6.3 Orderings and Posets
6.3.1 Equivalence Relations
6.3.2 Equivalence Classes
6.4 Relation Databases
6.5 Exercises
Chapter 7: Combinatorics
7.1 Finite and Infinite Sets: Basic Rules
7.1.1 The Sum and Product Rules
7.1.2 Unions, Cartesian Products, Booleans
7.1.3 Arrangements and Combinations
7.1.4 Stirling Numbers
7.1.5 Combinations With Repetitions
7.1.6 Permutations With Identified Elements
7.2 Exercises
Chapter 8: Elements of Number Theory
8.1 Divisibility and FTA
8.1.1 Divisibility, the FTA, and the Euclidean Algorithm
8.1.2 Euclidean Algorithm
8.1.3 Algorithms
8.1.4 Modular or Clock Arithmetic: Linear Congruences
8.1.5 Totient Function
8.1.6 Pseudorandom Numbers
8.1.7 Cryptography Application: Sharing Secrets
8.1.8 Affine Ciphers
8.2 Exercises
Chapter 9: Boolean Functions
9.1 Boolean Degree: DNF and CNF
9.2 Boolean Polynomials
9.3 Boolean Derivatives
9.4 Exercises
Chapter 10: Hashing Functions and Cryptographic Maps
10.1 Rosetta Stone
10.2 Hashing Functions
10.3 Substitution Ciphers
10.4 Exercises
Chapter 11: Generating Polynomials and Inversion Formulas
11.1 Partitions of the Integers
11.1.1 Compositions
11.1.2 Inversion Formulas
11.2 Exercises
Chapter 12: Systems of Representatives
12.1 SDRs
12.1.1 Systems of Triples
12.2 Exercises
Chapter 13: Boolean Algebras
13.1 Operations and Axioms
13.2 Boolean Rings
13.3 Exercises
Chapter 14: Combinatorial Circuits
14.1 Graphs and Schemes
14.2 Logical Problems
14.2.1 Binary Adders
14.3 Exercises
Chapter 15: Complete Systems of Boolean Functions and Bases
15.1 Complete Systems and Bases
15.2 Post Theorem
15.2.1 Bases
15.3 Exercises
Chapter 16: Introductory Graph Theory, Euler’s Formula, and Unbreakable Ciphers
16.1 Graphs and Diagrams
16.2 Connectivity in Graphs
16.2.1 Unbreakable Ciphers
16.2.2 Bipartite Graphs
16.3 Exercises
Chapter 17: Trees and Digraphs
17.1 Spanning Trees
17.2 Binary Search
17.3 Exercises
Chapter 18: Computations and Algorithms
18.1 Exercise
Chapter 19: Finite Automata
19.1 Simple Model
19.2 Tables and Graphs of Automata
19.3 Classification: Equivalent States and Equivalent Automata
19.3.1 Minimization of Automata
19.3.2 Automaton Operators
19.3.3 Regular Grammars
19.4 Exercises
Chapter 20: Introduction to Game Theory
20.1 Classification of Strategies
20.2 Exercises
Chapter 21: Information Theory and Coding
21.1 Measure of Information
21.2 Channels
21.3 Exercises
Chapter 22: Probability Theory with a Finite Sample Space and the Birthday Problem
22.1 Random Experiments
22.2 Probability Distributions
22.3 Expectation: Bayes Formula
22.4 Bernoulli Trials and The Birthday Problem
22.5 Exercises
Chapter 23: Turing Machines, P and NP Classes, and Other Models of Computation
23.1 Turing Machines
23.2 Exercise
Chapter 24: Answers and Solutions to Selected Exercises
Bibliography
Index
