17.2.5. Difficult Computation in Certain Cyclic Groups

So, let us start with the discrete logarithm definition in the context of cyclic groups. So, 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. So, since my group G is a cyclic group it must be having a generator, so, let the g be generator and since the order of the group is q, has q number of elements that means, by raising or by computing q different powers of the generator, I can obtain all the elements of my group. Now, 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.

In this section, we discuss the concept of discrete logarithm in cyclic groups. A cyclic group is a mathematical structure with a set of elements that can be generated by repeatedly applying an operation (like multiplication) to a specific element called the generator. When we say the 'order' of the group is q, it means there are q different elements in the group. Every element can be expressed as the generator raised to some power. The discrete logarithm helps us find out this particular power (or exponent) for any element in the group.

Think of a light dimmer switch that can only be set to a limited number of brightness levels, say 5. The dimmer switch represents our generator, and each brightness level represents an element in the cyclic group. If I tell you that the light is set to level 3, finding out which setting that is (3/5) is similar to finding the discrete logarithm, where you need to determine how many turns you've made on the dimmer from its lowest setting, which is like finding 'x' in y = g^x.

So, now an interesting problem is that how easy or how difficult it is to compute the discrete logarithm. So, imagine we are given an abstract cyclic group of order q and this notation means that, the number of bits that I need to represent my q is n bits. So, this notation is nothing but the number of bits needed to represent q. That means magnitude wise q is as large as 2n. Now, let us see how difficult or how easy it is to compute a discrete logarithm.

The next important point is understanding how difficult it can be to compute the discrete logarithm. If q is a large number, representing it as n bits means that q can be as big as 2 raised to the power n. This growth indicates that even though we have definitions and methods, finding the discrete logarithm becomes increasingly complex as the size of q increases. We want to determine how efficiently we can compute this logarithm with available resources.

Imagine trying to find out which step you are on in a very tall building with 2^n floors. If I ask you to find out which floor you're on without you telling me first, it’ll take a long time to check each floor, especially as the building gets taller (q becomes larger). The problem with finding the discrete logarithm is similar — the bigger the group, the longer it can take to find the exact 'floor' or power you're standing on.

So, here is a naive algorithm which will always be successful to give you the discrete log of the randomly chosen y. 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.

We introduce a basic method for solving the discrete logarithm problem called the brute force method. The idea is straightforward: you try every possible power of the generator (from 0 to q-1) until you find the one that produces the desired element y. While this method guarantees a correct answer, it is not efficient since it might require checking a large number of possibilities, leading to an exponential runtime.

Imagine you're looking for a specific book in a massive library without a catalog. The brute force approach would mean searching each shelf one by one until you find the book you want. This method works, but it can take a very long time, especially if the library has thousands of books (like the number of possible logarithm calculations in a large group).

So now, 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. But at the same time, we do have some candidate cyclic groups where it is for which it is conjectured that we do not have any better algorithm other than brute forcing over all candidate values of x.

In some cases, more efficient algorithms do exist that allow us to compute discrete logarithms much faster than the brute force method. However, there are also cyclic groups for which no better strategies have been found, leaving brute force as the only viable option. This highlights the complexity and variability in solving the discrete logarithm problem across different groups.

Think of trying to crack different types of codes. For some simple codes, using pattern recognition might help you break it quickly (better algorithms). However, for highly sophisticated codes, you might still need to rely on trial and error (brute force) because no shortcuts are available without knowing more about the code.

--