폴라드 로 알고리즘

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

핵심 개념편집

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

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

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

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

알고리즘편집

이 알고리즘은 인수분해 하려는 정수 nx에 대한 다항식을 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

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

소인수분해 예제편집

먼저  , 그리고  이라고 가정했을 때,

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

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

변형편집

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

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

적용편집

폴라드 로 알고리즘은 타원곡선 방법 비슷하게과 작은 인수를 가진 수의 경우에는 매우 빠르지만 모든 인수가 클 경우에는 느리다. 폴라드 로 알고리즘의 가장 주목할 만한 성과는 페르마 수 F8을 소인수분해한 것이다: F8 = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321[4]. 소인수 p = 1238926361552897은 다른 인수에 비해 훨씬 작았기 때문에 ρ 알고리즘은 F8을 소인수분해 하기에 적절하였고, 소인수분해 과정은 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로 정해서 알고리즘을 적용하면 다음과 같이 된다.

        단계
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단계에서  이 될 때까지 알고리즘이 알아내지 못한다. 이때   이 되어 소인수를 찾게 된다.

복잡도편집

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

같이 보기편집

참조편집

  1. Pollard, J. M. (1975). “A Monte Carlo method for factorization”. 《BIT Numerical Mathematics》 15 (3): 331–334. doi:10.1007/bf01933667. 
  2. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2009). 〈Section 31.9: Integer factorization〉. 《Introduction to Algorithms》 i판. Cambridge, MA: MIT Press. 975–980쪽. ISBN 978-0-262-03384-8.  (이 문단은 폴라드 로 알고리즘만을 다룬다).
  3. Brent, Richard P. (1980). “An Improved Monte Carlo Factorization Algorithm”. 《BIT》 20: 176–184. doi:10.1007/BF01933190. 
  4. Brent, R.P.; Pollard, J. M. (1981). “Factorization of the Eighth Fermat Number”. 《Mathematics of Computation》 36 (154): 627–630. doi:10.2307/2007666. 
  5. Steven D., Galbraith (2012). 〈14.2.5 Towards a rigorous analysis of Pollard rho〉. 《Mathematics of Public Key Cryptography》. Cambridge University Press. 272–273쪽. ISBN 9781107013926. .

참고 문헌편집

  • Katz, Jonathan; Lindell, Yehuda (2007). 〈Chapter 8〉. 《Introduction to Modern Cryptography》. CRC Press. 
  • Samuel S. Wagstaff, Jr. (2013). 《The Joy of Factoring》. Providence, RI: American Mathematical Society. 135-138쪽. ISBN 978-1-4704-1048-3. 

외부 링크편집