1. Introduction

In cryptographic circles, the discrete logarithm remains a topic of intrigue. Although the discrete logarithm can be computed in specific scenarios, finding efficient solutions for general cases remains a formidable challenge. Notably, some algorithms tackle this problem and hold paramount significance in public-key cryptography, exemplified by systems like Elgamal [1]. This research endeavors to illuminate the intricacies of the Shanks' Babystep-Giantstep Algorithm and the Pohlig-Hellman Discrete Logarithm Algorithm. Both stand as robust solutions to the Discrete Logarithm Problem. To lay a foundation, it's imperative first to delve into fundamental concepts such as order and primitive root. By understanding these, one can better appreciate their applications to the focal problem. The crux of this study revolves around the operational mechanics of these two algorithms, exploring their methodologies in solving the Discrete Logarithm Problem, and discerning their connections to foundational tenets of elementary number theory.

2. Foundational Theories of Orders and Primitive Roots

2.1. Order

Definition 1: Let \( m∈{N^{+}}, and a∈{N^{+}} with (a, m)=1 \) , the order (or the multiplicative order) of a modulo m is the smallest positive integer r satisfying \( {a^{r}}≡1 (mod m) \) [2].

The order of a modulo m is always written as \( {δ_{m}}(a) \) or \( {ord_{m}}(a) \) [3]. Also, order always exists due to the Euler’s Theorem: Let \( m∈{N^{+}}, and a∈{N^{+}} with (a,m)=1 \) , then \( {a^{φ(m)}}≡1 (mod m) \) [4]. Euler’s Theorem is too basic so the proof is skipped here. The Euler’s Theorem says that for \( m∈{N^{+}}, and a∈{N^{+}} with (a,m)=1 \) , the set {r \( ∈{N^{+}} \) | \( {a^{r}}≡1(mod m) \) } is not empty so this set must have the smallest element, which is the (multiplicative) order, due to the Well-Ordering Principle.

Proposition 1: Let \( m∈{N^{+}}, and a∈{N^{+}} with (a,m)=1 \) , \( k∈{N^{+}} \) , then \( {a^{k}}≡1 (mod m) \) if and only if \( {δ_{m}}(a) | k \) [5].

Proof: If \( {a^{k}}≡1(mod m), \) let, then \( {a^{r}}≡1 (mod m) \) .

By Division Algorithm, there exists q, t \( ∈{N^{+}} \) with 0 \( ≤t \) <r-1 such that k=qr+t.

This means t=k-qr.

Also, notice that \( {a^{qr}}≡1 (modm) \) .

Thus, \( {a^{t}}={a^{k-qr}}≡{a^{k-qr}}{a^{qr}}={a^{k}}≡1(modm) \) .

But r is the smallest positive integer satisfying \( {a^{r}}≡1 (mod m) \) and t<r, so it means t=0

So k=qr, which means r|k.

Therefore, \( {δ_{m}} \) (a)|k.

On the other hand, if \( {δ_{m}}(a) | k \) , so r |k, thus there exists \( l∈{N^{+}}, \) such that k= lr.

Since \( {a^{r}}≡1 (mod m) \) , thus, \( {a^{k}}={a^{lr}}={({a^{r}})^{l}}≡1 (mod m) \) .

Hence, \( {a^{k}}≡1 (mod m) \) if and only if \( {δ_{m}}(a) | k \) .

By Proposition1 and Euler’s Theorem, a result can be got easily:

Corollary 1: Let \( m∈{N^{+}}, and a∈{N^{+}} with (a,m)=1 \) , then \( {δ_{m}}(a) | φ(m) \) .

Proof: By Euler’s Theorem, \( {a^{φ(m)}}≡1 (mod m) \) .

By Proposition1 and let k= \( φ(m), \) \( {δ_{m}}(a) | φ(m) \) .

So the Corollary1 holds.

Next, another important result about (multiplicative) order will be introduced.

Proposition 2: Let \( m∈{N^{+}}, and a∈{N^{+}} with (a,m)=1 \) , then a, \( {a^{2}},…, {a^{r}} \) are distinct modulo m, where r= \( {δ_{m}} \) (a) [6].

Proof: Suppose \( ∃1≤i \lt j≤r, s.t. {a^{i}}≡{a^{j}}(mod m), then {a^{i}}({a^{j-i}}-1)≡0(mod m) \) .

This means m | \( {a^{i}}({a^{j-i}}-1) \) .

Since (a, m) =1, so ( \( {a^{i}} \) , m) =1.

Thus, m | \( {a^{j-i}}-1 \) , which means \( {a^{j-i}}≡1(mod m) \) .

Hence, r | j-i, so j-i \( ≥r \) .

But \( 1≤i \lt j≤r \) , which says j-i<r, it is a contradiction.

Hence, a, \( {a^{2}},…, {a^{r}} \) are distinct modulo m.

Proposition 2: Let \( m∈{N^{+}}, and a∈{N^{+}} with (a,m)=1, \) let \( {δ_{m}} \) (a) = r, then \( {δ_{m}} \) ( \( {a^{n}} \) ) = \( \frac{r}{(r,n) } (n∈{N^{+}}) \) [7].

Proof: Let \( {δ_{m}} \) ( \( {a^{n}} \) )= \( l \) , then \( {a^{nl}}≡1(mod m) \) .

By Proposition1, r | \( l \) n, so \( ∃ q∈{N^{+}},s.t. nl=rq \)

Thus, \( \frac{ln}{(r,n) } \) = \( \frac{r}{(r,n) }q \) .

So \( \frac{r}{(r,n) } | \) \( \frac{ln}{(r,n) } \) .

Notice that ( \( \frac{r}{(r,n) } \) , \( \frac{n}{(r,n) })=1 \) .

Hence, \( \frac{r}{(r,n) } | \) \( \frac{l}{(r,n) } \) ., so \( \frac{r}{(r,n) }| l \) .

On the other hand, notice that \( {{(a^{n}})^{\frac{r}{(r,n)}}}=({{a^{r}})^{\frac{n}{(r,n)}}}≡1(mod m) \) .

By Proposition1, \( l| \frac{r}{(r,n)} \) .

Therefore, \( l=\frac{r}{(r,n) } \) .

Hence, \( {δ_{m}} \) ( \( {a^{n}} \) )= \( \frac{r}{(r,n) } \) .

2.2. Primitive root

Definition 2: Let m \( ∈{N^{+}}(m≥2). \) The primitive root mod m is an integer g, such that \( {δ_{m}} \) (g) = \( φ(m) and (g,m)=1 \) [8].

By Definition 2 and Proposition2, it is easy to get the following corollary.

Corollary 2: Let m \( ∈{N^{+}}(m≥2), \) a be an primitive root of m, then the list a, \( {a^{2}},…, {a^{φ(m)}} \) picks up every element of \( Z_{m}^{*} \) .

What is worth saying is that the corollary2 is also another version of the definition of primitive root [7].

The most important result about primitive root is the Primitive Root Theorem.

Theorem 1(Primitive Root Theorem): Let p be a prime number, then \( Z_{p}^{*} \) has a primitive root.

Proof: [Lemma]: Let p be a prime number and a, b \( ∈Z_{p}^{*} \) , denote \( {δ_{p}}(a)=k, and {δ_{p}}(b)=l. If (k,l)=1 , then {δ_{p}}(ab)=kl. \)

[Proof of Lemma]: Let \( {δ_{p}}(ab)=r \) .

Since \( {(ab)^{kl}}={a^{kl}}{b^{kl}}=({{a^{k}})^{l}}({{b^{l}})^{k}}≡1 (mod p) \) .

By Proposition 1, \( r|kl \) .

The following is to prove \( k|r and l|r \) .

Because \( ({{a^{r}})^{k}}={a^{rk}}=({{a^{k}})^{r}}≡1(modp), and ({{b^{r}})^{l}}={b^{rl}}=({{b^{l}})^{r}}≡1 (modp) \) .

Also, notice that \( ({{a^{r}})^{l}}≡({{a^{r}})^{l}} ({{b^{r}})^{l}}= \) \( ({{ab^{r}})^{l}}≡1 (mod p) \) .

Thus, \( k|rl \) , combined with \( (k,l)=1, so k|r \) .

Similarly, \( l|r \) .

Since \( (k,l)=1, this leads to kl | r \) .

Hence, \( kl=r \) .

Therefore, \( {δ_{p}}(ab)=kl \) .

[Back to Primitive Root Theorem]: For any a in \( Z_{p}^{*} \) , then (a, p) =1.

By Fermart’s Little Theorem, \( {a^{p-1}}≡1 (mod p) \) .

By Proposition 1, \( {δ_{p}}(a)|p-1 \) .

If \( {δ_{p}}(a)=p-1=φ(p), \) then a is the primitive root of p, the Primitive Root Theorem holds.

If \( {δ_{p}}(a) \lt p-1, \) let \( {δ_{p}}(a)=k \) , the main idea of the following part is to find some b in \( Z_{p}^{*}, \) such that the order of b modulo p is greater than the order of a.

By Proposition 2 (or Corollary 2), the list a, \( {a^{2}}, …, {a^{k}} \) can pick up all the roots of the polynomial f(x)= \( {x^{k}}-1 in Z_{p}^{*} \) , since k < p-1, so there exists c in \( Z_{p}^{*} \) and c is not in the list above.

Let \( {δ_{p}}(c)=l, if l | k , then {c^{k}}≡1(mod p) \) , thus \( l does not divide k since c is not the root of f \)

Consider the prime factorization of \( k and l, \) there must be an unique prime number q who appears more often in \( l \) than it appears in k, in other words, \( {v_{q}}(l) \gt {v_{q}}(k) \) , here \( {v_{q}}(x) \) represents the power of q in the prime factorization of the positive integer \( x. \)

Let k= \( {q^{d}}{k_{1}} \) and \( l={q^{e}}{l_{1}}, where 0≤d \lt e \) and both \( {k_{1}} and {l_{1}} \) does not contain the prime factor q.

Pick b = \( {a^{{q^{d}}}}{c^{{l_{1}}}} \) , By Proposition 2, it tells that \( {δ_{p}}({a^{{q^{d}}}})=\frac{k}{(k, {q^{d}})}=\frac{k}{{q^{d}}} \) = \( {k_{1}} \) and \( {δ_{p}}({c^{{l_{1}}}})=\frac{l}{(l,{l_{1}}})=\frac{l}{{l_{1}}}={q^{e}} \) .

Now, notice that ( \( {k_{1}},{q^{e}})=1 \) .

By Lemma, \( {δ_{p}}(b)={δ_{p}}({a^{{q^{d}}}}{c^{{l_{1}}}})={δ_{p}}({a^{{q^{d}}}}){δ_{p}}({c^{{l_{1}}}})={k_{1}}{q^{e}} \gt {q^{d}}{k_{1}}=k={δ_{p}}(a) \) .

Thus, an element b in \( Z_{p}^{*} \) with greater order than a is found.

Following this way, new elements in \( Z_{p}^{*} \) with strictly increasing order can be found until find an element with the order p-1 and that element is just the primitive root.

In general, \( Z_{p}^{*} \) has a primitive root.

The Primitive Root Theorem tells that every prime number has its own primitive root but there are still many problems about primitive root cannot be solved by this theorem although it has already been an amazing result. Also, the Primitive Root Theorem can describe why the assumption of Discrete Logarithm Problem always holds and this point will be discussed in the following session of this essay. The following is to introduce several results of primitive roots without proof since it does not have a close relation to the main topic of this research.

Theorem 2: Let m \( ∈{N^{+}}(m≥2) \) . If \( Z_{m}^{*} \) has primitive roots, then the number of primitive roots in \( Z_{m}^{*} \) is \( φ(φ(m)) \) [8].

In particular, if m = p is a prime number, then \( φ(φ(m))= φ(p-1) \) , so it can tell that for any prime number p, the total number of primitive roots of p is \( φ(p-1) \) .

Theorem 3: Let m \( ∈{N^{+}}(m≥2) \) . Then \( Z_{m}^{*} \) has primitive roots if and only if m \( ∈\lbrace 2,4,{p^{k}} \) , \( 2{p^{k}}| p is an odd prime and k∈{N^{+}}\rbrace \) [9].

This result tells the structure of m that has primitive roots of m.

3. Definition and Properties of Discrete Logarithms

3.1. Discrete Logarithms and its properties

Definition 3: For a given positive integer m (m \( ≥2), \) let a \( ∈{N^{+ }} with (a,m)=1 \) , and r is the primitive root of m, x= \( {ind_{r}}a \) if \( {r^{x}}≡a (mod m) \) .

The discrete logarithms have the following 5 properties:

Proposition 3: Let p be a prime number, and a is the primitive root of p, then: \( x≡y (mod p) if and only if {ind_{a}}x≡{ind_{a}}y (mod p-1); \)

\( {ind_{a}}{a^{k}}≡k (mod p-1); \)

\( {ind_{a}}a=1; \)

\( {ind_{a}}xy≡{ind_{a}}x+{ind_{a}}y ( mod p-1) \) ;

\( {ind_{a}}{x^{k}}≡k{ind_{a}}x (mod p-1). \)

To prove these properties, an easy lemma should be used:

[Lemma]: Let p be an prime number and a is the primitive root of p. Let b, c be positive integers, then \( b≡c (mod p-1) if and only if {a^{b}}≡{a^{c}} (mod p). \)

[Proof of Lemma]: Since p is a prime number and a is primitive root of p, so \( {δ_{p}}(a)=p-1 \)

Also, By Fermat’s Little Theorem, \( {a^{p-1}}≡1 (mod p) \) (Also this holds since its order is p-1).

If \( b≡c (mod p-1), \) then there exists positive integers k, such that b-c =k(p-1)

Thus, \( {a^{b-c}}≡{a^{k(p-1)}}≡1(mod p) \) , so \( {a^{b}}≡{a^{c}}(mod p) \) .

On the other hand, if \( {a^{b}}≡{a^{c}} (mod p) \) , since (a, p) =1, so (p, \( {a^{c}})=1 \) .

Therefore, \( {a^{b-c}}≡1(mod p) \) .

Since \( {δ_{p}}(a)=p-1, \) By Proposition 1, p-1 | b-c.

Hence, \( b≡c (mod p-1) \) .

In general, \( b≡c (mod p-1) if and only if {a^{b}}≡{a^{c}} (mod p) \) .

This Lemma is proved.

By using this lemma, it is not difficult to prove the above five properties and here only the property iv) will be proved. The rest of them can just be showed by the similar way of using lemma and the direct use of definition of the discrete logarithm.

Proof of iv): Let \( l={ind_{a}}xy, \) \( {l_{1}}={ind_{a}}x, \) \( {l_{2}}={ind_{a}}y \) .

By definition, \( {a^{l}}≡xy (mod p), {a^{{l_{1}}}}≡x (mod p), {a^{{l_{2}}}}≡ y (mod p) \)

Thus, \( {a^{l}}≡xy≡{a^{{l_{1}}}}{a^{{l_{2}}}}={a^{{l_{1}}+{l_{2}}}} (mod p) \) .

By the Lemma above, \( {l_{1}}+{l_{2}}≡l (mod p-1) \) .

Hence, \( {ind_{a}}xy≡{ind_{a}}x+{ind_{a}}y ( mod p-1) \) .

4. Solution Methods for the Discrete Logarithm Problem

4.1. The Discrete Logarithm Problem

The main idea of this session is to introduce the Discrete Logarithm Problem and its solutions including.

The two main algorithms mentioned before. Firstly, the target is seeing what is Discrete Logarithm Problem.

Definition 4: The Discrete Logarithm Problem can be formulized as follows:

Given a positive integer b, and a large prime number p, let a be a primitive root of p, there exists an.

unique index i ( \( 0 ≤i≤p-1) \) , such that \( b≡{a^{i}} (mod p). \) The problem is targeted at finding the exact value of this i.

The assumption of this problem holds because such a must exist by Theorem 1 (Primitive Root Theorem). Also the index i satisfying such property must be unique since by the congruence \( b≡{ a^{i}} (mod p) \) , it is clear that (b, p) = (a, p) =1, so the remainder of b divides p is not 0 so the remainder, called r, is in \( Z_{p}^{*} \) .

By Corollary 2, the list a, \( { a^{2}},…, {a^{p-1}} \) picks up every element of \( Z_{p}^{*}=\lbrace 1,2,…,p-1\rbrace . \) This means that there must exists an unique i, such that \( r ≡ b≡ {a^{i}} (mod p). \) Also, from the argument above, it is clear that there exists a bijection between two sets \( Z_{p}^{*} \) and the set {a, \( { a^{2}},…, {a^{p-1}} \) } under modulo p.

Moreover, it is necessary that a should be the primitive root of p, otherwise, the set {a, \( { a^{2}},…, {a^{p-1}} \) } under modulo p has the competitive element so that it is impossible to encrypt it.

Another problem is that why this problem should need a big prime number. This is because if just take a small prime number, it is very easy to encrypt it so the large prime ensures the difficulty of this problem. Then, this essay will discuss about two algorithms to solve this problem: Shanks' Babystep-Giantstep Algorithm and Pohlig-Hellman Discrete Logarithm Algorithm.

4.2. Shanks' Babystep-Giantstep Algorithm

Algorithm 1(Shanks' Babystep-Giantstep Algorithm): Consider the given congruence \( b≡{ a^{x}} (mod p) \) , where p is a large prime number. Let N = p-1. The process of the algorithm is as follows:

Calculate \( n=[\sqrt[]{N} \) ] \( +1; \)

Construct the two sets A = {1, a, \( {a^{2}}, …, {a^{n}}\rbrace and B=\lbrace b, b{a^{-n}}, b{a^{-2n}}, …, b{a^{-{n^{2}}}}\rbrace \) ;

A and B actually have the same element, so there exists i, j \( ∈\lbrace 0,1,2,…,n\rbrace , such that {a^{i}}≡b{a^{-jn}} (mod p); \)

Let x = i + jn, then, x is the solution to the congruence \( b≡{ a^{x}} (mod p) \) .

It is very clear that this algorithm works and its run time is O ( \( \sqrt[]{N} \) ), which greatly decreases the run time compared with calculating each value [10].

4.3. Pohlig-Hellman Discrete Logarithm Algorithm

To introduce the Pohlig-Hellman Discrete Logarithm Algorithm, firstly, the Chinese Remainder Theorem should be reviewed.

Theorem 4 (Chinese Remainder Theorem): Let \( {m_{1}}, {m_{2}}, …, {m_{k }}∈{N^{+}} (k ≥2, k ∈{N^{+}}) \) and they are pairwise coprime. (That is, ( \( {m_{i}}, {m_{j}})=1 for all 1 \lt i≤j≤k) \) . If \( {a_{1}}, {a_{2}}, …, {a_{k}} ∈Z \) , and consider the system of congruences:

\( x≡ {a_{1}} (mod {m_{1}}) \)

\( x≡ {a_{2}} (mod {m_{2}})\ \ \ (1) \)

…

\( x≡ {a_{k}} (mod {m_{k}}) \)

This system of congruences has an unique solution modulo \( {m_{1}} {m_{2}}… {m_{k }} \) . In other words, if \( x \) = \( {x_{0}} \) is a particular solution of this system, then all the solutions are given by all the integers \( x satisfying x≡{x_{0}} (mod {m_{1}} {m_{2}}… {m_{k }}) \) [7].

This theorem is a very basic result in number theory so the proof does not present in this essay but the proof can tell the algorithm to solve the system of congruences by using Chinese Remainder Theorem.

The solutions can be given by the formula:

\( x≡{a_{1}}{M_{1}}{y_{1}}+{a_{2}}{M_{2}}{y_{2}}+…+{a_{n}}{M_{n}}{y_{n}} (mod {m_{1}} {m_{2}}… {m_{k }})\ \ \ (2) \)

Where, \( {M_{i}}= \frac{M}{{m_{i}}}, M= {m_{1}} {m_{2}}… {m_{k }}, {y_{i}}={({M_{i}})^{-1}}(mod {m_{i}}) , i=1,2, …, k. \)

Now, it is the time to present the Pohlig-Hellman Discrete Logarithm Algorithm [11]:

Algorithm 2(Pohlig-Hellman Discrete Logarithm Algorithm):

Consider the prime factorization of p-1 = \( {{p_{1}}^{{k_{1}}}}{{p_{2}}^{{k_{2}}}}…{{p_{m}}^{{k_{m}}}} \) ;

For each prime factor \( {p_{i}} (1≤i≤m), \) let x = \( {a_{0}}+{a_{1}}{p_{i}}+…+{a_{{k_{i-1}}}}{{p_{i}}^{{k_{i-1}}}} (mod {{p_{i}}^{{k_{i}}}}); \)

Let r =1, compute \( ({{a^{x}})^{\frac{p-1}{{{p_{i}}^{r}}}}} ≡ {b^{\frac{p-1}{{{p_{i}}^{r}}}}} (mod p); \) Substitute x, and expand it, notice that from the second term, all the values are since due to the Fermat’s Little Theorem, so it leads to \( {a^{{a_{0}}\frac{p-1}{{p_{i}}}}}≡ \) \( {b^{\frac{p-1}{{{p_{i}}^{r}}}}} (mod p); \) By the former steps, \( {a_{0}} \) can be computed in the run-time of O ( \( {p_{i}}) \) , then let \( {r_{1}}=r+1, \) and go back to the third step; Continue the operation above until all the \( {a_{i}}(1≤i≤m) \) are computed; For each i, a congruence can be got in the form of second step, then use the Chinese Remainder Theorem to solve x. The above two algorithms are the two main effective algorithms to solve the Discrete Logarithm Problem.

5. Conclusion

This research targeted at solving the Discrete Logarithm Problem so to introduce the algorithm to solve this famous problem, first of all, several important concepts in the field of Elementary Number Theory are introduced, including the multiplicative order and the primitive root. In addition, several important theorems are given the rigorous proof like the Primitive Root Theorem, and then this essay turn to focus on the discrete logarithm, which is the base of the Discrete Logarithm Problem, and the most important properties of discrete logarithm are introduced. Finally, this research starts to give the solutions to the Discrete Logarithm Problem but before this, it discusses about why such this problem is designed in such way and how the previous concept and theories in number theory play an important role in this problem. Then, the two main algorithms are demonstrated including the Shanks' Babystep-Giantstep Algorithm and Pohlig-Hellman Discrete Logarithm Algorithm. This research gives the effective solutions to the Discrete Logarithm Problem and they can work much more efficiently than compute each value of power, which greatly reduce the run-time of solving this problem.