폴리그-헬먼 알고리즘

폴리그-헬먼 알고리즘()은 이산 로그를 밑의 차수가 소수인 경우로 귀결시켜 계산하는 알고리즘이다. 군의 크기(즉, 밑의 차수)가 충분히 매끄러운 정수인 경우 특히 효율적이다.

 정의 
폴리그-헬먼 알고리즘 는 다음과 같다.
 입력: 크기가 인 유한 순환군의 생성 원소 와 임의의 원소 
 출력: 이산 로그 
 의 소인수 분해 를 구한다.
 만약 이라면 0을 반환한다. 만약 , 이라면, (또는 )를 반환한다. 여기서 는 아기걸음 거인걸음(는 폴라드 로 이산 로그 알고리즘)이다.
 만약 이라면,
 로 놓는다.
 로 놓는다.
 을 반환한다.
 , 로 놓는다.
 을 와 의 에서의 곱셈 역원인 정수의 곱으로 놓는다. 마찬가지로, 를 와 의 에서의 곱셈 역원인 정수의 곱으로 놓는다.
 로 놓는다.
 로 놓는다.
 를 반환한다.

 복잡도 
폴리그-헬먼 알고리즘의 복잡도는 순환군의 크기(즉, 이산 로그의 밑의 차수)가 소수인 경우에 사용하는 알고리즘의 복잡도와 이 매끄러운 정도에 의존한다.

아기걸음 거인걸음을 사용하는 경우, 폴리그-헬먼 알고리즘의 시간 복잡도는

(특히 )이며, 공간 복잡도는 이다. 여기서 은 순환군의 크기, 는 의 소인수 분해, 는 의 가장 큰 소인수이다.

플로이드 순환 탐지 알고리즘을 갖춘 폴라드 로 이산 로그 알고리즘을 사용하는 경우, 폴리그-헬먼 알고리즘의 기대 시간 복잡도는

(특히 )이며, 공간 복잡도는 이다.

특히, 만약 이 충분히 매끄러운 정수인 경우 폴리그-헬먼 알고리즘은 의 자릿수에 대하여 준선형 시간을 갖는다.

 역사 
스티븐 폴리그()와 마틴 헬먼이 1978년 논문에서 처음 출판하였다. 폴리그와 헬먼은 이 논문에서 다음과 같이 주해하였다.

 참고 문헌 

 외부 링크 



분류:수론 알고리즘