Arithmetic of Integers
Basic Arithmetic Operations
GCD
Congruences and Modular Arithmetic
Linear Congruences
Polynomial Congruences
Quadratic Congruences
Multiplicative Orders
Continued Fractions
Prime Number Theorem and Riemann Hypothesis
Running Times of Arithmetic Algorithms
Arithmetic of Finite Fields
Existence and Uniqueness of Finite Fields
Representation of Finite Fields
Implementation of Finite Field Arithmetic
Some Properties of Finite Fields
Alternative Representations of Finite Fields
Computing Isomorphisms among Representations
Arithmetic of Polynomials
Polynomials over Finite Fields
Finding Roots of Polynomials over Finite Fields
Factoring Polynomials over Finite Fields
Properties of Polynomials with Integer Coefficients
Factoring Polynomials with Integer Coefficients
Arithmetic of Elliptic Curves
What Is an Elliptic Curve?
Elliptic-Curve Group
Elliptic Curves over Finite Fields
Some Theory of Algebraic Curves
Pairing on Elliptic Curves
Elliptic-Curve Point Counting
Primality Testing
Introduction to Primality Testing
Probabilistic Primality Testing
Deterministic Primality Testing
Primality Tests for Numbers of Special Forms
Integer Factorization
Trial Division
Pollard’s Rho Method
Pollard’s p - 1 Method
Dixon’s Method
CFRAC Method
Quadratic Sieve Method
Cubic Sieve Method
Elliptic Curve Method
Number-Field Sieve Method
Discrete Logarithms
Square-Root Methods
Algorithms for Prime Fields
Algorithms for Fields of Characteristic Two
Algorithms for General Extension Fields
Algorithms for Elliptic Curves (ECDLP)
Large Sparse Linear Systems
Structured Gaussian Elimination
Lanczos Method
Wiedemann Method
Block Methods
Public-Key Cryptography
Public-Key Encryption
Key Agreement
Digital Signatures
Entity Authentication
Pairing-Based Cryptography
Appendix A: Background
Appendix B: Solutions to Selected Exercises
Index
Biography
Abhijit Das is an associate professor in the Department of Computer Science and Engineering at the Indian Institute of Technology, Kharagpur. His research interests are in the areas of arithmetic and algebraic computations with specific applications to cryptology.
"This book would be a good choice for cryptography and engineering students wanting to learn the basics of algorithmic number theory."
—Mathematical Reviews, November 2014
