Preface 1 Arithmetic cf Integers 1.1 Basic Aiithmetic Operations 1.1.1 Representation of Big Integers 1.1.1.1 Inlzut and Output 1.1.2 Schoolbock Arithmetic 1.1.2.1 Addition 1.1.2.2 Subtraction 1.1.2.3 Multiplication 1.1.2.4 Euclidean Division 1.1.3 Fast Arithmetic 1.1.3.1 Karatsuba-Ofman Multiplication 1.1.3.2 Toom-Cook Multiplicaticn 1.1.3.3 FFT-Based Multiplication 1.1.4 An Introduction to GP/PARI 1.2 GCD 1.2.1 Euclidean GCD Algorithm 1.2.2 Extended GCD Algorithm 1.2.3 Binary GCD Algorithm 1.3 Congruences and Modular Arithmetic 1.3.1 Modular Exponentiation 1.3.2 Fast Modular Exponentiation 1.4 Linear Congruences 1.4.1 Chinese Remainder Theorem 1.5 Polynomial Ccngruences 1.5.1 Hensel Lifting 1.6 Quadratic Congruences 1.6.1 Quadratic Residues and Non-Residues 1.6.2 Legendre Symbol 1.6.3 Jaeobi Symbol 1.7 Multiplicative Orders 1.7.1 Primitive Roots 1.7.2 Coml:uting Orders 1.8 Continued Fractions 1.8.1 Finite Continued Fractions 1.8.2 Infinite Continued Fractions 1.9 Prime Number Theorem and Riemann Hypothesis 1.10 Running Times of Arithmetic Algorithms 2 Arithmetic of Finite Fields 2.1 Existence and Uniqueness of Finite Fields 2.2 Representation of Finite Fields 2.2.1 Polynomial-Basis Representation 2.2.2 Working with Finite Fields in GP/PARI 2.2.3 Choice of the Defining Polynomial 2.3 Implementation of Finite Field Arithmetic 2.3.1 Representation of Elements 2.3.2 Polynomial Arithmetic 2.3.2.1 Addition and Subtraction 2.3.2.2 Multiplication 2.3.2.3 Comb Methods 2.3.2.4 Windowed Comb Methods 2.3.2.5 Modular Reduction 2.3.3 Polynomial GCD and Inverse 2.3.3.1 Euclidean Inverse 2.3.3.2 Binary Inverse 2.3.3.3 Almost Inverse 2.4 Some Properties of Finite Fields 2.4.1 Fermat's Little Theorem for Finite Fields 2.4.2 Multiplicative Orders of Elements in Finite Fields 2.4.3 Normal Elements 2.4.4 Minimal Polynomials 2.4.5 Implementing Some Functions in GP/PARI 2.5 Alternative Representations of Finite Fields 2.5.1 Representation with Respect to Arbitrary Bases 2.5.2 Normal and Optimal Normal Bases 2.5.3 Discrete-Log Representation 2.5.4 Representation with Towers of Extensions 2.6 Computing Isomorphisms among Representations 3 Arithmetic of Polynomials 3.1 Polynomials over Finite Fields 3.1.1 Polynomial Arithmetic 3.1.2 Irreducible Polynomials over Finite Fields 3.1.3 Testing Irreducibility of Polynomials 3.1.4 Handling Irreducible Polynomials in GP/PARI 3.2 Finding Roots of Polynomials over Finite Fields 3.2.1 Algorithm for Fields of Odd Characteristics 3.2.2 Algorithm for Fields of Characteristic Two 3.2.3 Root Finding with GP/PARI 3.3 Factoring Polynomials over Finite Fields 3.3.1 Square-Free Factorization 3.3.2 Distinct-Degree Factorization 3.3.3 Equal-Degree Factorization 3.3.4 Factoring Polynomials in GP/PARI 3.4 Properties of Polynomials with Integer Coefficients 3.4.1 Relation with Polynomials with Rational Coefficients. 3.4.2 Height, Resultant, and Discriminant 3.4.3 Hensel Lifting 3.5 Factoring Polynomials with Integer Coefficients 3.5.1 Berlekamp's Factoring Algorithm 3.5.2 Basis Reduction in Lattices 3.5.3 Lenstra-Lenstra-Lov~sz Factoring Algorithm 3.5.4 Factoring in GP/PARI 4 Arithmetic of Elliptic Curves 4.1 What Is an Elliptic Curve? 4.2 Elliptic-Curve Group 4.2.1 Handling Elliptic Curves in GP/PARI 4.3 Elliptic Curves over Finite Fields 4.4 Some Theory of Algebraic Curves 4.4.1 Affine and Projective Curves 4.4.1.1 Affine Curves 4.4.1.2 Projective Curves ����