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}