폴라드 로 이산 로그 알고리즘

**폴라드 로 이산 로그 알고리즘**(Pollard’s rho algorithm for discrete logarithms)은 이산 로그를 계산하는 확률적 알고리즘이다.zbl=1277.94042형식=PDF 결정론적 이산 로그 알고리즘과 비슷한 기대 실행 시간을 가지지만, 적절한 순환 탐지 알고리즘을 사용하는 경우 상수 공간 또는 선형 공간만을 사용한다.
# 정의
아벨 군 G 및 g,h\in G 및 집합의 분할 G=S_0\sqcup S_1\sqcup S_2에 대하여, 함수 f_{g,h,\vec S}\colon G\to G와 e_{\vec S},e'_{\vec S}\colon G\times\mathbb Z\to\mathbb Z를 다음과 같이 정의하자. :f(x)=\begin{cases} gx & x\in S_0 \\\ x^2 & x\in S_1 \\\ hx & x\in S_2 \end{cases} :e(x,k)=\begin{cases} k+1 & X\in S_0 \\\ 2k & X\in S_1 \\\ k & X\in S_2 \end{cases} :e'(x,k)=\begin{cases} k & X\in S_0 \\\ 2k & X\in S_1 \\\ k+1 & X\in S_2 \end{cases} (대략, 이는 만약 x=g^ah^b\in\langle g,h\rangle이라면 f(x)=g^{e(x,a)}h^{e'(x,b)}이도록 정의한 것이다.) 이제, 임의의 유한군 G에 대하여, 적절한 G의 분할 (S_{0,G},S_{1,G},S_{2,G})를 잡자. 이는 크기가 대략 같은 세 집합으로 구성되어야 하며, 임의의 군 원소가 어떤 집합에 속하는지 쉽게 알 수 있어야 한다. 보통 다음과 같은 분할 (S_{0,G},S_{1,G},S_{2,G})를 사용한다. * g\in G를 나타내는 비트 문자열을 이진법 전개로 하는 정수를 3으로 나눈 나머지가 i\in\\{0,1,2\\}라면, g\in S_i이다. (\mathbb Z/(p))^\times만을 고려하는 경우, 다음과 같은 분할을 사용할 수 있다. * 만약 ip/3\le g<(i+1)p/3이라면, g의 합동류는 S_i에 속한다. 폴라드 보행과 소박한(naive) 순환 탐지 알고리즘을 사용하는 **폴라드 로 이산 로그 알고리즘**는 크기가 n인 순환군 G와 그 생성 원소 g\in G와 임의의 원소 h\in G가 주어졌을 때, 이산 로그 \log_gh\in\mathbb Z/n을 다음과 같이 계산한다. # 다음을 반복한다. ## 무작위 원소 a_0,b_0\in\mathbb Z/n을 고르고, x_0\leftarrow g^{a_0}h^{b_0}으로 놓는다. ## j=1,2,3,\dots에 대하여, ### x_j\leftarrow f(x_{j-1}), a_j\leftarrow e(x_{j-1},a_{j-1}), b_j\leftarrow e'(x_{j-1},b_{j-1})로 놓는다. ### 만약 x_i=x_j인 i가 존재한다면, 다음 단계로 넘어간다. ## 만약 b_j-b_i가 \mathbb Z/n의 가역원이라면 (a_i-a_j)/(b_j-b_i)\in\mathbb Z/n을 반환한다.
## 반복 함수의 개선
임의의 아벨 군 G 및 g,h\in G 및 m_1,\dots,m_r,n_1,\dots,n_r\in\mathbb Z/n 및 양의 정수 r 및 함수 \operatorname{hash}\colon G\to\\{1,\dots,r\\}에 대하여, 함수 f_{g,h,\vec m,\vec n,\operatorname{hash\colon G\to G와 e_{\vec m,\vec n,\operatorname{hash,e'_{\vec m,\vec n,\operatorname{hash\colon G\times\mathbb Z\to\mathbb Z를 다음과 같이 정의하자. :f(x)=g^{m_{\operatorname{hash}(x)h^{n_{\operatorname{hash}(x)x :e(x,k)=k+m_{\operatorname{hash}(x)} :e'(x,k)=k+n_{\operatorname{hash}(x)} (그렇다면, 만약 x=g^ah^b라면 f(x)=g^{e(x,a)}h^{e'(x,b)}이다.) 이 경우, 임의의 x_0\in G에 대하여, 열 x_0,f(x_0),f(f(x_0)),\dots을 **테스케 r-더하기 보행**(Teske’s r-adding walk)이라고 한다. 이제, 임의의 유한군 G 및 양의 정수 r에 대하여, 적절한 해시 함수 \operatorname{hash}_{G,r}\colon G\to\\{1,\dots,r\\}를 잡자. 보통, 다음과 같이 정의한다. * \operatorname{hash}(g)는 g를 나타내는 비트 문자열을 이진법 전개로 하는 정수를 r로 나눈 나머지이다. 이제, 적절한 양의 정수 r를 잡자. 만약 r가 너무 작다면, 이는 무작위성을 잘 모의하지 못한다. 폴라드가 사용한 보행은 r=3에 해당하며, 이는 너무 작다. 경험적으로 r\approx20이 잘 작동한다. 테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 **폴라드 로 이산 로그 알고리즘**은 크기가 n인 순환군 G와 그 생성 원소 g\in G와 임의의 원소 h\in G가 주어졌을 때, 이산 로그 \log_gh\in\mathbb Z/n을 다음과 같이 계산한다. # 다음을 반복한다. ## 무작위 원소 m_1,\dots,m_r,n_1,\dots,n_r\in\mathbb Z/n을 고르고, 각 i=1,\dots,r에 대하여 M_i\leftarrow g^{m_i}h^{n_i}로 놓는다. ## 무작위 원소 a_0,b_0\in\mathbb Z/n을 고르고, x_0\leftarrow g^{a_0}h^{b_0}으로 놓는다. ## j=1,2,3,\dots에 대하여, ### x_j\leftarrow f(x_{j-1}), a_j\leftarrow e(x_{j-1},a_{j-1}), b_j\leftarrow e'(x_{j-1},b_{j-1})로 놓는다. ### 만약 x_i=x_j인 i가 존재한다면, 다음 단계로 넘어간다. ## 만약 b_j-b_i가 \mathbb Z/n의 가역원이라면 (a_i-a_j)/(b_j-b_i)\in\mathbb Z/n을 반환한다.
## 순환 탐지 알고리즘의 개선

### 플로이드 순환 탐지 알고리즘
테스케 r-더하기 보행과 플로이드 순환 탐지 알고리즘을 사용하는 **폴라드 로 이산 로그 알고리즘**은 크기가 n인 순환군 G와 그 생성 원소 g\in G와 임의의 원소 h\in G가 주어졌을 때, 이산 로그 \log_gh\in\mathbb Z/n을 다음과 같이 계산한다. # 다음을 반복한다. ## 무작위 원소 m_1,\dots,m_r,n_1,\dots,n_r\in\mathbb Z/n을 고르고, 각 i=1,\dots,r에 대하여 M_i\leftarrow g^{m_i}h^{n_i}로 놓는다. ## 무작위 원소 a,b\in\mathbb Z/n을 고르고, x\leftarrow g^ah^b, a'\leftarrow a, b'\leftarrow b, x'\leftarrow x로 놓는다. ## 다음을 반복한다. ### x\leftarrow f(x), a\leftarrow e(x,a), b\leftarrow e'(x,b)로 놓는다. ### x'\leftarrow f(x'), c\leftarrow e(x',a'), d\leftarrow e'(x',b')로 놓는다. ### x'\leftarrow f(x'), c\leftarrow e(x',a'), d\leftarrow e'(x',b')로 놓는다. ### 만약 x=x'라면, 다음 단계로 넘어간다. ## 만약 b'-b가 \mathbb Z/n의 가역원이라면 (a-a')/(b'-b)\in\mathbb Z/n을 반환한다.
### 구별점 방법
크기가 n인 임의의 유한군 G 및 함수 \operatorname{hash}\colon G\to\\{0,1\\}^{\lfloor\ln n\rfloor} 및 양의 정수 k에 대하여, 적절한 함수 B_{G,\operatorname{hash},k}\colon G\to\\{0,1\\}를 잡자. 이는 흔히 다음과 같이 정의한다. * 만약 \operatorname{hash}(g)의 k개 최하위 비트가 모두 0이라면, B(g)=1이다. 이 경우, B^{-1}(1)의 원소를 구별점(distinguished point)이라고 부른다. 이제, 적절한 함수 \theta\colon\mathbb Z^+\to\mathbb R를 잡자. 예를 들어, :\theta(n)=\ln^cn/\sqrt n 으로 놓을 수 있다. 여기서 c는 적절한 양의 실수(예를 들어, c\approx10)이다. c가 클수록 기대 시간은 줄고 기대 공간은 는다. 테스케 r-더하기 보행과 구별점 방법을 사용하는 **폴라드 로 이산 로그 알고리즘**은 크기가 n인 순환군 G와 그 생성 원소 g\in G와 임의의 원소 h\in G가 주어졌을 때, 이산 로그 \log_gh\in\mathbb Z/n을 다음과 같이 계산한다. # 다음을 반복한다. ## 무작위 함수 \operatorname{hash}\colon G\to\\{0,1\\}^{\lfloor\ln n\rfloor}을 고른다. k\leftarrow\lceil\log_2\theta(n)\rceil, t\leftarrow0으로 놓는다. ## 다음을 반복한다. ### 만약 k=0이라면, 이 순환을 빠져나온다. ### 만약 t=\lfloor \pi n/2\rfloor라면, k\leftarrow k-1, t\leftarrow0으로 놓는다. ### t\leftarrow t+1로 놓는다. ### 무작위 원소 m_1,\dots,m_r,n_1,\dots,n_r\in\mathbb Z/n을 고르고, 각 i=1,\dots,r에 대하여 M_i\leftarrow g^{m_i}h^{n_i}로 놓는다. ### 무작위 원소 a_0,b_0\in\mathbb Z/n을 고르고, x_0\leftarrow g^{a_0}h^{b_0}으로 놓는다. ### D\leftarrow\varnothing으로 놓는다. ### j=1,2,3,\dots에 대하여, #### x_j\leftarrow f(x_{j-1}), a_j\leftarrow e(x_{j-1},a_{j-1}), b_j\leftarrow e'(x_{j-1},b_{j-1})로 놓는다. #### 만약 B(x_j)=1이라면, ##### 만약 x_i=x_j인 x_i\in D가 존재한다면, ###### 만약 b_j-b_i가 \mathbb Z/n의 가역원이라면, (a_i-a_j)/(b_j-b_i)\in\mathbb Z/n을 반환한다. ###### 만약 b_j-b_i가 \mathbb Z/n의 가역원이 아니라면, 이 순환(“7. j=1,2,3,\dots에 대하여”)를 빠져나온다. ##### 만약 x_i=x_j인 x_i\in D가 존재하지 않는다면, D\leftarrow D\cup\\{(a_j,b_j,x_j)\\}로 놓는다.
# 복잡도
폴라드 로 이산 로그 알고리즘의 모든 형태는 거의 확실하게(즉, 확률 1로) 종료하며, 종료하는 경우 옳은 이산 로그 값을 반환한다. 따라서, 폴라드 로 이산 로그 알고리즘은 라스베이거스 알고리즘이다. f\colon G\to G와 x_0\in G가 이산 균등 분포를 따른다고 가정하자. 즉, x_0,x_1,x_2,\dots는 이산 균등 분포를 따르는 독립 확률 변수들의 열이다. 그렇다면, 첫 순환 x_i,x_{i+1},\dots,x_{j-1}의 시작점 i와 순환의 주기 j-i와 두 번째 순환의 시작점 j의 기댓값은 다음과 같이 점근적으로 근사할 수 있다. :\operatorname E(i)=\operatorname E(j-i)\sim\sqrt{\pi n/8}\approx0.63\sqrt n :\operatorname E(j)\sim\sqrt{\pi n/2}\approx1.25\sqrt n 소박한 순환 탐지 알고리즘을 사용하는 경우, 반복 횟수는 j번이며, 매 회 반복마다 1회 군 연산을 사용하고 1개 군 원소를 추가 저장한다. 따라서, 기대 시간 복잡도는 O(\sqrt n)번 군 연산이며, 기대 공간 복잡도는 O(\sqrt n)개 군 원소이다. 플로이드 순환 탐지 알고리즘을 사용하는 경우, 기대 반복 횟수는 {}\sim\sqrt{9\pi n/32}\approx0.94\sqrt n이며, 매 회 반복마다 3회 군 연산을 사용하며, 2개의 군 원소만을 비교하므로 군 원소를 추가 저장할 필요가 없다. 따라서, 기대 시간 복잡도는 O(\sqrt n)번 군 연산이며, 공간 복잡도는 O(1)개 군 원소이다. 구별점 방법을 사용하는 경우, 기대 반복 횟수는 {}\sim\sqrt{\pi n/2}+1/\theta이며, 매 회 반복마다 1회 군 연산을 사용하고 군 원소가 구별점인 경우에만 추가 저장한다. 이 경우, 기대 시간 복잡도는 O(\sqrt{\pi n/2}+1/\theta)번 군 연산, 기대 공간 복잡도는 O(\theta\sqrt n)개 군 원소이다. 특히, \theta=\ln^cn/\sqrt n인 경우 기대 반복 횟수는 {}\sim\sqrt{\pi n/2}, 기대 시간 복잡도는 O(\sqrt n)번 군 연산, 기대 공간 복잡도는 O(\ln^cn)이다. 물론, 실제 알고리즘에서 사용하는 보행은 진정한 무작위 보행이 아니며, 실제 알고리즘의 성능은 경험적으로 무작위 가정 아래 성능에 못 미친다. 예를 들어, 다음과 같은 경험적인 추정들이 존재한다. * G가 (\mathbb Z/(p))^\times의 소수 크기 부분군일 때, ** 폴라드 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, \operatorname E(j)\sim\approx1.55\sqrt n ** 테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, \operatorname E(j)\sim\approx1.27\sqrt n * G가 유한체 위의 타원 곡선의 부분군일 때, ** 폴라드 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, \operatorname E(j)\sim\approx1.60\sqrt n ** 테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, \operatorname E(j)\sim\approx1.29\sqrt n