소수계승걸음

**소수계승걸음**(primorial-steps)은 군의 원소의 차수를 계산하는 알고리즘이다. 미지의 차수가 n이라고 하였을 때 o(\sqrt n)번 군 연산을 시간 복잡도로 한다.
# 정의

## 유계 소수계승걸음
**유계 소수계승걸음**(bounded primorial-steps)은 다음과 같다. * 입력: ** 크기 n을 모르는 유한 순환군 G의 생성 원소 g\in G ** 양의 실수 M\ge n 및 양의 실수 M'\le M ** 쾌속 차수 알고리즘 가운데 하나 \mathcal A(g',E). 이는 어떤 군의 원소 g'와 소인수 분해가 주어진 g'의 차수의 배수 E를 입력으로 받고, g'의 차수를 다항 시간 안에 출력한다. * 출력: g의 차수 n # (초기화) w를 p_w\\#\le\sqrt{M'}인 가장 큰 양의 정수로 놓는다. 여기서 p_w\\#은 소수계승이다. m을 m^2p_w\\#\phi(p_w\\#)\le M'인 가장 큰 정수로 놓는다. r\leftarrow mp_w\\#, E\leftarrow\prod_{p\le p_w}p^{\lfloor\log_pM\rfloor}, h\leftarrow g^E로 놓는다. # (아기 걸음) j=1,\dots,r에 대하여, 만약 j\perp p_w\\#라면, ## h^j를 계산하고 (j,\beta^j)를 어떤 표에 저장한다. ## 만약 h^j=1_G라면, n'\leftarrow j로 놓고 4번째 단계(차수의 계산)로 넘어간다. # (거인 걸음) i=2r,3r,\dots에 대하여, ## h^i를 계산한다. ## 만약 h^i=h^j, j\perp p_w\\#인 j=1,\dots,r가 존재한다면, n'\leftarrow i-j로 놓고 4번째 단계(차수의 계산)로 넘어간다. # (차수의 계산) \mathcal A(g^{n'},E)n'을 반환한다.
## 무계 소수계승걸음
**무계 소수계승걸음**(unbounded primorial-steps)은 다음과 같다. * 입력: ** 크기 n을 모르는 유한 순환군 G의 생성 원소 g\in G ** 최종적으로 증가하는 함수 d\colon\mathbb Z^+\to\mathbb Z^+ ** 양의 실수 l\ge\log_2n 및 양의 실수 L>0 ** 쾌속 차수 알고리즘 가운데 하나 \mathcal A(g',E). 이는 어떤 군의 원소 g'와 소인수 분해가 주어진 g'의 차수의 배수 E를 입력으로 받고, g'의 차수를 다항 시간 안에 출력한다. * 출력: g의 차수 n # (g^E의 계산) E\leftarrow\prod_{p\le L}p^{\lfloor\log_p2^l\rfloor}로 놓는다. h\leftarrow g^E로 놓는다. # (초기화) w를 p_w\\#\le d(0)이며 p_w\le L인 가장 큰 양의 정수로 놓는다. k\leftarrow0, r\leftarrow0, s\leftarrow0으로 놓는다. # (p_w\\#의 조정) ## 만약 p_{w+1}\\#\le d(k)이며 p_{w+1}\le L이라면, ### w\leftarrow w+1로 놓는다. r'을 r'\ge r인 가장 작은 p_w\\#의 배수로 놓는다. s'을 s'\ge s인 가장 작은 p_w\\#의 배수로 놓는다. ### j=r,r+1,\dots,r'에 대하여, 만약 j\perp p_w\\#라면 h^j를 계산하고 (j,h^j)를 어떤 표에 저장한다. 만약 h^j=1_G라면, n'\leftarrow j로 놓고 7번째 단계(g의 차수의 계산)로 넘어간다. 만약 h^j\ne1_G라면, r\leftarrow r'으로 놓는다. ### i=s'로 놓는다. h^i를 계산한다. 만약 h^i=h^j인 j=r,r+1,\dots,r'이 존재한다면, n'\leftarrow i-j로 놓고 7번째 단계(g의 차수의 계산)로 넘어간다. 만약 h^i=h^j인 j=r,r+1,\dots,r'이 존재하지 않는다면, s\leftarrow s'으로 놓는다. ## m을 mp_w\\#\le d(k)인 가장 큰 정수로 놓는다. # (아기 걸음) 각 j=r,r+1,\dots,r+mp_w\\#에 대하여, 만약 j\perp p_w\\#이라면, ## h^j를 계산하고 (j,h^j)를 어떤 표에 저장한다. ## 만약 h^j=1_G라면, n'\leftarrow j로 놓고 7번째 단계(g의 차수의 계산)로 넘어간다. 만약 h^j\ne1_G라면, r\leftarrow r+mp_w\\#로 놓는다. # (거인 걸음) 각 i=s+r,s+2r,\dots,s+m\phi(p_w\\#)r에 대하여, ## h^i를 계산한다. ## 만약 h^i=h^j인 j=r,r+1,\dots,r+mp_w\\#이 존재한다면, n'\leftarrow i-j로 놓고 7번째 단계(g의 차수의 계산)로 넘어간다. 만약 h^i=h^j인 j=r,r+1,\dots,r+mp_w\\#이 존재하지 않는다면, s\leftarrow s+m\phi(p_w\\#)r로 놓는다. # (반복) k\leftarrow k+1로 놓고 3번째 단계로 돌아간다. # (g의 차수의 계산) \mathcal A(g^{n'},E)n'을 반환한다.
# 복잡도
유계 소수계승걸음의 시간 복잡도는 :(2\exp(-\gamma/2)+o(1))\sqrt{M/\ln\ln M} 번 이하의 군 연산이며, 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 \gamma는 오일러-마스케로니 상수이며, 2\exp(-\gamma/2)\approx1.4986이다. 만약 g의 차수가 \\{1,\dots,M\\} 위의 이산 균등 분포를 따르며, M'=(\zeta(2)/2)M\approx0.8225M을 사용한다고 가정하였을 때, 유계 소수계승걸음의 기대 시간 복잡도는 :\left(\exp(-\gamma)\sqrt{2\zeta(2)}+o(1)\right)\sqrt M/\ln\ln M 번 이하의 군 연산이며, 기대 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 \zeta는 리만 제타 함수이며, \exp(-\gamma)\sqrt{2\zeta(2)}\approx1.0184이다. 무계 소수계승걸음의 입력이 다음 추가 조건들을 만족시킨다고 가정하자. * L\ge l/2 * d(k)-d(k-1)\ll d(k) * d는 다항 유계 함수(polynomially bounded function)이다. 즉, 정수 계수 다항식 f,g\in\mathbb Z[x]가 존재하며, 임의의 양의 정수 k에 대하여 f(k)\le d(k)\le g(k)이다. * T(\log_2|g'|,\log_2E)가 알고리즘 \mathcal A(g',E)의 복잡도라고 하자. 그렇다면, T(\log_2|g'|,\log_2E)는 적어도 \ln E에 대하여 선형이다. 그렇다면, 무계 소수계승걸음의 시간 복잡도는 :(2\sqrt2\exp(-\gamma/2)+o(1))\sqrt{n/\ln\ln n}+T(\ln n,l\pi(L)) 번 이하의 군 연산이며, 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 \pi는 소수 계량 함수이며, 2\sqrt2\exp(-\gamma/2)\approx2.1194이다. 특히, L을 너무 크게 잡지 않는 한 무계 소수계승걸음의 시간 복잡도는 :O\left(\sqrt{n/\ln\ln n}\right) (특히 o(\sqrt n))번 군 연산이다. 만약 g의 차수가 \\{1,\dots,M\\} 위의 이산 균등 분포를 따르며, l=O(\ln M)이며, L=M^{1/u}라면 (u>2), 무계 소수계승걸음의 기대 시간 복잡도는 :(uA+o(1))\sqrt M/\left((\ln M\sqrt{\ln\ln M}\right) 번 이하의 군 연산이며, 기대 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 A\approx2.4이다.
# 역사
앤드루 서덜랜드(Andrew Sutherland)가 2007년 박사 학위 논문에서 제시하였다.형식=PDF