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

폴라드 로 이산 로그 알고리즘(영어: Pollard’s rho algorithm for discrete logarithms)은 이산 로그를 계산하는 확률적 알고리즘이다.^[1][2] 결정론적 이산 로그 알고리즘과 비슷한 기대 실행 시간을 가지지만, 적절한 순환 탐지 알고리즘을 사용하는 경우 상수 공간 또는 선형 공간만을 사용한다.

정의

아벨 군 ${\displaystyle G}$ 및 ${\displaystyle g,h\in G}$ 및 집합의 분할 ${\displaystyle G=S_{0}\sqcup S_{1}\sqcup S_{2}}$에 대하여, 함수 ${\displaystyle f_{g,h,{\vec {S}}}\colon G\to G}$와 ${\displaystyle e_{\vec {S}},e'_{\vec {S}}\colon G\times \mathbb {Z} \to \mathbb {Z} }$를 다음과 같이 정의하자.

${\displaystyle f(x)={\begin{cases}gx&x\in S_{0}\\x^{2}&x\in S_{1}\\hx&x\in S_{2}\end{cases}}}$

${\displaystyle e(x,k)={\begin{cases}k+1&X\in S_{0}\\2k&X\in S_{1}\\k&X\in S_{2}\end{cases}}}$

${\displaystyle e'(x,k)={\begin{cases}k&X\in S_{0}\\2k&X\in S_{1}\\k+1&X\in S_{2}\end{cases}}}$

(대략, 이는 만약 ${\displaystyle x=g^{a}h^{b}\in \langle g,h\rangle }$이라면 ${\displaystyle f(x)=g^{e(x,a)}h^{e'(x,b)}}$이도록 정의한 것이다.)

이제, 임의의 유한군 ${\displaystyle G}$에 대하여, 적절한 ${\displaystyle G}$의 분할 ${\displaystyle (S_{0,G},S_{1,G},S_{2,G})}$를 잡자. 이는 크기가 대략 같은 세 집합으로 구성되어야 하며, 임의의 군 원소가 어떤 집합에 속하는지 쉽게 알 수 있어야 한다. 보통 다음과 같은 분할 ${\displaystyle (S_{0,G},S_{1,G},S_{2,G})}$를 사용한다.

• ${\displaystyle g\in G}$를 나타내는 비트 문자열을 이진법 전개로 하는 정수를 3으로 나눈 나머지가 ${\displaystyle i\in \{0,1,2\}}$라면, ${\displaystyle g\in S_{i}}$이다.

${\displaystyle (\mathbb {Z} /(p))^{\times }}$만을 고려하는 경우, 다음과 같은 분할을 사용할 수 있다.

• 만약 ${\displaystyle ip/3\leq g<(i+1)p/3}$이라면, ${\displaystyle g}$의 합동류는 ${\displaystyle S_{i}}$에 속한다.

폴라드 보행과 소박한(naive) 순환 탐지 알고리즘을 사용하는 폴라드 로 이산 로그 알고리즘는 크기가 ${\displaystyle n}$인 순환군 ${\displaystyle G}$와 그 생성 원소 ${\displaystyle g\in G}$와 임의의 원소 ${\displaystyle h\in G}$가 주어졌을 때, 이산 로그 ${\displaystyle \log _{g}h\in \mathbb {Z} /n}$을 다음과 같이 계산한다.

1. 다음을 반복한다.
   1. 무작위 원소 ${\displaystyle a_{0},b_{0}\in \mathbb {Z} /n}$을 고르고, ${\displaystyle x_{0}\leftarrow g^{a_{0}}h^{b_{0}}}$으로 놓는다.
   2. ${\displaystyle j=1,2,3,\dots }$에 대하여,
      1. ${\displaystyle x_{j}\leftarrow f(x_{j-1})}$, ${\displaystyle a_{j}\leftarrow e(x_{j-1},a_{j-1})}$, ${\displaystyle b_{j}\leftarrow e'(x_{j-1},b_{j-1})}$로 놓는다.
      2. 만약 ${\displaystyle x_{i}=x_{j}}$인 ${\displaystyle i<j}$가 존재한다면, 다음 단계로 넘어간다.
   3. 만약 ${\displaystyle b_{j}-b_{i}}$가 ${\displaystyle \mathbb {Z} /n}$의 가역원이라면 ${\displaystyle (a_{i}-a_{j})/(b_{j}-b_{i})\in \mathbb {Z} /n}$을 반환한다.

반복 함수의 개선

임의의 아벨 군 ${\displaystyle G}$ 및 ${\displaystyle g,h\in G}$ 및 ${\displaystyle m_{1},\dots ,m_{r},n_{1},\dots ,n_{r}\in \mathbb {Z} /n}$ 및 양의 정수 ${\displaystyle r}$ 및 함수 ${\displaystyle \operatorname {hash} \colon G\to \{1,\dots ,r\}}$에 대하여, 함수 ${\displaystyle f_{g,h,{\vec {m}},{\vec {n}},\operatorname {hash} }\colon G\to G}$와 ${\displaystyle e_{{\vec {m}},{\vec {n}},\operatorname {hash} },e'_{{\vec {m}},{\vec {n}},\operatorname {hash} }\colon G\times \mathbb {Z} \to \mathbb {Z} }$를 다음과 같이 정의하자.

${\displaystyle f(x)=g^{m_{\operatorname {hash} (x)}}h^{n_{\operatorname {hash} (x)}}x}$

${\displaystyle e(x,k)=k+m_{\operatorname {hash} (x)}}$

${\displaystyle e'(x,k)=k+n_{\operatorname {hash} (x)}}$

(그렇다면, 만약 ${\displaystyle x=g^{a}h^{b}}$라면 ${\displaystyle f(x)=g^{e(x,a)}h^{e'(x,b)}}$이다.)

이 경우, 임의의 ${\displaystyle x_{0}\in G}$에 대하여, 열 ${\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots }$을 테스케 r-더하기 보행(영어: Teske’s r-adding walk)이라고 한다.

이제, 임의의 유한군 ${\displaystyle G}$ 및 양의 정수 ${\displaystyle r}$에 대하여, 적절한 해시 함수 ${\displaystyle \operatorname {hash} _{G,r}\colon G\to \{1,\dots ,r\}}$를 잡자. 보통, 다음과 같이 정의한다.

• ${\displaystyle \operatorname {hash} (g)}$는 ${\displaystyle g}$를 나타내는 비트 문자열을 이진법 전개로 하는 정수를 ${\displaystyle r}$로 나눈 나머지이다.

이제, 적절한 양의 정수 ${\displaystyle r}$를 잡자. 만약 ${\displaystyle r}$가 너무 작다면, 이는 무작위성을 잘 모의하지 못한다. 폴라드가 사용한 보행은 ${\displaystyle r=3}$에 해당하며, 이는 너무 작다. 경험적으로 ${\displaystyle r\approx 20}$이 잘 작동한다.

테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 폴라드 로 이산 로그 알고리즘은 크기가 ${\displaystyle n}$인 순환군 ${\displaystyle G}$와 그 생성 원소 ${\displaystyle g\in G}$와 임의의 원소 ${\displaystyle h\in G}$가 주어졌을 때, 이산 로그 ${\displaystyle \log _{g}h\in \mathbb {Z} /n}$을 다음과 같이 계산한다.

1. 다음을 반복한다.
   1. 무작위 원소 ${\displaystyle m_{1},\dots ,m_{r},n_{1},\dots ,n_{r}\in \mathbb {Z} /n}$을 고르고, 각 ${\displaystyle i=1,\dots ,r}$에 대하여 ${\displaystyle M_{i}\leftarrow g^{m_{i}}h^{n_{i}}}$로 놓는다.
   2. 무작위 원소 ${\displaystyle a_{0},b_{0}\in \mathbb {Z} /n}$을 고르고, ${\displaystyle x_{0}\leftarrow g^{a_{0}}h^{b_{0}}}$으로 놓는다.
   3. ${\displaystyle j=1,2,3,\dots }$에 대하여,
      1. ${\displaystyle x_{j}\leftarrow f(x_{j-1})}$, ${\displaystyle a_{j}\leftarrow e(x_{j-1},a_{j-1})}$, ${\displaystyle b_{j}\leftarrow e'(x_{j-1},b_{j-1})}$로 놓는다.
      2. 만약 ${\displaystyle x_{i}=x_{j}}$인 ${\displaystyle i<j}$가 존재한다면, 다음 단계로 넘어간다.
   4. 만약 ${\displaystyle b_{j}-b_{i}}$가 ${\displaystyle \mathbb {Z} /n}$의 가역원이라면 ${\displaystyle (a_{i}-a_{j})/(b_{j}-b_{i})\in \mathbb {Z} /n}$을 반환한다.

순환 탐지 알고리즘의 개선

플로이드 순환 탐지 알고리즘

테스케 r-더하기 보행과 플로이드 순환 탐지 알고리즘을 사용하는 폴라드 로 이산 로그 알고리즘은 크기가 ${\displaystyle n}$인 순환군 ${\displaystyle G}$와 그 생성 원소 ${\displaystyle g\in G}$와 임의의 원소 ${\displaystyle h\in G}$가 주어졌을 때, 이산 로그 ${\displaystyle \log _{g}h\in \mathbb {Z} /n}$을 다음과 같이 계산한다.

1. 다음을 반복한다.
   1. 무작위 원소 ${\displaystyle m_{1},\dots ,m_{r},n_{1},\dots ,n_{r}\in \mathbb {Z} /n}$을 고르고, 각 ${\displaystyle i=1,\dots ,r}$에 대하여 ${\displaystyle M_{i}\leftarrow g^{m_{i}}h^{n_{i}}}$로 놓는다.
   2. 무작위 원소 ${\displaystyle a,b\in \mathbb {Z} /n}$을 고르고, ${\displaystyle x\leftarrow g^{a}h^{b}}$, ${\displaystyle a'\leftarrow a}$, ${\displaystyle b'\leftarrow b}$, ${\displaystyle x'\leftarrow x}$로 놓는다.
   3. 다음을 반복한다.
      1. ${\displaystyle x\leftarrow f(x)}$, ${\displaystyle a\leftarrow e(x,a)}$, ${\displaystyle b\leftarrow e'(x,b)}$로 놓는다.
      2. ${\displaystyle x'\leftarrow f(x')}$, ${\displaystyle c\leftarrow e(x',a')}$, ${\displaystyle d\leftarrow e'(x',b')}$로 놓는다.
      3. ${\displaystyle x'\leftarrow f(x')}$, ${\displaystyle c\leftarrow e(x',a')}$, ${\displaystyle d\leftarrow e'(x',b')}$로 놓는다.
      4. 만약 ${\displaystyle x=x'}$라면, 다음 단계로 넘어간다.
   4. 만약 ${\displaystyle b'-b}$가 ${\displaystyle \mathbb {Z} /n}$의 가역원이라면 ${\displaystyle (a-a')/(b'-b)\in \mathbb {Z} /n}$을 반환한다.

구별점 방법

크기가 ${\displaystyle n}$인 임의의 유한군 ${\displaystyle G}$ 및 함수 ${\displaystyle \operatorname {hash} \colon G\to \{0,1\}^{\lfloor \ln n\rfloor }}$ 및 양의 정수 ${\displaystyle k}$에 대하여, 적절한 함수 ${\displaystyle B_{G,\operatorname {hash} ,k}\colon G\to \{0,1\}}$를 잡자. 이는 흔히 다음과 같이 정의한다.

• 만약 ${\displaystyle \operatorname {hash} (g)}$의 ${\displaystyle k}$개 최하위 비트가 모두 0이라면, ${\displaystyle B(g)=1}$이다.

이 경우, ${\displaystyle B^{-1}(1)}$의 원소를 구별점(영어: distinguished point)이라고 부른다.

이제, 적절한 함수 ${\displaystyle \theta \colon \mathbb {Z} ^{+}\to \mathbb {R} }$를 잡자. 예를 들어,

${\displaystyle \theta (n)=\ln ^{c}n/{\sqrt {n}}}$

으로 놓을 수 있다. 여기서 ${\displaystyle c}$는 적절한 양의 실수(예를 들어, ${\displaystyle c\approx 10}$)이다. ${\displaystyle c}$가 클수록 기대 시간은 줄고 기대 공간은 는다.

테스케 r-더하기 보행과 구별점 방법을 사용하는 폴라드 로 이산 로그 알고리즘은 크기가 ${\displaystyle n}$인 순환군 ${\displaystyle G}$와 그 생성 원소 ${\displaystyle g\in G}$와 임의의 원소 ${\displaystyle h\in G}$가 주어졌을 때, 이산 로그 ${\displaystyle \log _{g}h\in \mathbb {Z} /n}$을 다음과 같이 계산한다.

1. 다음을 반복한다.
   1. 무작위 함수 ${\displaystyle \operatorname {hash} \colon G\to \{0,1\}^{\lfloor \ln n\rfloor }}$을 고른다. ${\displaystyle k\leftarrow \lceil \log _{2}\theta (n)\rceil }$, ${\displaystyle t\leftarrow 0}$으로 놓는다.
   2. 다음을 반복한다.
      1. 만약 ${\displaystyle k=0}$이라면, 이 순환을 빠져나온다.
      2. 만약 ${\displaystyle t=\lfloor \pi n/2\rfloor }$라면, ${\displaystyle k\leftarrow k-1}$, ${\displaystyle t\leftarrow 0}$으로 놓는다.
      3. ${\displaystyle t\leftarrow t+1}$로 놓는다.
      4. 무작위 원소 ${\displaystyle m_{1},\dots ,m_{r},n_{1},\dots ,n_{r}\in \mathbb {Z} /n}$을 고르고, 각 ${\displaystyle i=1,\dots ,r}$에 대하여 ${\displaystyle M_{i}\leftarrow g^{m_{i}}h^{n_{i}}}$로 놓는다.
      5. 무작위 원소 ${\displaystyle a_{0},b_{0}\in \mathbb {Z} /n}$을 고르고, ${\displaystyle x_{0}\leftarrow g^{a_{0}}h^{b_{0}}}$으로 놓는다.
      6. ${\displaystyle D\leftarrow \varnothing }$으로 놓는다.
      7. ${\displaystyle j=1,2,3,\dots }$에 대하여,
         1. ${\displaystyle x_{j}\leftarrow f(x_{j-1})}$, ${\displaystyle a_{j}\leftarrow e(x_{j-1},a_{j-1})}$, ${\displaystyle b_{j}\leftarrow e'(x_{j-1},b_{j-1})}$로 놓는다.
         2. 만약 ${\displaystyle B(x_{j})=1}$이라면,
            1. 만약 ${\displaystyle x_{i}=x_{j}}$인 ${\displaystyle x_{i}\in D}$가 존재한다면,
               1. 만약 ${\displaystyle b_{j}-b_{i}}$가 ${\displaystyle \mathbb {Z} /n}$의 가역원이라면, ${\displaystyle (a_{i}-a_{j})/(b_{j}-b_{i})\in \mathbb {Z} /n}$을 반환한다.
               2. 만약 ${\displaystyle b_{j}-b_{i}}$가 ${\displaystyle \mathbb {Z} /n}$의 가역원이 아니라면, 이 순환(“7. ${\displaystyle j=1,2,3,\dots }$에 대하여”)를 빠져나온다.
            2. 만약 ${\displaystyle x_{i}=x_{j}}$인 ${\displaystyle x_{i}\in D}$가 존재하지 않는다면, ${\displaystyle D\leftarrow D\cup \{(a_{j},b_{j},x_{j})\}}$로 놓는다.

복잡도

폴라드 로 이산 로그 알고리즘의 모든 형태는 거의 확실하게(즉, 확률 1로) 종료하며, 종료하는 경우 옳은 이산 로그 값을 반환한다. 따라서, 폴라드 로 이산 로그 알고리즘은 라스베이거스 알고리즘이다.

${\displaystyle f\colon G\to G}$와 ${\displaystyle x_{0}\in G}$가 이산 균등 분포를 따른다고 가정하자. 즉, ${\displaystyle x_{0},x_{1},x_{2},\dots }$는 이산 균등 분포를 따르는 독립 확률 변수들의 열이다. 그렇다면, 첫 순환 ${\displaystyle x_{i},x_{i+1},\dots ,x_{j-1}}$의 시작점 ${\displaystyle i}$와 순환의 주기 ${\displaystyle j-i}$와 두 번째 순환의 시작점 ${\displaystyle j}$의 기댓값은 다음과 같이 점근적으로 근사할 수 있다.

${\displaystyle \operatorname {E} (i)=\operatorname {E} (j-i)\sim {\sqrt {\pi n/8}}\approx 0.63{\sqrt {n}}}$

${\displaystyle \operatorname {E} (j)\sim {\sqrt {\pi n/2}}\approx 1.25{\sqrt {n}}}$

소박한 순환 탐지 알고리즘을 사용하는 경우, 반복 횟수는 ${\displaystyle j}$번이며, 매 회 반복마다 1회 군 연산을 사용하고 1개 군 원소를 추가 저장한다. 따라서, 기대 시간 복잡도는 ${\displaystyle O({\sqrt {n}})}$번 군 연산이며, 기대 공간 복잡도는 ${\displaystyle O({\sqrt {n}})}$개 군 원소이다.

플로이드 순환 탐지 알고리즘을 사용하는 경우, 기대 반복 횟수는 ${\displaystyle {}\sim {\sqrt {9\pi n/32}}\approx 0.94{\sqrt {n}}}$이며, 매 회 반복마다 3회 군 연산을 사용하며, 2개의 군 원소만을 비교하므로 군 원소를 추가 저장할 필요가 없다. 따라서, 기대 시간 복잡도는 ${\displaystyle O({\sqrt {n}})}$번 군 연산이며, 공간 복잡도는 ${\displaystyle O(1)}$개 군 원소이다.

구별점 방법을 사용하는 경우, 기대 반복 횟수는 ${\displaystyle {}\sim {\sqrt {\pi n/2}}+1/\theta }$이며, 매 회 반복마다 1회 군 연산을 사용하고 군 원소가 구별점인 경우에만 추가 저장한다. 이 경우, 기대 시간 복잡도는 ${\displaystyle O({\sqrt {\pi n/2}}+1/\theta )}$번 군 연산, 기대 공간 복잡도는 ${\displaystyle O(\theta {\sqrt {n}})}$개 군 원소이다. 특히, ${\displaystyle \theta =\ln ^{c}n/{\sqrt {n}}}$인 경우 기대 반복 횟수는 ${\displaystyle {}\sim {\sqrt {\pi n/2}}}$, 기대 시간 복잡도는 ${\displaystyle O({\sqrt {n}})}$번 군 연산, 기대 공간 복잡도는 ${\displaystyle O(\ln ^{c}n)}$이다.

물론, 실제 알고리즘에서 사용하는 보행은 진정한 무작위 보행이 아니며, 실제 알고리즘의 성능은 경험적으로 무작위 가정 아래 성능에 못 미친다. 예를 들어, 다음과 같은 경험적인 추정들이 존재한다.

• ${\displaystyle G}$가 ${\displaystyle (\mathbb {Z} /(p))^{\times }}$의 소수 크기 부분군일 때,
  • 폴라드 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, ${\displaystyle \operatorname {E} (j)\sim \approx 1.55{\sqrt {n}}}$
  • 테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, ${\displaystyle \operatorname {E} (j)\sim \approx 1.27{\sqrt {n}}}$
• ${\displaystyle G}$가 유한체 위의 타원 곡선의 부분군일 때,
  • 폴라드 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, ${\displaystyle \operatorname {E} (j)\sim \approx 1.60{\sqrt {n}}}$
  • 테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, ${\displaystyle \operatorname {E} (j)\sim \approx 1.29{\sqrt {n}}}$