소수계승걸음

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

 정의 
 유계 소수계승걸음 
유계 소수계승걸음()은 다음과 같다.
 입력:
 크기 을 모르는 유한 순환군 의 생성 원소 
 양의 실수  및 양의 실수 
 쾌속 차수 알고리즘 가운데 하나 . 이는 어떤 군의 원소 와 소인수 분해가 주어진 의 차수의 배수 를 입력으로 받고, 의 차수를 다항 시간 안에 출력한다.
 출력: 의 차수 
 (초기화) 를 인 가장 큰 양의 정수로 놓는다. 여기서 은 소수계승이다. 을 인 가장 큰 정수로 놓는다. , , 로 놓는다.
 (아기 걸음) 에 대하여, 만약 라면,
 를 계산하고 를 어떤 표에 저장한다.
 만약 라면, 로 놓고 4번째 단계(차수의 계산)로 넘어간다.
 (거인 걸음) 에 대하여,
 를 계산한다.
 만약 , 인 가 존재한다면, 로 놓고 4번째 단계(차수의 계산)로 넘어간다.
 (차수의 계산) 을 반환한다.

 무계 소수계승걸음 
무계 소수계승걸음()은 다음과 같다.
 입력:
 크기 을 모르는 유한 순환군 의 생성 원소 
 최종적으로 증가하는 함수 
 양의 실수  및 양의 실수 
 쾌속 차수 알고리즘 가운데 하나 . 이는 어떤 군의 원소 와 소인수 분해가 주어진 의 차수의 배수 를 입력으로 받고, 의 차수를 다항 시간 안에 출력한다.
 출력: 의 차수 
 (의 계산) 로 놓는다. 로 놓는다.
 (초기화) 를 이며 인 가장 큰 양의 정수로 놓는다. , , 으로 놓는다.
 (의 조정)
 만약 이며 이라면,
 로 놓는다. 을 인 가장 작은 의 배수로 놓는다. 을 인 가장 작은 의 배수로 놓는다.
 에 대하여, 만약 라면 를 계산하고 를 어떤 표에 저장한다. 만약 라면, 로 놓고 7번째 단계(의 차수의 계산)로 넘어간다. 만약 라면, 으로 놓는다.
 로 놓는다. 를 계산한다. 만약 인 이 존재한다면, 로 놓고 7번째 단계(의 차수의 계산)로 넘어간다. 만약 인 이 존재하지 않는다면, 으로 놓는다.
 을 인 가장 큰 정수로 놓는다.
 (아기 걸음) 각 에 대하여, 만약 이라면,
 를 계산하고 를 어떤 표에 저장한다.
 만약 라면, 로 놓고 7번째 단계(의 차수의 계산)로 넘어간다. 만약 라면, 로 놓는다.
 (거인 걸음) 각 에 대하여,
 를 계산한다.
 만약 인 이 존재한다면, 로 놓고 7번째 단계(의 차수의 계산)로 넘어간다. 만약 인 이 존재하지 않는다면, 로 놓는다.
 (반복) 로 놓고 3번째 단계로 돌아간다.
 (의 차수의 계산) 을 반환한다.

 복잡도 
유계 소수계승걸음의 시간 복잡도는

번 이하의 군 연산이며, 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 는 오일러-마스케로니 상수이며, 이다.

만약 의 차수가  위의 이산 균등 분포를 따르며, 을 사용한다고 가정하였을 때, 유계 소수계승걸음의 기대 시간 복잡도는

번 이하의 군 연산이며, 기대 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 는 리만 제타 함수이며, 이다.

무계 소수계승걸음의 입력이 다음 추가 조건들을 만족시킨다고 가정하자.


 는 다항 유계 함수()이다. 즉, 정수 계수 다항식 가 존재하며, 임의의 양의 정수 에 대하여 이다.
 가 알고리즘 의 복잡도라고 하자. 그렇다면, 는 적어도 에 대하여 선형이다.
그렇다면, 무계 소수계승걸음의 시간 복잡도는

번 이하의 군 연산이며, 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 는 소수 계량 함수이며, 이다.
특히, 을 너무 크게 잡지 않는 한 무계 소수계승걸음의 시간 복잡도는

(특히 )번 군 연산이다.

만약 의 차수가  위의 이산 균등 분포를 따르며, 이며, 라면 (), 무계 소수계승걸음의 기대 시간 복잡도는

번 이하의 군 연산이며, 기대 공간 복잡도는 그 절반인 개수 이하의 군 원소이다. 여기서 이다.

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

 참고 문헌 

 외부 링크 


분류:수론 알고리즘