Skip to main content
Mathematics LibreTexts

5: Indices and Discrete Logarithms

  • Page ID
  • \( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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

    This page titled 5: Indices and Discrete Logarithms is shared under a CC BY-SA license and was authored, remixed, and/or curated by Jonathan A. Poritz.

    • Was this article helpful?