# 5: Indices and Discrete Logarithms

- Page ID
- 28652

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

- 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)