Computational Number Theory

Free Standard Shipping

Purchasing Options

ISBN 9781439866153
Cat# K12950



SAVE 20%

eBook (VitalSource)
ISBN 9781439866184
Cat# KE13172



SAVE 30%

eBook Rentals


  • Explores many important computational issues and recent developments in number theory
  • Presents an elementary treatment of the material, eliminating the need for an extensive background in mathematics
  • Uses the GP/PARI number-theory calculator to illustrate complicated algorithms
  • Describes the application of number theory in public-key cryptography
  • Contains numerous examples and exercises, with some solutions in an appendix

Solutions manual available upon qualifying course adoption


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.

Table of Contents

Arithmetic of Integers
Basic Arithmetic Operations
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


Author Bio(s)