2. Shanks' Algorithm

이산 로그 문제(Discrete Logarithm Problem, DLP)

어떠한 원시근 $g$와 $y$에 대해, $y \equiv g^k \pmod{p}$를 만족하는 최소의 자연수 $k$를 찾는 문제이다.

아직까지 해결하기 어려운 문제로 남아 암호학 등에 주로 사용된다.

 

대충 간략하게 브루트포스 알고리즘으로 구성하면, 다음과 같다.

def discreteLog(y, g, mod):
  cur = 1
  cnt = 0
  while True:
    cur = (cur * g) % mod
    cnt += 1
    if cur == y:
      return cnt

print(discreteLog(3, 2, 11))

 

당연하지만 mod가 더럽게 커지면, 사실상 못 쓰는 코드다.

 

Shanks' Algorithm

sqrt decomposition의 핵심 아이디어는 구간을 제곱근 길이의 제곱근 개수로 쪼개서 산술기하 최소 구하는 것처럼 만드는 것이였다.

딱히 연관성은 없지만, 제곱근으로 분할하는 아이디어를 생각해 보자.

 

어떠한 수 $p$에 대하여, $p$ 미만의 임의의 음이 아닌 정수 $x$에 대해

$0 \le a, b \le \sqrt{p}$이고 $a \sqrt{p} + b$을 만족하는 음이 아닌 정수 $a, b$가 존재한다.

 

먼저 $S = \{1, g, g^2, g^3, ... , g^{\sqrt{p} }$를 생각하자.

만약 $n \times g^{-k \sqrt{p} } \pmod{p}$가 어떤 집합 $S$에 존재한다면,

다음을 만족하는 $0 \le k, c \le \sqrt{p}$인 $k, c$가 존재한다.

 

$g^c \equiv n \times g^{-k \sqrt{p}} \pmod{p}$

이제 양변에 $g^{k \sqrt{p}}$을 곱하면, 이산 로그 $x = k\sqrt{p} + c$를 얻는다.

 

만약 해당 알고리즘으로 찾을 수 없다고 하면,

$0 \le k < p$인 모든 $k$에 대해 $g^k \equiv n$이 성립하지 않는다는 뜻이다.

그러나 원시근의 성질에 의해 이 모든 값들은 다 합동이 아니기 때문에, 모순이 발생한다.

 

시간 복잡도를 분석해 보면, 저 $g^{-k\sqrt{p}}$ $\sqrt{p}$개를 계산하는 데 시간복잡도는 $O(\log{p})$이다.

총 배열 $\sqrt{p}$개, 길이 $\sqrt{p}$의 배열에서 존재 여부 판별시간 $O( \log{p} )$

따라서 총 $O(\sqrt{p} \log{p} )$의 시간으로 구할 수 있게 된다.

 

아래는 다음 내용을 C++으로 구현한 것이다.

#include <iostream>
#include <set>
#include <cmath>

using namespace std;
typedef long long int LL;

LL mod;

LL pow(LL base, LL exp)
{
  if(exp == 0) return 1;
  if(exp == 1) return base;
  if(exp % 2 == 1) return pow(base, exp - 1) * base % mod;

  LL half = pow(base, exp / 2);
  return half * half % mod;
}

/* base ^ res = target (mod p) */
LL discreteLog(LL base, LL target)
{
  set<LL> s;
  LL sqrtP = ceil(sqrt(mod));
  LL inv_sqrtP = pow(pow(base, sqrtP), mod - 2); //FlT

  //Baby Step, 0 ~ sqrtP
  LL tmp = 1;
  for(LL i = 0; i < sqrtP; i++)
    {
      s.insert(tmp);
      tmp = (tmp * base) % mod;
    }

  //Giant Step
  tmp = 1;
  for(LL i = 0; i < sqrtP; i++)
    {
      LL cur = target * tmp % mod;
      if(s.find(cur) != s.end()) //이산로그 존재
      {
        tmp = 1;
        for(LL j = 0; j < sqrtP; j++)
          {
            if(tmp == cur) return i * sqrtP + j;
            tmp = (tmp * base) % mod;
          }
      }
      tmp = (tmp * inv_sqrtP) % mod;
    }
  return -1; //error
}