# 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 the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.