# Public-Key Parameters

Contents in Brief

• 4.1 Introduction.............................133
• 4.2 Probabilistic primality tests.....................135
• 4.3 (True) Primality tests........................142
• 4.4 Prime number generation......................145
• 4.5 Irreducible polynomials over Zp..................154
• 4.6 Generators and elements of high order...............160
• 4.7 Notes and further references....................165

## Introduction

The efficient generation of public-key parameters is a prerequisite in public-key systems. A specific example is the requirement of a prime number p to define a finite field Zp for use in the Diffie-Hellman key agreement protocol and its derivatives (§12.6). In this case, an element of high order in Z* is also required. Another example is the requirement of prunes p and q for an RSA modulus n = pq (§8.2). In this case, the prime must be of sufficient size, and be “random” in the sense that the probability of any particular prune being selected must be sufficiently small to preclude an adversary from gaining advantage through optimizing a search strategy based on such probability. Prime numbers may be required to have certain additional properties, in order that they do not make the associated cryptosystems susceptible to specialized attacks. A thud example is the requirement of an irreducible polynomial f(x) of degree m over the finite field Zp for constructing the finite field Fpm. In this case, an element of high order in F*„, is also required.

Chapter outline

The remainder of §4.1 introduces basic concepts relevant to prune number generation and summarizes some results on the distribution of prime numbers. Probabilistic primality tests, the most important of which is the Miller-Rabin test, are presented in §4.2. True primality tests by which arbitrary' integers can be proven to be prune are the topic of §4.3; since these tests are generally more computationally intensive than probabilistic primality tests, they are not described in detail. §4.4 presents four algorithms for generating prime numbers, strong primes, and provable prunes. §4.5 describes techniques for constructing irreducible and primitive polynomials, while §4.6 considers the production of generators and elements of high orders in groups. §4.7 concludes with chapter notes and references.