正版 计算数论(英文) (印)阿比吉特·达斯 哈尔滨工业大学出版社 9

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

4

本书共包含九章及两个附录，具体介绍了计算数论的相关知识，内容涉及整数的算术、有限域算术、多项式算术、椭圆曲线算术、整数分解、离散对数、大稀疏线性系统、公钥密码学等内容。本书通过很好基础的整数和多项式的算术来构建计算数论的基础，讨论了椭圆曲线、整数分解算法、计算离散对数以及稀疏线性系统方法，同时展示了数论在密码学和密码分析中的应用，还专门针对数论在公钥密码学中的应用设计了一个章节，展示了基于配对的密码学的近期新发展情况。本书可为深入研究这一方向的读者提供丰富的参考资料。