이산 로그
이산 로그 (Discrete Logarithm) 의 정의는 다음과 같습니다.
법 n에 대한 원시근 g와 gcd 이고 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}이므로 가능한 알고리즘 입니다.