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 α to be a primitive root mod p, so p1 is the smallest positive exponent n such that αn1 (mod p). This implies that

αm1αm2(mod p)m1m2(mod p1).

Assume that

βαx, 0x<p1.

We want to find x.

First, it’s easy to determine x (mod 2). Note that

(α(p1)/2)2αp11(mod p), 

so α(p1)/2±1 (mod p) (see Exercise 15 in Chapter 3). However, p1 is assumed to be the smallest exponent to yield +1, so we must have

α(p1)/21(mod p).

Starting with βαx (mod p), raise both sides to the (p1)/2 power to obtain

β(p1)/2αx(p1)/2(1)x(mod p).

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.