폴라드 로 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻|폴라드 로 이산 로그 알고리즘|소인수분해 알고리즘|이산 로그 알고리즘}}

'''폴라드 로 알고리즘'''({{llang|en|Pollard's rho algorithm}})은 [[존 폴라드]]가 1975년에 고안한 [[소인수분해]] [[알고리즘]]이다.<ref>{{저널 인용|성=Pollard|이름=J. M.|저자링크=존 폴라드|연도=1975|제목=A Monte Carlo method for factorization|저널=BIT Numerical Mathematics|권=15|호=3|쪽=331–334|doi=10.1007/bf01933667}}</ref> 이 알고리즘은 저장 공간을 적게 사용하고 소인수분해하는 데 걸리는 실행 시간은 소인수분해하려는 [[합성수]]의 가장 작은 [[소인수]]의 제곱근에 비례하는 알고리즘이다.

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

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

[[파일:Pollard rho cycle.svg|썸네일|그리스 문자 ρ를 닮은 순환 그래프]]

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

== 알고리즘 ==
이 알고리즘은 인수분해 하려는 정수 {{수학 변수|n}}과 {{수학 변수|x}}에 대한 다항식을 {{수학 변수|n}}으로 나눈 나머지인 연산 {{#tag:math|g(x)}}를 입력으로 받는다. 폴라드가 만든 원래 알고리즘에서는 <math>g(x) = (x^2 - 1) \bmod n</math>이였지만, 최근에 사용할 때에는 보통 <math>g(x) = (x^2 + 1) \bmod n</math>을 더 많이 사용한다. 출력값으로는 {{수학 변수|n}}의 자명하지 않은 소인수이거나 '실패'이며, 폴라드 로 알고리즘은 다음의 단계를 따라 실행된다:<ref>{{서적 인용|성=Cormen|이름=Thomas H.|성2=Leiserson|이름2=Charles E.|성3=Rivest|이름3=Ronald L.|저자링크3=로널드 라이베스트|성4=Stein|이름4=Clifford|저자앰퍼샌드=yes|장=Section 31.9: Integer factorization|제목=[[Introduction to Algorithms]]|연도=2009|판=third|출판사=MIT Press|위치=Cambridge, MA|쪽=975–980|isbn=978-0-262-03384-8}} (이 문단은 폴라드 로 알고리즘만을 다룬다).</ref>

     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}}는 각각 핵심 개념 문단의 {{#tag:math|x_i}}와 {{#tag:math|x_j}}에 대응한다. 이 알고리즘은 {{수학 변수|n}}이 합성수일 경우에도 자명하지 않은 인수를 찾는데 실패할 수 있다는 점을 주의해야 한다. 이러한 경우, 시작 값으로 2가 아닌 다른 값을 이용하거나 다른 {{#tag:math|g(x)}}를 이용하여 다시 수행할 수 있다.

== 소인수분해 예제 ==
먼저 <math>n = 8051</math>, 그리고 <math>g(x) = (x^2 + 1) \bmod 8051</math>이라고 가정했을 때,
{| class="wikitable" style="text-align:right"
! width=30 | {{수학 변수|i}} || width=60 | {{수학 변수|x}} || width=60 | {{수학 변수|y}} || {{수학|GCD({{절댓값|''x'' &minus; ''y''}}, 8051)}}
|-
| 1 || 5 || 26 || 1
|-
| 2 || 26 || 7474 || 1
|-
| 3 || 677 || 871 || 97
|-
| 4 || 7474 || 1481 || 1
|}

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

== 변형 ==
[[리차드 브렌트]]는 1980년에 이 알고리즘을 조금 더 효율적으로 바꾼 폴라드 로 알고리즘을 발표했다. 브랜트의 알고리즘은 폴라드 로 알고리즘과 핵심 개념은 같지만 반복을 만들어 소인수를 얻어내는 방법이 [[플로이드 순환 검출 알고리즘]]에서 [[순환 검출#브렌트 알고리즘|브렌트 순환 검출 방법]]으로 바꾸어 개량한 알고리즘이다.<ref>{{저널 인용|성=Brent|이름=Richard P.|저자링크=리차드 브렌트|연도=1980 |제목=An Improved Monte Carlo Factorization Algorithm|저널=BIT|권=20|쪽=176–184|url=http://maths-people.anu.edu.au/~brent/pub/pub051.html|doi=10.1007/BF01933190}}</ref>

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

== 적용 ==
폴라드 로 알고리즘은 타원곡선 방법 비슷하게과 작은 인수를 가진 수의 경우에는 매우 빠르지만 모든 인수가 클 경우에는 느리다. 폴라드 로 알고리즘의 가장 주목할 만한 성과는 [[페르마 수]] {{수학|''F''<sub>8</sub>}}을 소인수분해한 것이다: {{수학|''F''<sub>8</sub>}} = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321<ref>{{저널 인용|성1=Brent|이름1=R.P.|저자링크1=리차드 브렌트|성2=Pollard|이름2=J. M.|저자링크2=존 폴라드|연도=1981|제목=Factorization of the Eighth Fermat Number|저널=Mathematics of Computation|권=36|호=154|쪽=627–630|doi=10.2307/2007666|doi-access=free}}</ref>. 소인수 {{수학 변수|p}} = 1238926361552897은 다른 인수에 비해 훨씬 작았기 때문에 ρ 알고리즘은 {{수학|''F''<sub>8</sub>}}을 소인수분해 하기에 적절하였고, 소인수분해 과정은 [[UNIVAC]] [[유니박 1100/2200 시리즈|1100/42]]에서 2시간이 걸렸다. 또한 이 알고리즘은 소인수분해하고 싶은 수의 비교적 작은 소인수들을 얻어내는 데 많이 쓰인다.

== {{수학 변수|n}} = 10403 = 101 · 103 인 예제 ==
다음은 또다른 변형 알고리즘으로, 한 수열만 계산하며 수열을 반복하여 계산할 때마다 최대공약수를 계산한다.

=== C 코드 예제 ===
다음 예제 코드는 시작값 {{수학 변수|x}} = 2로 10403의 인수 101을 찾는다.
<syntaxhighlight lang="c">

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

=== Python 코드 예제 ===
<syntaxhighlight lang="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()
</syntaxhighlight>

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

{| class="wikitable" style="text-align:right;"
! {{#tag:math|x}} !! {{#tag:math|x_{fixed} }} !! {{#tag:math|x \bmod 101}} !! {{#tag:math|x_{fixed} \bmod 101}} !! 단계
|-
| 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 ||{{rh|align=right}}| 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 ||{{rh|align=right}}| 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 ||{{rh|align=right}}| 72 || '''72''' || 23
|}

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

== 복잡도 ==
폴라드 로 알고리즘에서 쓰이는 유사 난수 <math>x = g(x)</math>가 실제로 완전한 난수라고 가정한다면, [[생일 역설]]에 의해 폴라드 로 알고리즘은 <math>O(\sqrt p)\le O(n^{1/4})</math> 시간 안에 입력값의 인수를 출력할 수 있다. 실제로 폴라드 로 알고리즘은 대략 이 정도 시간에 작동하는 것이 알려져 있지만, 이는 아직 확률적인 추측이며 엄밀한 증명은 아직 이루어지지 않았다.<ref>{{서적 인용|제목=Mathematics of Public Key Cryptography|성=Steven D.|이름=Galbraith|출판사=Cambridge University Press|연도=2012|isbn=9781107013926|contribution=14.2.5 Towards a rigorous analysis of Pollard rho|쪽=272–273|url=https://books.google.com/books?id=owd76BElvosC&pg=PA272}}.</ref>

== 같이 보기 ==
* [[폴라드 로 이산 로그 알고리즘]]
* [[폴라드의 캥거루 알고리즘]]

== 각주 ==
{{각주}}

== 참고 문헌 ==
* {{서적 인용|성=Katz|이름=Jonathan|성2=Lindell|이름2=Yehuda|장=Chapter 8|제목=Introduction to Modern Cryptography|url=https://archive.org/details/Introduction_to_Modern_Cryptography|연도=2007|출판사=CRC Press}}
* {{서적 인용|저자=Samuel S. Wagstaff, Jr.|제목=The Joy of Factoring|출판사=American Mathematical Society|위치=Providence, RI|연도=2013|isbn=978-1-4704-1048-3|url=http://www.ams.org/bookpages/stml-68|쪽=135-138}}

== 외부 링크 ==
* [https://sofosband.wixsite.com/pversusnp/single-post/2018/08/27/Factorising-part-2---Pollards-Rho-algorithm 입문자 수준에서 설명한 폴라드 로 알고리즘에 대한 종합 기사] (영어 사이트)
* {{매스월드|제목=Pollard rho Factorization Method|id=PollardRhoFactorizationMethod}}
<!-- Dead link: * [http://www.patrickkonsor.com/code/ Java Implementation] -->
* [https://introcs.cs.princeton.edu/java/99crypto/PollardRho.java.html 자바로 구현한 폴라드 로 알고리즘]
* [https://forthmath.blogspot.com/2020/01/about-pollard-rho.html About Pollard rho]

{{수론 알고리즘}}

[[분류:소인수 분해 알고리즘]]