ABSTRACT
Mathematics, rightly viewed, possesses not only truth, but supreme beauty — a beauty cold and austere, like that of sculpture.
From Philosophical Essays (1910) no. 2 Bertrand Russell (1872-1970), British philosopher and
mathematician
In this chapter we look at the multiplicative structure of Z/nZ introduced in Definition 2.4 on page 79. The topic of this chapter, primitive roots, defined in this section, may be used to simplify the calculations in Z/nZ. The results we develop will allow us to look at further applications to primality testing and to random number generation, both of which are important in cryptographic applications, such as in §3.5. We need to develop the tools to do so. First we need the following concept related to Euler’s Theorem 2.10 on page 93, which tells us that for m ∈ Z and n ∈ N with gcd(m,n) = 1, we have mφ(n) ≡ 1 (mod n). One may naturally ask for the smallest exponent e ∈ N such that me ≡ 1(mod n). Definition 3.1 Modular Order of an Integer
Let m ∈ Z, n ∈ N, and gcd(m,n) = 1. Then the order of m modulo n is the smallest e ∈ N such that me ≡ 1(mod n), denoted by e = ordn(m), and we say that m belongs to the exponent e modulo n.
