소수계승걸음

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

## 정의
### 유계 소수계승걸음
**유계 소수계승걸음**()은 다음과 같다.
* 입력:
** 크기 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'을 반환한다.

### 무계 소수계승걸음
**무계 소수계승걸음**()은 다음과 같다.
* 입력:
** 크기 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는 다항 유계 함수()이다. 즉, 정수 계수 다항식 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이다.

## 역사
앤드루 서덜랜드()가 2007년 박사 학위 논문에서 제시하였다.

## 참고 문헌


## 외부 링크
* 

분류:수론 알고리즘