폴라드 로 알고리즘

이 문서는 소인수분해 알고리즘에 관한 것입니다. 이산 로그 알고리즘에 대해서는 폴라드 로 이산 로그 알고리즘 문서를 참고하십시오.

폴라드 로 알고리즘(영어: Pollard's rho algorithm)은 존 폴라드가 1975년에 고안한 소인수분해 알고리즘이다.^[1] 이 알고리즘은 저장 공간을 적게 사용하고 소인수분해하는 데 걸리는 실행 시간은 소인수분해하려는 합성수의 가장 작은 소인수의 제곱근에 비례하는 알고리즘이다.

핵심 개념

소인수분해하려는 숫자 ${\displaystyle n=pq}$에서, ${\displaystyle p}$는 자명하지 않은 인수(1이 아닌 인수)라고 가정한다. 다항식을 ${\displaystyle n}$으로 나누는 연산 ${\displaystyle g(x)}$ (예: ${\displaystyle g(x)=(x^{2}+1){\bmod {n}}}$)는 유사난수 수열을 생성할 때 사용되는데, 이때 시작값을 적당히 2로 설정하면 수열은 ${\displaystyle x_{1}=g(2)}$, ${\displaystyle x_{2}=g(g(2))}$, ${\displaystyle x_{3}=g(g(g(2)))}$의 형태로 생성된다. 이 수열은 다른 수열 ${\displaystyle \{x_{k}{\bmod {p}}\}}$과 관련이 있으나 ${\displaystyle p}$가 사전에 주어지지 않았기 때문에 두 번째 수열은 이 알고리즘에서 계산할 수는 없다. 여기서 첫 번째 수열과 두 번째 수열의 관계가 폴라드 로 알고리즘의 핵심 아이디어이다.

이 수열에 나오는 수의 개수가 유한하기 때문에, ${\displaystyle n}$의 나머지인 수열 ${\displaystyle \{x_{k}\}}$와 ${\displaystyle \{x_{k}{\bmod {p}}\}}$는 언젠가 반복이 된다. 이 수열을 완전한 난수라고 가정하면, 생일 역설 (Birthday Paradox)에 의해 이 수열이 반복되기 전까지 나오는 서로 다른 ${\displaystyle x_{k}}$의 개수는 대략 ${\displaystyle O({\sqrt {N}})}$이며, 이 때 ${\displaystyle N}$은 가능한 값의 개수이다. 따라서 수열 ${\displaystyle \{x_{k}{\bmod {p}}\}}$은 수열 ${\displaystyle \{x_{k}\}}$보다 먼저 반복된다. 각각의 값은 수열의 이전에 나온 값에 의해서만 결정되기 때문에, 한 번 수열이 반복되면 수열은 계속 순환하게 된다. 이렇게 최종적으로 순환하게 되는 구조는 ${\displaystyle x_{1}{\bmod {p}}}$, ${\displaystyle x_{2}{\bmod {p}}}$, 등의 값을 가지며 이 값들을 유향 그래프의 꼭짓점으로 표현하면 그리스 문자 ρ처럼 생겼기 때문에 "폴라드 로 알고리즘"이라는 이름이 붙게 되었다.

그리스 문자 ρ를 닮은 순환 그래프

위 수열에서 나오는 반복은 플로이드 순환 찾기 알고리즘으로 찾는다. 먼저, 두 수 ${\displaystyle i}$와 ${\displaystyle j}$ (즉, ${\displaystyle x_{i}}$와 ${\displaystyle x_{j}}$)를 정한다. 매 단계마다 하나는 수열의 다음 수로 이동하고, 다른 하나는 두 번 이동한다. 그리고 ${\displaystyle \gcd(x_{i}-x_{j},n)\neq 1}$인지를 검사한다. 만약 1이 아니라면 수열 ${\displaystyle \{x_{k}{\bmod {p}}\}}$는 반복이 된다는 것을 의미한다 (즉, ${\displaystyle x_{i}{\bmod {p}}=x_{j}{\bmod {p}}}$이다). 이러한 경우는 ${\displaystyle x_{i}}$가 ${\displaystyle x_{j}}$와 같거나, ${\displaystyle x_{i}}$와 ${\displaystyle x_{j}}$의 차이가 ${\displaystyle p}$의 배수여야 한다. 결국 이러한 경우가 반드시 생기기 때문에, 결과값인 최대공약수(GCD)는 1이 아닌 ${\displaystyle n}$의 약수이며, 여기서 두 수열이 동시에 순환할 수 있기 때문에 알고리즘의 결과값이 ${\displaystyle n}$ 자신이 될 수도 있다. 이러한 경우에는 알고리즘이 소인수를 찾는 데 실패하며, 다른 초기값으로 실행하거나 다른 알고리즘 (타원곡선 방법 (ECM) 등)을 사용할 수도 있다.

알고리즘

이 알고리즘은 인수분해 하려는 정수 n과 x에 대한 다항식을 n으로 나눈 나머지인 연산 ${\displaystyle g(x)}$를 입력으로 받는다. 폴라드가 만든 원래 알고리즘에서는 ${\displaystyle g(x)=(x^{2}-1){\bmod {n}}}$이였지만, 최근에 사용할 때에는 보통 ${\displaystyle g(x)=(x^{2}+1){\bmod {n}}}$을 더 많이 사용한다. 출력값으로는 n의 자명하지 않은 소인수이거나 '실패'이며, 폴라드 로 알고리즘은 다음의 단계를 따라 실행된다:^[2]

    x ← 2
    y ← 2
    d ← 1

    while d = 1:
        x ← g(x)
        y ← g(g(y))
        d ← gcd(|x - y|, n)

    if d = n:
        return failure
    else:
        return d

이 때 x와 y는 각각 핵심 개념 문단의 ${\displaystyle x_{i}}$와 ${\displaystyle x_{j}}$에 대응한다. 이 알고리즘은 n이 합성수일 경우에도 자명하지 않은 인수를 찾는데 실패할 수 있다는 점을 주의해야 한다. 이러한 경우, 시작 값으로 2가 아닌 다른 값을 이용하거나 다른 ${\displaystyle g(x)}$를 이용하여 다시 수행할 수 있다.

소인수분해 예제

먼저 ${\displaystyle n=8051}$, 그리고 ${\displaystyle g(x)=(x^{2}+1){\bmod {8}}051}$이라고 가정했을 때,

i	x	y	GCD(|x − y|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97
4	7474	1481	1

97은 8051의 자명하지 않은 인수이다. 시작값으로 x = y = 2가 아닌 다른 값을 이용하면 97이 아닌 다른 인수 (83)을 얻을 수 있다. y는 x보다 두 배 더 빠르게 수열의 값이 변한다는 것을 나타내기 위해 한 단계를 더 나타내었다. 참고로, 이 알고리즘은 최대공약수가 1 이상이 나온 후 다시 이 과정을 반복하는 경우 1이 다시 나올 수도 있다.

변형

리차드 브렌트는 1980년에 이 알고리즘을 조금 더 효율적으로 바꾼 폴라드 로 알고리즘을 발표했다. 브랜트의 알고리즘은 폴라드 로 알고리즘과 핵심 개념은 같지만 반복을 만들어 소인수를 얻어내는 방법이 플로이드 순환 검출 알고리즘에서 브렌트 순환 검출 방법으로 바꾸어 개량한 알고리즘이다.^[3]

폴라드와 브렌트는 이 알고리즘을 더욱 개선했다. 이들은 ${\displaystyle \gcd(a,n)>1}$일 경우, 모든 양의 정수 ${\displaystyle b}$에 대하여 ${\displaystyle \gcd(ab,n)>1}$인 것을 이용하였다. 그 예시로 모든 단계에서 ${\displaystyle \gcd(|x-y|,n)}$을 계산하는 대신, ${\displaystyle z}$를 100개의 연속한 ${\displaystyle |x-y|}$의 곱을 ${\displaystyle n}$으로 나눈 나머지로 정의하고 ${\displaystyle \gcd(z,n)}$을 계산하는 방법 등으로 원래 알고리즘에 비해 속도를 개선하였다. 이 방법이 속도를 증가시키는 이유는 최대공약수를 구하는 연산을 100번 반복하던 것을 곱을 이용하여 ${\displaystyle n}$으로 나눈 나머지 99번과 최대공약수를 구하는 연산을 1번씩만을 계산하도록 바꾸었기 때문이다. 이 방법은 가끔씩 ${\displaystyle n}$이 소수의 제곱수 같은 약수를 포함하고 있을 때에는 알고리즘이 실패할 수도 있는데, 그럴 경우에는 ${\displaystyle \gcd(z,n)=1}$인 수열의 항으로 돌아가서 다시 일반적인 폴라드 로 알고리즘을 실행해도 충분히 그 소인수를 얻어낼 수 있다.

적용

폴라드 로 알고리즘은 타원곡선 방법 비슷하게과 작은 인수를 가진 수의 경우에는 매우 빠르지만 모든 인수가 클 경우에는 느리다. 폴라드 로 알고리즘의 가장 주목할 만한 성과는 페르마 수 F₈을 소인수분해한 것이다: F₈ = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321^[4]. 소인수 p = 1238926361552897은 다른 인수에 비해 훨씬 작았기 때문에 ρ 알고리즘은 F₈을 소인수분해 하기에 적절하였고, 소인수분해 과정은 UNIVAC 1100/42에서 2시간이 걸렸다. 또한 이 알고리즘은 소인수분해하고 싶은 수의 비교적 작은 소인수들을 얻어내는 데 많이 쓰인다.

n = 10403 = 101 · 103 인 예제

다음은 또다른 변형 알고리즘으로, 한 수열만 계산하며 수열을 반복하여 계산할 때마다 최대공약수를 계산한다.

C 코드 예제

다음 예제 코드는 시작값 x = 2로 10403의 인수 101을 찾는다.

#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b)
{
    int remainder;
    while (b != 0) {
        remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

int main (int argc, char *argv[])
{
    int number = 10403, loop = 1, count;
    int x_fixed = 2, x = 2, size = 2, factor;

    do {
        printf("----   loop %4i   ----\n", loop);
        count = size;
        do {
            x = (x * x + 1) % number;
            factor = gcd(abs(x - x_fixed), number);
            printf("count = %4i  x = %6i  factor = %i\n", size - count + 1, x, factor);
        } while (--count && (factor == 1));
        size *= 2;
        x_fixed = x;
        loop = loop + 1;
    } while (factor == 1);
    printf("factor is %i\n", factor);
    return factor == number ? EXIT_FAILURE : EXIT_SUCCESS;
}

위의 코드는 알고리즘이 진행되는 것을 중간값으로 표시한다. 출력의 마지막 행은 "factor is 101"이다. 이 코드는 x를 제곱할 때 정수 자료형에서 오버플로우가 일어날 수 있어 테스트 값이 작은 경우에만 적용된다.

Python 코드 예제

from itertools import count
from math import gcd

number, x = 10403, 2

for cycle in count(1):
    y = x
    for i in range(2 ** cycle):
        x = (x * x + 1) % number
        factor = gcd(x - y, number)
        if factor > 1:
            print("factor is", factor)
            exit()

결과

다음의 표에서 세번째와 네번째 열은 pq = 10403을 소인수분해하기 전에는 모르는 정보이다. 이는 알고리즘이 어떻게 동작하는지 나타내기 위해 추가되었다. 초깃값을 x = 2로 정해서 알고리즘을 적용하면 다음과 같이 된다.

${\displaystyle x}$	${\displaystyle x_{fixed}}$	${\displaystyle x{\bmod {1}}01}$	${\displaystyle x_{fixed}{\bmod {1}}01}$	단계
2	2	2	2	0
5	2	5	2	1
26	2	26	2	2
677	26	71	26	3
598	26	93	26	4
3903	26	65	26	5
3418	26	85	26	6
156	3418	55	85	7
3531	3418	97	85	8
5168	3418	17	85	9
3724	3418	88	85	10
978	3418	69	85	11
9812	3418	15	85	12
5983	3418	24	85	13
9970	3418	72	85	14
236	9970	34	72	15
3682	9970	46	72	16
2016	9970	97	72	17
7087	9970	17	72	18
10289	9970	88	72	19
2594	9970	69	72	20
8499	9970	15	72	21
4973	9970	24	72	22
2799	9970	72	72	23

101로 나눈 나머지에서 첫 번째 반복은 17단계의 97이다. 이 반복은 23단계에서 ${\displaystyle x\equiv x_{fixed}{\pmod {101}}}$이 될 때까지 알고리즘이 알아내지 못한다. 이때 ${\displaystyle \gcd(x-x_{fixed},n)=\gcd(2799-9970,n)}$은 ${\displaystyle p=101}$이 되어 소인수를 찾게 된다.

복잡도

폴라드 로 알고리즘에서 쓰이는 유사 난수 ${\displaystyle x=g(x)}$가 실제로 완전한 난수라고 가정한다면, 생일 역설에 의해 폴라드 로 알고리즘은 ${\displaystyle O({\sqrt {p}})\leq O(n^{1/4})}$ 시간 안에 입력값의 인수를 출력할 수 있다. 실제로 폴라드 로 알고리즘은 대략 이 정도 시간에 작동하는 것이 알려져 있지만, 이는 아직 확률적인 추측이며 엄밀한 증명은 아직 이루어지지 않았다.^[5]

같이 보기

• 폴라드 로 이산 로그 알고리즘
• 폴라드의 캥거루 알고리즘