
# 5: Indices and Discrete Logarithms


• 5.0: Prelude to Indices and Discrete Logarithms
We talked about the cyclic subgroup ⟨a⟩ of (Z/nZ)* generated by an element a in the proof of our version of Lagrange’s Theorem 3.3.1, on the way to Euler’s Theorem 3.3.2. Recall it consisted of all powers of a (well, of [a]_n ) in (Z/nZ)*.
• 5.1: More Properties of Multiplicative Order
This section explores more theorems regarding the properties of multiplicative order, as well as provides the appropriate example and exercises.
• 5.2: A Necessary Digression - Gauss’s Theorem on Sums of Euler’s Function
Later in this chapter, we will need a fact first proved by Gauss about Euler’s ϕ function. This section discusses the two proofs of Gauss’s Theorem on Sums of Euler’s Function.
• 5.3: Primitive Roots
Now back to those elements which generate large cyclic subgroups – which have a name: Primitive Root.
• 5.4: Indices
Some things are natural to conjecture, given these examples and the simple definition of index; many of them are very easy to prove (and are exercises). Before turning to cryptology, we explore some pure mathematical applications of indices.
• 5.5: Diffie-Helman Key Exchange
About a year before the RSA cryptosystem was invented, Whitfield Diffie and Martin Hellman published New directions in cryptography , the first full description of a working public key cryptosystem in the open scientific literature.
• 5.6: The ElGamal Cryptosystem
The ElGamal cryptosystem uses an elementary arithmetic operation – multiplication of a numerical form of the message by a random number in some mod – to do the scrambling needed for encryption. Enough information is also passed along in the ciphertext so that the intended recipient, who knows the value of a certain discrete log, can cancel out this scrambling multiplication.

Thumbnail: In the Diffie–Hellman key exchange scheme, each party generates a public/private key pair and distributes the public key. After obtaining an authentic copy of each other's public keys, Alice and Bob can compute a shared secret offline. (Pubic Domain; Davidgothberg via Wikipedia)