Primality Testing in Polynomial Time多项式时间中的初级测试 pdf epub mobi txt 电子书 下载 2025

1.　Introduction: Efficient Primality Testing
　1.1　Algorithms for the Primality Problem
　1.2　Polynomial and Superpolynomial Time Bounds
　1.3　Is PRIMES in P?
　1.4　Randomized and Superpolynomial Time Algorithms for the Primality Problem
　1.5　The New Algorithm
　1.6　Finding Primes and Factoring Integers
　1.7　How to Read This Book
2.　Algorithms for Numbers and Their Complexity
　2.1　Notation for Algorithms on Numbers
　2.2　O-notation
　2.3　Complexity of Basic Operations on Numbers
3.　Fundamentals from Number Theory
　3.1　Divisibility and Greatest Common Divisor
　3.2　The Euclidean Algorithm
　3.3　Modular Arithmetic
　3.4　The Chinese Remainder Theorem
　3.5　Prime Numbers
　　3.5.1　Basic Observations and the Sieve of Eratosthenes
　　3.5.2　The Fundamental Theorem of Arithmetic
　3.6　Chebychev's Theorem on the Density of Prime Numbers
4.　Basics from Algebra: Groups, Rings, and Fields
　4.1　Groups and Subgroups
　4.2　Cyclic Groups
　　4.2.1　Definitions, Examples, and Basic Facts
　　4.2.2　Structure of Cyclic Groups
　　4.2.3　Subgroups of Cyclic Groups
　4.3　Rings and Fields
　4.4　Generators in Finite Fields
5.　The Miller-Rabin Test
　5.1　The Fermat Test
　5.2　Nontrivial Square Roots of 1
　5.3　Error Bound for the Miller-Rabin Test
6.　The Solovay-Strassen Test
　6.1　Quadratic Residues
　6.2　The Jacobi Symbol
　6.3　The Law of Quadratic Reciprocity
　6.4　Primality Testing by Quadratic Residues
7.　More Algebra: Polynomials and Fields
　7.1　Polynomials over Rings
　7.2　Division with Remainder and Divisibility for Polynomials...
　7.3　Quotients of Rings of Polynomials
　7.4　Irreducible Polynomials and Factorization
　7.5　Roots of Polynomials
　7.6　Roots of the Polynomial Xr-1
8.　Deterministic Primality Testing in Polynomial Time
　8.1　The Basic Idea
　8.2　The Algorithm of Agrawal, Kayal, and Saxena
　8.3　The Running Time
　　8.3.1　Overall Analysis
　　8.3.2　Bound for the Smallest Witness r
　　8.3.3　Improvements of the Complexity Bound
　8.4　The Main Theorem and the Correctness Proof
　8.5　Proof of the Main Theorem
　　8.5.1　Preliminary Observations
　　8.5.2　Powers of Products of Linear Terms
　　8.5.3　A Field F and a Large Subgroup G of F* .
　　8.5.4　Completing the Proof of the Main Theorem
A.　Appendix
　A.1 Basics from Combinatorics
　A.2 Some Estimates
　A.3 Proof of the Quadratic Reciprocity Law
　　A.3.1 A Lemma of Gauss
　　A.3.2 Quadratic Reciprocity for Prime Numbers
　　A.3.3 Quadratic Reciprocity for Odd Integers
References
Index
· · · · · · (收起)