Baby-Step, Giant-Step: Solving Discrete Logarithms and Why It’s A Hard Problem To Solve

Within normal logarithms we define:

h = aˣ

So if we want to find the value of x, we use:

x = logₐ (h)

So 10⁴ is 10,000, and the inverse log is log10(10,000) is 4.

Within discrete logarithms we introduce a finite field with a prime number. For this we have:

h = gˣ (mod p)

and where p is the prime number. It is thus a difficult task to find the value of x which has been used, even if we know h, g and p. We use discrete logarithms with the Diffie-Hellman key exchange method and in ElGamal encryption.

Let’s start with an example:

20 = 5ˣ (mod 53)

In this case we have g= 5, h= 20 and p= 53, and want to find x. We first determine the square root of p-1, and we will round it up to the nearest integer. In this case it will be:

N =Ceiling(√(p-1)) = Ceiling(√(52)) = 7

Next we will pre-compute from 1 to N with the baby table. These will store gⁱ (mod p) and then store them in the form of {gⁱ (mod p), i}:

{1: 0, 3: 7, 5: 1, 51: 5, 42: 4, 43: 6, 19: 3, 25: 2}