이산 로그

이산 로그 (Discrete Logarithm) 의 정의는 다음과 같습니다.

법 $n$에 대한 원시근 $g$와 $\gcd(a, n) = 1$ 이고 $g^{x} \equiv a \pmod{n}$인 정수 $x = \operatorname{ind}_g a$를 이산 로그라 한다.

$\gcd(a, b)$는 최대공약수 입니다.

이산로그를 $a = g^x \pmod{n}$를 $O(\sqrt{n})$에 구하는 방법이 알려져있습니다. ($O(f(n))$은 란다우 표기법 )
1. $m = \lceil\sqrt{n}\rceil$을 정의한다.
2. 리스트 A = [$(a \times g^{-i}, i)$ for i in range(m)] 을 정의한다.
3. 리스트 B = [$(g^{mj}, mj)$ for j in range$\left(\lceil \frac{n}{m} \rceil + 1\right)$] 을 정의한다.
4. $A[i][0] = B[j][0]$이면, $\operatorname{ind}_{g} a = A[i][1] + B[j][1]$ 이다.
$a \times g^{-i} \equiv g^{mj} \pmod{n}$이면 $a \equiv g^{mj + i} \pmod{n}$이므로 가능한 알고리즘 입니다.