# 10.2 Computing Discrete Logs

In this section, we present some methods for computing discrete logarithms. A method based on the birthday attack is discussed in Subsection 12.1.1.

For simplicity, take $\alpha $ to be a primitive root mod $p$, so $p-1$ is the smallest positive exponent $n$ such that ${\alpha}^{n}\equiv 1\text{}(\text{mod}\text{}p)$. This implies that

Assume that

We want to find $x$.

First, it’s easy to determine $x\text{}(\text{mod}\text{}2)$. Note that

so ${\alpha}^{(p-1)/2}\equiv \pm 1\text{}(\text{mod}\text{}p)$ (see Exercise 15 in Chapter 3). However, $p-1$ is assumed to be the smallest exponent to yield $+1$, so we must have

Starting with $\beta \equiv {\alpha}^{x}\text{}(\text{mod}\text{}p)$, raise both sides to the $(p-1)/2$ power to obtain

Therefore, if ...

Get *Introduction to Cryptography with Coding Theory, 3rd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.