Skip to content

Discrete Logarithm

Definition

Prerequisite: Order and Primitive Root.

The definition of discrete logarithm is similar to that of ordinary logarithm. Let \(m\) be a positive integer with a primitive root, and let \(g\) be one of its primitive roots. For an integer \(a\) satisfying \((a,m)=1\), we know there exists a unique integer \(0\leq k<\varphi(m)\) such that

\[ g^k\equiv a\pmod m \]

We call this \(k\) the discrete logarithm of \(a\) to base \(g\) modulo \(m\), denoted as \(k=\operatorname{ind}_g a\), or simply \(\operatorname{ind} a\) when no confusion arises.

Clearly, \(\operatorname{ind}_g 1=0\) and \(\operatorname{ind}_g g=1\).

Properties

The properties of discrete logarithm are also similar to those of ordinary logarithm.

Properties

Let \(g\) be a primitive root modulo \(m\), and \((a,m)=(b,m)=1\). Then:

  1. \(\operatorname{ind}_g(ab)\equiv\operatorname{ind}_g a+\operatorname{ind}_g b\pmod{\varphi(m)}\)

    Consequently, \((\forall n\in\mathbf{N}),~~\operatorname{ind}_g a^n\equiv n\operatorname{ind}_g a\pmod{\varphi(m)}\)

  2. If \(g_1\) is also a primitive root modulo \(m\), then \(\operatorname{ind}_g a\equiv\operatorname{ind}_{g_1}a \cdot \operatorname{ind}_g g_1\pmod{\varphi(m)}\)

  3. \(a\equiv b\pmod m\iff \operatorname{ind}_g a=\operatorname{ind}_g b\)
Proof
  1. \(g^{\operatorname{ind}_g(ab)}\equiv ab\equiv g^{\operatorname{ind}_g a}g^{\operatorname{ind}_g b}\equiv g^{\operatorname{ind}_g a+\operatorname{ind}_g b}\pmod m\)

  2. Let \(x=\operatorname{ind}_{g_1}a\), then \(a\equiv g_1^x\pmod m\). Also let \(y=\operatorname{ind}_g g_1\), then \(g_1\equiv g^y\pmod m\).

    Thus \(a\equiv g^{xy}\pmod m\), i.e., \(\operatorname{ind}_g a\equiv xy\equiv\operatorname{ind}_{g_1}a \cdot \operatorname{ind}_g g_1\pmod{\varphi(m)}\)

  3. Note that

    \[ \begin{aligned} \operatorname{ind}_g a=\operatorname{ind}_g b&\iff \operatorname{ind}_g a\equiv\operatorname{ind}_g b\pmod{\varphi(m)}\\ &\iff g^{\operatorname{ind}_g a}\equiv g^{\operatorname{ind}_g b}\pmod m\\ &\iff a\equiv b\pmod m \end{aligned} \]

Baby-step Giant-step Algorithm

Currently, there is no polynomial-time classical algorithm for the discrete logarithm problem (the input size of the discrete logarithm problem is the number of bits of the input data). In cryptography, based on this fact, many asymmetric encryption algorithms have been designed, such as Ed25519.

In competitive programming, BSGS (baby-step giant-step) is commonly used to solve the discrete logarithm problem. Formally, for \(a,b,m\in\mathbf{Z}^+\), the algorithm can solve

\[ a^x \equiv b \pmod m \]

in \(O(\sqrt{m})\) time, where \(a\perp m\). The solution \(x\) satisfies \(0 \le x < m\). (Note that \(m\) is not necessarily prime.)

Algorithm Description

Let \(x = A \left \lceil \sqrt m \right \rceil - B\), where \(0\le A,B \le \left \lceil \sqrt m \right \rceil\). Then \(a^{A\left \lceil \sqrt m \right \rceil -B} \equiv b \pmod m\). After slight transformation, we have \(a^{A\left \lceil \sqrt m \right \rceil} \equiv ba^B \pmod m\).

We know \(a\) and \(b\), so we can first compute all possible values of \(ba^B\) on the right-hand side by enumerating \(B\), store them in a hash/map, then compute \(a^{A\left \lceil \sqrt m \right \rceil}\) for each \(A\), and check if there is an equal \(ba^B\). Thus we can obtain all \(x\) as \(x=A \left \lceil \sqrt m \right \rceil - B\).

Note that \(A\) and \(B\) are both less than \(\left \lceil \sqrt m \right \rceil\), so the time complexity is \(\Theta\left (\sqrt m\right )\), with an extra \(\log\) factor if using map.

Why require \(a\) and \(m\) to be coprime?

Note that we find \(A\) and \(B\). We need to ensure that from \(a^{A\left \lceil \sqrt m \right \rceil} \equiv ba^B \pmod m\) we can deduce \(a^{A\left \lceil \sqrt m \right \rceil -B} \equiv b \pmod m\). The latter is obtained by dividing both sides of the former by \(a^B\), so we must have \(a^B \perp m\), i.e., \(a\perp m\).

Extended BSGS Algorithm

For \(a,b,m\in\mathbf{Z}^+\), solve

\[ a^x\equiv b\pmod m \]

where \(a\) and \(m\) are not necessarily coprime.

When \((a, m)=1\), \(a\) has a multiplicative inverse modulo \(m\), so the BSGS algorithm can be used. Therefore, we try to make them coprime.

Specifically, let \(d_1=(a, m)\). If \(d_1\nmid b\), then the original equation has no solution. Otherwise, we divide both sides by \(d_1\), obtaining

\[ \frac{a}{d_1}\cdot a^{x-1}\equiv \frac{b}{d_1}\pmod{\frac{m}{d_1}} \]

If \(a\) and \(\frac{m}{d_1}\) are still not coprime, we divide again. Let \(d_2=\left(a, \frac{m}{d_1}\right)\). If \(d_2\nmid \frac{b}{d_1}\), the equation has no solution; otherwise, divide by \(d_2\) to get

\[ \frac{a^2}{d_1d_2}\cdot a^{x-2}≡\frac{b}{d_1d_2} \pmod{\frac{m}{d_1d_2}} \]

Similarly, continue this process until \(a\perp \dfrac{m}{d_1d_2\cdots d_k}\).

Let \(D=\prod_{i=1}^kd_i\). Then the equation becomes:

\[ \frac{a^k}{D}\cdot a^{x-k}\equiv\frac{b}{D} \pmod{\frac{m}{D}} \]

Since \(a\perp\dfrac{m}{D}\), we have \(\dfrac{a^k}{D}\perp \dfrac{m}{D}\). Thus \(\dfrac{a^k}{D}\) has an inverse modulo \(\dfrac{m}{D}\). Move it to the right-hand side, and we have an ordinary BSGS problem. Solve for \(x-k\), then add \(k\) to get the solution to the original equation.

Note that solutions less than or equal to \(k\) are not excluded. Therefore, before eliminating factors, perform an \(\Theta(k)\) enumeration to directly check \(a^i\equiv b \pmod m\), which avoids this situation.

Exercises

Parts of this page and the code are translated from the blog post Дискретное извлечение корня and its English translation Discrete Root. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.

References

  1. Discrete logarithm - Wikipedia
  2. Pan Chengdong, Pan Chengbiao. Elementary Number Theory.
  3. Feng Keqin. Elementary Number Theory and Its Applications.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用