Introduction and Proof of Baby-step Giant-step Algorithm (BSGS)

시작하기에 앞서, Baby-step Giant-step Algorithm(BSGS Algorithm)을 이해하기 위해 필요한 이산 로그 문제(Discrete Logarithm Problem, DLP)에 대해 간단히 설명하겠다.

일반적으로 양의 실수 집합에서 정의되는 로그(Logarithm)는 $a^x=b$에서 $x$를 의미한다. 이와 유사한 의미로, 한 원소를 곱셈의 항등원에 곱하는 연산을 몇 번 적용해야 하는지를 의미한다. 특히 $\mathbb{Z}/p\mathbb{Z}$에 대한 이산 로그 문제는 다음과 같이 정의할 수 있다. 이때 $p$는 소수이다.

 

$\mathbb{Z}/p\mathbb{Z}$의 원소 $b,n$에 대해 $b^x\equiv n\text{ }(\text{mod }p)$를 만족하는 $0$ 이상 $\phi(p)=p-1$ 미만의 정수 $x$를 찾아라.

 

BSGS Algorithm은 위와 같은 $\mathbb{Z}/p\mathbb{Z}$에서의 DLP를 $O(\sqrt{p}\lg p)$의 시간복잡도에 해결할 수 있는 알고리즘이다. 완전탐색을 제외한 DLP 알고리즘 중 간단한 편에 속한다. 알고리즘의 pseudo code를 소개하자면 다음과 같다.

 

1. $0$ 이상 $\lceil\sqrt{p}\rceil$ 미만인 모든 정수 $c$에 대해 $b^c\mod p$를 집합 $S$에 삽입한다. (Baby-step)
2. $1$ 이상 $\lceil\sqrt{p}\rceil$ 미만인 모든 정수 $k$에 대해 $n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$를 계산하고, 이 값이 $S$에 있는지 확인한다. 있다면 $b^c\mod p = n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$를 만족하는 $c$를 찾는다. (Giant-step)
3. $x=k\lceil\sqrt{p}\rceil+c$를 결과로써 반환한다.

---

BSGS Algorithm의 정당성 증명

임의의 $p$ 미만의 음이 아닌 정수는 $\lceil\sqrt{p}\rceil$ 미만이고 음이 아닌 두 정수 $a,b$에 대해 $a\lceil\sqrt{p}\rceil+b$ 꼴로 표현할 수 있다. $x$는 존재할 때 0 이상 $p-1$ 미만인 것이 존재한다는 것이 보장되므로, 모든 존재하는 지수는 $a\lceil\sqrt{p}\rceil+b$ 꼴로 표현 가능하다는 사실을 기억하자.

2.에서 $n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$가 $S$에 존재한다면, $b^c\equiv n\times b^{-k\lceil\sqrt{p}\rceil}\text{ }(\text{mod }p)$를 만족하는 $\lceil\sqrt{p}\rceil$ 미만의 음이 아닌 정수 $c$가 존재한다는 것을 알 수 있다.

이 식의 양변에 $b^{k\lceil\sqrt{p}\rceil}$를 곱하면 $n\equiv b^{k\lceil\sqrt{p}\rceil+c}\text{ }(\text{mod }p)$을 얻는다. 따라서 $x=k\lceil\sqrt{p}\rceil+c$를 얻을 수 있다.

---

BSGS Algorithm의 시간복잡도 증명

분할정복을 이용해 거듭제곱을 계산하면 $a^b\mod p$는 $O(\lg b)$에 계산 가능하다. 또한 잘 구현된 집합 구현체를 이용하면 원소의 존재 여부를 집합의 크기 $n$에 대해 $O(\lg n)$에 판단 가능하다.

따라서 1.에서는 $\lceil\sqrt{p}\rceil\times O(\lg p)=O(\sqrt{p}\lg p)$의 시간이 소요된다.

2.에서는 거듭제곱과 모듈로 역원을 한 번 계산하고 집합에의 포함 여부를 판별하는데 각각 $O(\lg p)$의 시간이 소요되므로 총 $O(\sqrt{p}\lg p)$의 시간이 소요된다.

결론적으로 BSGS Algorithm은 $O(\sqrt{p}\lg p)$의 시간에 이산 로그 문제를 해결할 수 있음을 확인할 수 있다.

 

---

BSGS Algorithm의 구현

이산 로그를 구현한 대부분의 잘 알려진 구현체는 BSGS보다 빠른 시간에 동작하는 pollard-rho algorithm, 혹은 pohlig-hellman algorithm 등을 구현한다. 따라서 이들을 사용 가능하다면 사용하기를 권장한다. 아래는 C++로 구현된 BSGS algorithm이다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll ipow(ll x,ll n,ll p){
    if(n==0)return 1;
    if(n==1)return x%p;
    if(n==2)return (x%p)*(x%p)%p;
    ll k=ipow(x*x%p,n/2,p);
    if(n%2==1)k=k*x%p;
    return k;
}

ll discrete_log(ll n,ll b,ll p){
    set<ll> s;
    ll k=ceil(sqrt(p));
    ll binvk=ipow(ipow(b,k,p),p-2,p);//by fermat's little theorem
    ll t;

    //baby-step
    t=1;
    for(ll i=0;i<k;i++){
        s.insert(t);
        t*=b;
        t%=p;
    }
    
    //giant-step
    t=1;
    for(ll i=0;i<k;i++){
        ll x=n*t%p;
        if(s.find(x)!=s.end()){
            t=1;
            for(ll j=0;j<k;j++){
                if(t==x){
                    return i*k+j;
                }
                t*=b;
                t%=p;
            }
        }
        t*=binvk;
        t%=p;
    }
    return -1;
}