Chapter 3 Contents

Chapter 3 Contents
3 Number-Theoretic Reference Problems
3.1 Introduction and overview
3.2 The integer factorization problem
3.2.1 Trial division
3.2.2 Pollard's rho factoring algorithm
3.2.3 Pollard's p-1 factoring algorithm
3.2.4 Elliptic curve factoring
3.2.5 Random square factoring methods
3.2.6 Quadratic sieve factoring
3.2.7 Number field sieve factoring
3.3 The RSA problem
3.4 The quadratic residuosity problem
3.5 Computing square roots in Zn
3.5.1 Case (i): n prime
3.5.2 Case (ii): n composite
3.6 The discrete logarithm problem
3.6.1 Exhaustive search
3.6.2 Baby-step giant-step algorithm
3.6.3 Pollard's rho algorithm for logarithms
3.6.4 Pohlig-Hellman algorithm
3.6.5 Index-calculus algorithm
3.6.6 Discrete logarithm problem in subgroups of Zp*
3.7 The Diffie-Hellman problem
3.8 Composite moduli
3.9 Computing individual bits
3.9.1 The discrete logarithm problem in Zp* - individual bits
3.9.2 The RSA problem - individual bits
3.9.3 The Rabin problem - individual bits
3.10 The subset sum problem
3.10.1 The L3-lattice basis reduction algorithm
3.10.2 Solving subset sum problems of low density
3.10.3 Simultaneous diophantine approximation
3.11 Factoring polynomials over finite fields
3.11.1 Square-free factorization
3.11.2 Berlekamp's Q-matrix algorithm
3.12 Notes and further references
Return to the Table of contents