ABSTRACT
In a reduced system of residues, if the exponent of an element isexactly ϕ(m), then this element is called a primitive root modulo m. In a reduced system of residues with a primitive root, every element can be expressed as a power of the primitive root. Conversely, all elements represented by powers of a primitive root form a reduced system of residues. This gives a natural method for constructing a reduced system of residues. However, primitive roots exist only for m = 1, 2, 4, pα, 2pα. How do we construct a reduced system of residues for modulus m for which the primitive root does not exist? All of these will be discussed in this chapter. We will also introduce two major concepts, the exponents and indexes, and their properties. Indexes are called discrete logarithms in cryptography, and the discrete logarithm problem is an important theoretical base for the design of several public key cryptographic algorithms.
