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

폴라드 로 이산 로그 알고리즘()은 이산 로그를 계산하는 확률적 알고리즘이다. 결정론적 이산 로그 알고리즘과 비슷한 기대 실행 시간을 가지지만, 적절한 순환 탐지 알고리즘을 사용하는 경우 상수 공간 또는 선형 공간만을 사용한다.

 정의 
아벨 군  및  및 집합의 분할 에 대하여, 함수 와 를 다음과 같이 정의하자.

(대략, 이는 만약 이라면 이도록 정의한 것이다.)

이제, 임의의 유한군 에 대하여, 적절한 의 분할 를 잡자. 이는 크기가 대략 같은 세 집합으로 구성되어야 하며, 임의의 군 원소가 어떤 집합에 속하는지 쉽게 알 수 있어야 한다. 보통 다음과 같은 분할 를 사용한다.
 를 나타내는 비트 문자열을 이진법 전개로 하는 정수를 3으로 나눈 나머지가 라면, 이다.
만을 고려하는 경우, 다음과 같은 분할을 사용할 수 있다.
 만약 이라면, 의 합동류는 에 속한다.

폴라드 보행과 소박한() 순환 탐지 알고리즘을 사용하는 폴라드 로 이산 로그 알고리즘는 크기가 인 순환군 와 그 생성 원소 와 임의의 원소 가 주어졌을 때, 이산 로그 을 다음과 같이 계산한다.
 다음을 반복한다.
 무작위 원소 을 고르고, 으로 놓는다.
 에 대하여,
 , , 로 놓는다.
 만약 인 가 존재한다면, 다음 단계로 넘어간다.
 만약 가 의 가역원이라면 을 반환한다.

 반복 함수의 개선 
임의의 아벨 군  및  및  및 양의 정수  및 함수 에 대하여, 함수 와 를 다음과 같이 정의하자.

(그렇다면, 만약 라면 이다.)

이 경우, 임의의 에 대하여, 열 을 테스케 r-더하기 보행()이라고 한다.

이제, 임의의 유한군  및 양의 정수 에 대하여, 적절한 해시 함수 를 잡자. 보통, 다음과 같이 정의한다.
 는 를 나타내는 비트 문자열을 이진법 전개로 하는 정수를 로 나눈 나머지이다.

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

테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 폴라드 로 이산 로그 알고리즘은 크기가 인 순환군 와 그 생성 원소 와 임의의 원소 가 주어졌을 때, 이산 로그 을 다음과 같이 계산한다.
 다음을 반복한다.
 무작위 원소 을 고르고, 각 에 대하여 로 놓는다.
 무작위 원소 을 고르고, 으로 놓는다.
 에 대하여,
 , , 로 놓는다.
 만약 인 가 존재한다면, 다음 단계로 넘어간다.
 만약 가 의 가역원이라면 을 반환한다.

 순환 탐지 알고리즘의 개선 
 플로이드 순환 탐지 알고리즘 
테스케 r-더하기 보행과 플로이드 순환 탐지 알고리즘을 사용하는 폴라드 로 이산 로그 알고리즘은 크기가 인 순환군 와 그 생성 원소 와 임의의 원소 가 주어졌을 때, 이산 로그 을 다음과 같이 계산한다.
 다음을 반복한다.
 무작위 원소 을 고르고, 각 에 대하여 로 놓는다.
 무작위 원소 을 고르고, , , , 로 놓는다.
 다음을 반복한다.
 , , 로 놓는다.
 , , 로 놓는다.
 , , 로 놓는다.
 만약 라면, 다음 단계로 넘어간다.
 만약 가 의 가역원이라면 을 반환한다.

 구별점 방법 
크기가 인 임의의 유한군  및 함수  및 양의 정수 에 대하여, 적절한 함수 를 잡자. 이는 흔히 다음과 같이 정의한다.
 만약 의 개 최하위 비트가 모두 0이라면, 이다.

이 경우, 의 원소를 구별점()이라고 부른다.

이제, 적절한 함수 를 잡자. 예를 들어,

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

테스케 r-더하기 보행과 구별점 방법을 사용하는 폴라드 로 이산 로그 알고리즘은 크기가 인 순환군 와 그 생성 원소 와 임의의 원소 가 주어졌을 때, 이산 로그 을 다음과 같이 계산한다.
 다음을 반복한다.
 무작위 함수 을 고른다. , 으로 놓는다.
 다음을 반복한다.
 만약 이라면, 이 순환을 빠져나온다.
 만약 라면, , 으로 놓는다.
 로 놓는다.
 무작위 원소 을 고르고, 각 에 대하여 로 놓는다.
 무작위 원소 을 고르고, 으로 놓는다.
 으로 놓는다.
 에 대하여,
 , , 로 놓는다.
 만약 이라면,
 만약 인 가 존재한다면,
 만약 가 의 가역원이라면, 을 반환한다.
 만약 가 의 가역원이 아니라면, 이 순환(“7. 에 대하여”)를 빠져나온다.
 만약 인 가 존재하지 않는다면, 로 놓는다.

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

와 가 이산 균등 분포를 따른다고 가정하자. 즉, 는 이산 균등 분포를 따르는 독립 확률 변수들의 열이다. 그렇다면, 첫 순환 의 시작점 와 순환의 주기 와 두 번째 순환의 시작점 의 기댓값은 다음과 같이 점근적으로 근사할 수 있다.

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

플로이드 순환 탐지 알고리즘을 사용하는 경우, 기대 반복 횟수는 이며, 매 회 반복마다 3회 군 연산을 사용하며, 2개의 군 원소만을 비교하므로 군 원소를 추가 저장할 필요가 없다. 따라서, 기대 시간 복잡도는 번 군 연산이며, 공간 복잡도는 개 군 원소이다.

구별점 방법을 사용하는 경우, 기대 반복 횟수는 이며, 매 회 반복마다 1회 군 연산을 사용하고 군 원소가 구별점인 경우에만 추가 저장한다. 이 경우, 기대 시간 복잡도는 번 군 연산, 기대 공간 복잡도는 개 군 원소이다. 특히, 인 경우 기대 반복 횟수는 , 기대 시간 복잡도는 번 군 연산, 기대 공간 복잡도는 이다.

물론, 실제 알고리즘에서 사용하는 보행은 진정한 무작위 보행이 아니며, 실제 알고리즘의 성능은 경험적으로 무작위 가정 아래 성능에 못 미친다. 예를 들어, 다음과 같은 경험적인 추정들이 존재한다.
 가 의 소수 크기 부분군일 때,
 폴라드 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, 
 테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, 
 가 유한체 위의 타원 곡선의 부분군일 때,
 폴라드 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, 
 테스케 r-더하기 보행과 소박한 순환 탐지 알고리즘을 사용하는 경우, 

 참고 문헌 

 외부 링크 


분류:수론 알고리즘