MMONO/232: Number-theoretic algorithms in cryptography密码术中的数论算法
点此进入淘宝搜索页搜索分類: 图书,进口原版书,科学与技术 Science & Techology ,
作者： O. N. Vasilenko，Alex Martsinkovsky著
出 版 社：
出版时间： 2006-12-1字数：版次：页数： 243印刷时间： 2006/12/01开本： 16开印次：纸张： 胶版纸I S B N ： 9780821840900包装： 精装内容简介
Algorithmic number theory is a rapidly developing branch of number theory, which, in addition to its mathematical importance, has substantial applications in computer science and cryptography. Among the algorithms used in cryptography, the following are especially important: algorithms for primality testing; factorization algorithms for integers and for polynomials in one variable; applications of the theory of elliptic curves; algorithms for computation of discrete logarithms; algorithms for solving linear equations over finite fields; algorithms for performing arithmetic operations on large integers. The book describes the current state of these and some other algorithms. It also contains extensive bibliography. For this English translation, additional references were prepared and commented on by the author.
目录
Preface to the English Edition
Preface
Notation
Chapter 1. Primality Testing and Construction of Large Primes
1.1. Introduction
1.2. Elementary methods of primality testing
1.3. Primality tests for numbers of a special form
1.4. (N±1)-methods for primality testing, and construction of large primes
1.5. The Konyagin-Pomerance algorithm
1.6. Miller's algorithm
1.7. Probabilistie primality tests
1.8. Modern methods for primality testing
1.9. Summary. A deterministic polynomial algorithm for primality testing
Chapter 2. Factorization of Integers with Exponential Complexity
2.1. Introduction. Fermat's method
2.2. Pollard's (P-1)-method
2.3. Pollard's p-method
2.4. The Sherman-Lehman method
2.5. Lenstra's algorithm
2.6. The Pollard-Strassen algorithm
2.7. Williams' (P+1)-method and its generalizations
2.8. Shanks' methods
2.9. Other methods. Summary
Chapter 3. Factorization of Integers with Subexponential Complexity
3.1. Introduction
3.2. Dixon's method. Additional strategies
3.3. The Brillhart-Morrison algorithm
3.4. Quadratic sieve
3.5. The methods of Schnorr-Lenstra and Lenstra-Pomerance
3.6. Number field sieves
3.7. Summary
Chapter 4. Application of Elliptic Curves to Primality Testing and Factorization of Integers
4.1. Introduction. Elliptic curves and their properties
4.2. Lenstra's algorithm for factorization of integers using elliptic curves
4.3. Computing the order of the group of points of an elliptic curve over a finite field
4.4. Primality testing using elliptic curves
4.5. Summary
Chapter 5. Algorithms for Computing Discrete Logarithm
5.1. Introduction. Deterministic methods
5.2. Pollard's p-method for the discrete logarithm problem
5.3. The discrete logarithm problem in prime fields
5.4. Discrete logarithm in Galois fields
5.5. Discrete logarithm and the number field sieve
5.6. Fermat quotient and discrete logarithm with composite modulus
5.7. Summary
Chapter 6. Factorization of Polynomials over Finite Fields
6.1. Introduction. A probabilistic algorithm for solving algebraic equations in finite fields
6.2. Solving quadratic equations
6.3. The Berlekamp algorithm
6.4. The Cantor-Zassenhaus method
6.5. Some other improvements of the Berleknmp algorithm
6.6. A probabilistic algorithm for irreducibility testing of polynomials over finite fields
6.7. Summary
Chapter 7. Reduced Lattice Bases and Their Applications
7.1. Introduction. Lattices and bases
7.2. LLL-reduced bases and their properties
7.3. An algorithm for constructing an LLL-reduced lattice basis
7.4. The Schnorr-Euchner algorithm and an integral LLL algorithm
7.5. Some applications of the LLL algorithm
7.6. The Ferguson-Forcade algorithm
7.7. Summary
Chapter 8. Factorization of Polynomials over the Field of Rational Numbers with Polynomial Complexity
8.1. Introduction
8.2. The LLL factorization algorithm: Factorization modulo a prime
8.3. The LLL factorization algorithm: Using lattices
8.4. The LLL factorization algorithm: Lifting the factorization
8.5. The LLL factorization algorithm: A complete description
8.6. A usable factorization algorithm
8.7. Factorization of polynomials using approximations
8.8. Summary
Chapter 9. Discrete Fourier Transform and Its Applications
9.1. Introduction. Discrete Fourier transform and its properties
9.2. Computing the discrete Fourier transform
9.3. Discrete Fourier transform and multiplication of polynomials
……
Chapter 10. High-Precision Integer Arithmetic
Chapter 11. Sloving Systems of Linear Equations over Finite Fields
Appendix.Facts from Number Theory
Bibliography
Index
