13 - Basic discrete logarithm algorithms

Summary

This chapter is about algorithms to solve the discrete logarithm problem (DLP) and some variants of it. We focus mainly on deterministic methods that work in any group; later chapters will present the Pollard rho and kangaroo methods, and index calculus algorithms. In this chapter, we also present the concept of generic algorithms and prove lower bounds on the running time of a generic algorithm for the DLP. The starting point is the following definition (already given as Definition 2.1.1).

Definition 13.0.1 Let G be a group written in multiplicative notation. The discrete logarithm problem (DLP) is: given g, h ∈ G find a, if it exists, such that h = g^a. We sometimes denote a by log_g(h).

As discussed after Definition 2.1.1, we intentionally do not specify a distribution on g or h or a above, although it is common to assume that g is sampled uniformly at random in G, and a is sampled uniformly from {1, …, #G}.

Typically, G will be an algebraic group over a finite field F_q and the order of g will be known. If one is considering cryptography in an algebraic group quotient then we assume that the DLP has been lifted to the covering group G. A solution to the DLP exists if and only if h ∈ 〈g〉 (i.e., h lies in the subgroup generated by g). We have discussed methods to test this in Section 11.6.