Chapter 4 Contents
4 Public-Key Parameters
4.1 Introduction
4.1.1 Generating large prime numbers naively
4.1.2 Distribution of prime numbers
4.2 Probabilistic primality tests
4.2.1 Fermat's test
4.2.2 Solovay-Strassen test
4.2.3 Miller-Rabin test
4.2.4 Comparison: Fermat, Solovay-Strassen, and Miller-Rabin
4.3 (True) Primality tests
4.3.1 Testing Mersenne numbers
4.3.2 Primality testing using the factorization of n-1
4.3.3 Jacobi sum test
4.3.4 Tests using elliptic curves
4.4 Prime number generation
4.4.1 Random search for probable primes
4.4.2 Strong primes
4.4.3 NIST method for generating DSA primes
4.4.4 Constructive techniques for provable primes
4.5 Irreducible polynomials over Zp
4.5.1 Irreducible polynomials
4.5.2 Irreducible trinomials
4.5.3 Primitive polynomials
4.6 Generators and elements of high order
4.6.1 Selecting a prime p and generator of Zp*
4.7 Notes and further references
Return to the Table of contents