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

**폴라드 로 이산 로그 알고리즘**()은 이산 로그를 계산하는 확률적 알고리즘이다. 결정론적 이산 로그 알고리즘과 비슷한 기대 실행 시간을 가지지만, 적절한 순환 탐지 알고리즘을 사용하는 경우 상수 공간 또는 선형 공간만을 사용한다.

## 정의
아벨 군 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이라면, g의 합동류는 S_i에 속한다.

폴라드 보행과 소박한() 순환 탐지 알고리즘을 사용하는 **폴라드 로 이산 로그 알고리즘**는 크기가 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-더하기 보행**()이라고 한다.

이제, 임의의 유한군 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)의 원소를 구별점()이라고 부른다.

이제, 적절한 함수 \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

## 참고 문헌


## 외부 링크
* 

분류:수론 알고리즘