1st Edition

Computational Number Theory

By Abhijit Das Copyright 2013
    614 Pages 13 B/W Illustrations
    by Chapman & Hall

    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 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



    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