Chapter 7. Primitive Roots

The concept of order is central to the multiplicative properties of congruences. The study of orders and indices exploits the structure of the multiplicative group formed by congruences. The primitive root theorem shows that the integers modulo a prime form a cyclic group, that is, they are powers of a single number. This property is important in applications of congruences to public-key cryptosystems such as the ElGamal system , signature schemes , and primality testing.

This chapter includes a detailed discussion of orders (with numerous examples), a proof of the primitive root theorem, properties of the discrete logarithm and algorithms to compute it, and proofs of primality using properties of orders.