17.2.2. Definition of Discrete Logarithm

Let G be a cyclic group and that abstract operation is o and suppose the order of the cyclic group is q that means, you have q number of elements and for simplicity and without loss of generality, I will follow that multiplicative interpretation, while giving the definition of discrete logarithm, but the definition can be easily generalized even when the underlying operation is interpreted in the additive sense.

In this section, we introduce cyclic groups. A cyclic group is a mathematical structure where every element can be generated by repeatedly applying a group operation (like addition or multiplication) to a specific element known as the generator. The order of the group, denoted q, tells us how many elements this group contains. For instance, a cyclic group of order 4 could be made up of elements {0, 1, 2, 3}, each corresponding to an operation applied to the generator. Importantly, the same principles apply whether we are looking at multiplication or addition.

Think of a music playlist that repeats after a certain number of songs. If your playlist can play four different songs, it represents a cyclic group of order 4. There’s always a song (the generator) that starts the sequence, and by playing it repeatedly, you return to the original song after four total plays.

Consider an arbitrary element y from the group, since the element y is a member of the group, it can be generated by some power of your generator. That unique power in the range 0 to q - 1 which when raised to the generator gives you the element y, will be called as the discrete logarithm of the y to the base g.

Here, we define the discrete logarithm in the context of a cyclic group. If y is an element of the group G, it can be expressed as g raised to some power, where g is the generator. The discrete logarithm is that power, which we denote as x, that satisfies the relation g^x = y, where x is between 0 and q-1. It’s a way of reverting back from the product (y) to the exponent (x), similar to how ordinary logarithms work.

Imagine you have a key for a locked box, which can only open at a certain position (the generator). The discrete logarithm represents the position you need to turn the key (y) to unlock the box. Just like you know the position of the key lock, the discrete logarithm tells you where to turn to find the value that leads to y.

Interestingly, like the natural logarithms, your discrete logarithm also obeys the rules that are there in the context of natural logarithms. For instance, we know that log of 1 to the base of any a is 0 because a to the power 0 is defined to be 1 in for natural logarithms. In the context of discrete logarithms, we say that the discrete log of the identity element of the group to the base of g will be 0.

This chunk discusses the properties of discrete logarithms that resemble those of natural logarithms. For example, the log of 1 in any base is 0 because raising any number to the power of 0 yields 1. Consequently, the discrete logarithm of the identity element in the group (which is always 1 for multiplication) is also 0 because the generator raised to the power of 0 (g^0) equals the identity element.

Think of a light switch that can either be on or off. The 'off' state (identity) is like the number 1. If the switch is off, no matter how you turn it (like any base raised to the power of 0), it remains off. The off-state represents the '0' in discrete logarithms.

You are given the description of the cyclic group. By the description I mean, you know, the characteristic of the elements of the group, your group might be exponentially large. It might have exponentially large number of elements and you may not have sufficient space and resources to store down all the elements of your group.

Here, we discuss the challenge of computing discrete logarithms. Given a potentially large cyclic group defined by its characteristics, one would need to find the discrete logarithm for some randomly selected element y. The problem can be computationally intensive and may require space/resources to handle large groups. It emphasizes the complexity of finding x when only provided with y and g, as simply running through all possible exponents (from 0 to q-1) could be extremely inefficient.

Imagine trying to find a specific book in a massive library without knowing its location. The library is like the large cyclic group, and each book represents an element. Searching through every shelf until you find the one you want would take a long time, illustrating why computing discrete logarithms can be hard.

I call this algorithm as brute force discrete log solver because it basically does what a naive algorithm will do, you basically try all powers of x in the range 0 to q - 1. And check whether computing g power x gives you the element y or not, if it is then, you output that x and stop the algorithm.

This chunk describes a brute force approach to compute the discrete logarithm. In this method, the algorithm tests every possible exponent x from 0 to q-1 to determine if raising g to that power yields the desired element y. While this algorithm is guaranteed to eventually find the answer, its efficiency is questionable since it may take a long time if q is large.

Think of a combination lock with a 3-digit code. The brute force method would involve trying every combination from 000 to 999 until you find the right one. While you will eventually unlock it, this method is time-consuming and inefficient, especially if the number of combinations is large.

In the next question is does there exist a better algorithm? And the answer is both yes, as well as no. Yes because as we will see soon, there are indeed certain cyclic groups where I can efficiently find out the discrete logarithm of any randomly chosen y, without doing the brute force.

This section discusses the overall difficulty of computing discrete logarithms. While brute force is one approach, the existence of more efficient algorithms for certain cyclic groups suggests that not all groups present a challenge in the same way. Some groups allow for easier computation of the discrete logarithm, while others remain complex and computationally taxing.

Imagine navigating through a city with varying levels of traffic. Some streets are clear (efficient algorithms) allowing you to reach your destination quickly, while others are heavily congested (complex groups) making for a frustrating and slow trip. Just like navigating traffic, discrete logarithms exist in varying degrees of difficulty depending on their structure.

--