Computational Number Theory

Developed from the author’s popular graduate-level course, Computational Number Theory presents a complete treatment of number-theoretic algorithms. Avoiding advanced algebra, this self-contained text is designed for advanced undergraduate and beginning graduate students in engineering. It is also suitable for researchers new to the field and practitioners of cryptography in industry. Requiring no prior experience with number theory or sophisticated algebraic tools, the book covers many computational aspects of number theory and highlights important and interesting engineering applications. It first builds the foundation of computational number theory by covering the arithmetic of integers and polynomials at a very basic level. It then discusses elliptic curves, primality testing, algorithms for integer factorization, computing discrete logarithms, and methods for sparse linear systems. The text also shows how number-theoretic tools are used in cryptography and cryptanalysis. A dedicated chapter on the application of number theory in public-key cryptography incorporates recent developments in pairing-based cryptography. With an emphasis on implementation issues, the book uses the freely available number-theory calculator GP/PARI to demonstrate complex arithmetic computations. The text includes numerous examples and exercises throughout and omits lengthy proofs, making the material accessible to students and practitioners.

Arithmetic of Integers Basic Arithmetic OperationsGCD Congruences and Modular Arithmetic Linear Congruences Polynomial Congruences Quadratic Congruences Multiplicative Orders Continued FractionsPrime Number Theorem and Riemann Hypothesis Running Times of Arithmetic Algorithms Arithmetic of Finite Fields Existence and Uniqueness of Finite Fields Representation of Finite FieldsImplementation of Finite Field ArithmeticSome Properties of Finite FieldsAlternative Representations of Finite FieldsComputing Isomorphisms among Representations Arithmetic of Polynomials Polynomials over Finite FieldsFinding Roots of Polynomials over Finite FieldsFactoring Polynomials over Finite FieldsProperties of Polynomials with Integer CoefficientsFactoring 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 CurvesPairing on Elliptic CurvesElliptic-Curve Point Counting Primality TestingIntroduction to Primality TestingProbabilistic Primality TestingDeterministic Primality Testing Primality Tests for Numbers of Special Forms Integer Factorization Trial Division Pollard’s Rho MethodPollard’s p - 1 MethodDixon’s Method CFRAC Method Quadratic Sieve MethodCubic Sieve Method Elliptic Curve Method Number-Field Sieve Method Discrete Logarithms Square-Root MethodsAlgorithms for Prime FieldsAlgorithms for Fields of Characteristic TwoAlgorithms 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 EncryptionKey Agreement Digital SignaturesEntity AuthenticationPairing-Based Cryptography Appendix A: BackgroundAppendix B: Solutions to Selected Exercises Index

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.