폴라드 로 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 핵심 개념
3. 알고리즘
- 3.1. 기본 알고리즘
- 3.2. 브렌트 변형 알고리즘 (Brent's variant)
4. 소인수분해 예제
5. 변형 및 개선
6. 적용 및 활용
7. 복잡도
참조

1. 개요

폴라드 로 알고리즘은 정수를 소인수분해하는 데 사용되는 알고리즘으로, 유사 난수 수열을 생성하여 소인수를 찾는다. 이 알고리즘은 다항식 g(x)를 사용하여 수열을 만들고, 플로이드 순환 찾기 알고리즘을 통해 수열의 반복을 감지하여 최대공약수를 계산한다. 브렌트 변형 알고리즘은 이 알고리즘의 개선된 버전으로, 순환 검출 방식을 변경하여 효율성을 높였다. 폴라드 로 알고리즘은 작은 소인수를 가진 수의 소인수분해에 특히 유용하며, 페르마 수 F8의 소인수분해에 성공적으로 사용된 바 있다. 알고리즘의 시간 복잡도는 O(n1/4)로 추정되지만, 이는 엄밀하게 증명되지 않았다.

더 읽어볼만한 페이지

소인수 분해 알고리즘 - 쇼어 알고리즘
쇼어 알고리즘은 소인수분해 및 이산 로그 문제를 해결하는 양자 알고리즘으로, 양자 위상 추정 알고리즘과 연분수 알고리즘을 활용하며, 공개 키 암호화 방식을 깨뜨릴 수 있다.
소인수 분해 알고리즘 - 연분수 소인수분해 알고리즘
연분수 소인수분해 알고리즘은 합성수 $n$ 의 제곱근을 연분수로 전개하여 얻은 값으로 $x^2 \equiv y^2 \pmod n$ 를 만족하는 $x$ 와 $y$ 를 찾아 $n$ 의 약수를 구하는 알고리즘이다.

폴라드 로 알고리즘
알고리즘 정보
폴라드 로 알고리즘을 설명하는 다이어그램
분류	정수 인수분해 알고리즘
개발자	존 폴라드
발표 연도	1975년
세부 정보
종류	특수 목적 알고리즘
시간 복잡도	O(n^(1/4))
공간 복잡도	O(1)

2. 핵심 개념

폴라드 로 알고리즘의 핵심은 소인수분해하려는 수 $n$ 에 대해 유사난수 수열을 만들고, 이 수열의 순환 구조를 이용하는 것이다. 이 수열은 $n$ 으로 나눈 나머지 연산을 사용하며, 주로 $g(x) = (x^2 + 1) \bmod n$ 과 같은 다항식이 쓰인다.^[2] 초기값(보통 2)을 넣어 $x_1 = g(2)$ , $x_2 = g(g(2))$ 와 같이 수열을 만든다.

이 수열은 $n$ 의 소인수 $p$ 에 대한 또 다른 수열 $\{x_k \bmod p\}$ 와 관련이 있다. $p$ 를 모르더라도, 생일 역설에 의해 $\{x_k \bmod p\}$ 수열이 $\{x_k\}$ 보다 먼저 반복될 가능성이 높다.^[2]

플로이드 순환 찾기 알고리즘으로 반복을 찾는다. 두 변수 $x_i$ , $x_j$ 를 두고, 하나는 한 단계씩, 다른 하나는 두 단계씩 움직이며 $\gcd(x_i - x_j, n) \ne 1$ 인지 확인한다. 이 조건이 맞으면, $\{x_k \bmod p\}$ 에서 반복이 일어난 것이고, 최대공약수(GCD)는 $n$ 의 약수가 된다.^[2]

이 순환 구조는 유향 그래프로 나타내면 ρ(로)와 비슷하여 "폴라드 로 알고리즘"이라 불린다.^[2]

최대공약수가

n

자신이면 (두 수열이 동시 순환) 알고리즘은 실패한 것이므로, 다른 초기값으로 다시 시도한다.

2. 1. 유사난수 수열

폴라드 로 알고리즘에서 사용되는 유사난수 수열은 소인수분해하려는 정수

n

에 대해, 특정 다항식

g(x)

를 이용하여 생성된다. 예를 들어,

g(x) = (x^2 + 1) \bmod n

과 같은 다항식을 사용한다. 이 수열은 초기값(주로 2)을 설정하고, 다음과 같이 진행된다:

x_1 = g(2)

,

x_2 = g(g(2))

,

x_3 = g(g(g(2)))

, ... . 즉, 이전 항의 값을 다항식

g(x)

에 대입하여 다음 항을 계산하는 방식이다.^[2]

이 수열은

n

의 자명하지 않은 인수(1이 아닌 인수)

p

에 대해, 또 다른 수열

\{x_k \bmod p\}

와 관련이 있다. 하지만

p

를 미리 알 수 없기 때문에, 이 두 번째 수열은 직접 계산할 수 없다. 폴라드 로 알고리즘의 핵심 아이디어는 이 두 수열 사이의 관계를 이용하는 것이다.^[2]

유한한 수의 값만 가질 수 있기 때문에,

\{x_k\}

수열과

\{x_k \bmod p\}

수열은 언젠가 반복될 수 밖에 없다. 만약 이 수열들이 완전한 난수처럼 작동한다면, 생일 역설에 따라 반복이 발생하기 전까지 나타나는 서로 다른

x_k

의 개수는 대략

O(\sqrt N)

(여기서

N

은 가능한 값의 개수)이다. 따라서

\{x_k \bmod p\}

수열은

\{x_k\}

수열보다 먼저 반복될 가능성이 높다.^[2]

한번 반복이 시작되면, 이후의 값들은 이전 값에 의해서만 결정되므로 수열은 순환하게 된다. 이러한 순환 구조는

x_1 \bmod p

,

x_2 \bmod p

등의 값을 유향 그래프의 꼭짓점으로 표현했을 때 그리스 문자 ρ와 유사한 형태를 띠기 때문에, 이 알고리즘에 "폴라드 로 알고리즘"이라는 이름이 붙었다.^[2]

2. 2. 순환 구조

유사난수 수열은 유한한 값들을 가지므로, 언젠가는 반드시 반복되는 순환 구조를 가진다. 이 순환 구조는 유향 그래프의 꼭짓점으로 표현하면 그리스 문자 ρ(로)와 비슷한 형태를 띠기 때문에 "폴라드 로 알고리즘"이라는 이름이 붙었다.^[2]

이러한 순환 구조는 플로이드 순환 찾기 알고리즘을 통해 발견할 수 있다. 알고리즘은 두 개의 숫자 x_i와 x_j를 வைத்து, 한 숫자는 한 칸씩, 다른 숫자는 두 칸씩 이동하면서 x_i와 x_j의 차이와 n의 최대공약수(GCD)가 1이 아닌지 확인한다. 만약 최대공약수가 1이 아니라면, 이는 순환 구조가 발견되었다는 것을 의미한다.^[2]

2. 3. 플로이드 순환 찾기 알고리즘 (Floyd's cycle-finding algorithm)

플로이드 순환 찾기 알고리즘은 유사난수 수열의 순환을 탐지하는 데 사용된다. 폴라드 로 알고리즘에서는 이 방법을 사용하여 소인수 분해를 수행한다. 두 개의 변수

x_i

와

x_j

를 사용하는데, 하나는 한 단계씩 (

x_i

), 다른 하나는 두 단계씩 (

x_j

) 이동하면서 순환을 찾는다.^[2]

구체적으로, 알고리즘 작동 방식은 다음과 같다.

1. 두 수

i

와

j

(즉,

x_i

와

x_j

)를 설정한다.

2. 매 단계마다

x_i

는 수열의 다음 수로 이동하고,

x_j

는 두 단계씩 이동한다.

3.

\gcd(x_i - x_j, n) \ne 1

인지 확인한다. 여기서

n

은 소인수분해 하려는 수이다.

4. 만약 위 조건이 만족되면, 이는

\{x_k \bmod p\}

수열에 반복이 있음을 의미한다. (

x_i \bmod p = x_j \bmod p

)^[2]

5. 이때,

x_i

와

x_j

의 차이는

p

의 배수이므로, 결과값인 최대공약수(GCD)는 1이 아닌

n

의 약수가 된다.^[2]

이 과정에서 두 수열이 동시에 순환하여 GCD가

n

자신이 될 수도 있는데, 이 경우에는 알고리즘이 실패한 것이므로 다른 초기값으로 다시 시도해야 한다.^[2]

이 알고리즘은 생일 문제에서 착안한 것으로,

1.177\sqrt{p}

개의 숫자를 임의로 선택했을 때 절반 이상의 확률로 두 숫자가

p

로 나누어진다는 관측 결과를 바탕으로 한다.^[2] 즉, 의사 난수 발생에

n

을 법으로 사용하고, 같은 난수열을 두 번 이용하여 한쪽은 순차적으로, 다른 한쪽은 한 칸씩 건너뛰며 난수열을 생성한다. 이 두 값을 각각

x

와

y

라고 하고, 반복마다

|x - y|

와

n

의 GCD를 구한다. 만약 이 GCD가

n

이 되면 알고리즘은 실패하고, 이는

x = y

임을 의미하며 플로이드 순환 찾기 알고리즘에 의해 이후 의사 난수열이 이전의 반복이 됨을 나타낸다.

2. 4. 최대공약수 (GCD)

플로이드 순환 찾기 알고리즘을 사용하여 두 수

x_i

와

x_j

를 추적한다. 매 단계마다

x_i

는 수열에서 한 칸 이동하고,

x_j

는 두 칸 이동한다. 그런 다음

\gcd(|x_i - x_j|, n)

을 계산하여 이 값이 1이 아닌지 확인한다. 1이 아니라면, 이는

n

의 자명하지 않은 약수를 찾았음을 의미한다.^[2]

\gcd(|x_i - x_j|, n) \ne 1

인 이유는

\{x_k \bmod p\}

수열에서 반복이 발생했기 때문이다. 즉,

x_i \bmod p = x_j \bmod p

이며, 이는

x_i

와

x_j

의 차이가

p

의 배수임을 뜻한다.

하지만 두 수열이 동시에 순환하여 최대공약수(GCD)가

n

자체가 되는 경우도 발생할 수 있다. 이 경우 알고리즘은 소인수 분해에 실패하며, 다른 초기값으로 다시 시도해야 한다.

2. 5. 생일 역설 (Birthday Paradox)

생일 문제에 따르면, 가능한 값이

N

개일 때,

O(\sqrt N)

개의 난수를 생성하면 그중에 같은 값이 있을 확률이 높아진다. 폴라드 로 알고리즘은 이러한 원리를 이용한다. 즉,

n

의 자명하지 않은 인수를

p

라 할 때,

\{x_k \bmod p\}

수열이

\{x_k\}

수열보다 더 빨리 반복될 가능성이 높다는 점을 활용한다.^[2]

\{x_k\}

와

\{x_k \bmod p\}

수열은 유한한 개수의 값만 가질 수 있으므로, 언젠가는 반드시 반복된다. 만약 이 수열들이 완전한 난수라면, 생일 문제에 의해 반복이 시작되기 전까지 등장하는 서로 다른 값의 개수는 대략

O(\sqrt N)

개이다. 따라서

\{x_k \bmod p\}

수열은

\{x_k\}

수열보다 먼저 반복될 가능성이 높다. 한번 반복이 시작되면, 이후의 값들은 이전 값에 의해서만 결정되므로 수열은 계속 순환하게 된다.^[2]

이러한 순환 구조는

x_1 \bmod p

,

x_2 \bmod p

등의 값을 유향 그래프의 꼭짓점으로 표현했을 때 그리스 문자 ρ (로)와 비슷하게 생겼기 때문에, 이 알고리즘은 '폴라드 로 알고리즘'이라는 이름을 가지게 되었다.

3. 알고리즘

폴라드 로 알고리즘은 인수분해하려는 정수 n과, x에 대한 다항식을 n으로 나눈 나머지 연산인 g(x)를 입력으로 받는다. 출력은 n의 자명하지 않은 인수이거나 실패이다.

이 알고리즘은 크게 기본 알고리즘과 이를 개선한 브렌트 변형 알고리즘으로 나뉜다.

기본 알고리즘: 폴라드가 처음 제시한 알고리즘이다. 자세한 단계는 하위 섹션 '기본 알고리즘'에 설명되어 있다.
브렌트 변형 알고리즘: 리차드 브렌트가 1980년에 발표한 개선된 알고리즘으로, 순환 검출 방법을 최적화하여 속도를 향상시켰다. 자세한 내용은 하위 섹션 '브렌트 변형 알고리즘 (Brent's variant)'에서 확인할 수 있다.

3. 1. 기본 알고리즘

이 알고리즘은 인수분해할 정수 ''n''과 ''x''에 대한 다항식을 ''n''으로 나눈 나머지인 연산 g(x)^영어를 입력으로 받는다. 폴라드가 만든 원래 알고리즘에서는 g(x) = (x² - 1) mod n^영어이었지만, 최근에는 g(x) = (x² + 1) mod n^영어을 더 많이 사용한다. 출력값으로는 ''n''의 자명하지 않은 소인수이거나 '실패'이다.^[8]

알고리즘은 다음 단계를 따라 실행된다.^[8]^[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''는 각각 핵심 개념 문단의 x_i^영어와 x_j^영어에 대응한다. 이 알고리즘은 ''n''이 합성수일 경우에도 자명하지 않은 인수를 찾는 데 실패할 수 있다. 이러한 경우, 시작 값으로 2가 아닌 다른 값을 이용하거나 다른 g(x)^영어를 이용하여 다시 수행할 수 있다.^[8]

다른 g(x)^영어로는 g(x) = (x² + b) mod n^영어를 사용할 수 있으며, 여기서 1 ≤ b < n-2^영어이다. ''f''(''x'')로는 선형 합동법 등이 고려될 수 있다. 또한, 상기 알고리즘에서는 하나의 약수만 찾을 수 있으므로, 완전한 소인수 분해를 수행하려면 이를 반복 적용할 필요가 있다.

3. 2. 브렌트 변형 알고리즘 (Brent's variant)

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

폴라드와 브렌트는 이 알고리즘을 더욱 개선했다. 이들은

\gcd (a,n) > 1

일 경우, 모든 양의 정수 b에 대하여

\gcd (ab,n) > 1

인 것을 이용하였다. 예를 들어, 모든 단계에서

\gcd (|x-y|,n)

을 계산하는 대신, z를 100개의 연속된

|x-y|

의 곱을 n으로 나눈 나머지로 정의하고

\gcd (z,n)

을 계산하는 방법 등으로 원래 알고리즘에 비해 속도를 개선하였다. 이 방법은 최대공약수를 구하는 연산을 100번 반복하던 것을 곱셈을 이용하여 n으로 나눈 나머지 연산 99번과 최대공약수를 구하는 연산 1번으로 바꾸었기 때문에 속도가 증가한다. 이 방법은 가끔씩 n이 소수의 제곱수 같은 약수를 포함하고 있을 때에는 알고리즘이 실패할 수도 있는데, 그럴 경우에는

\gcd(z,n)=1

인 수열의 항으로 돌아가서 다시 일반적인 폴라드 로 알고리즘을 실행해도 충분히 그 소인수를 얻어낼 수 있다.

1980년에 리처드 브렌트는 이 알고리즘을 변형하여 속도를 향상시킨 버전을 발표했다. 그는 폴라드와 동일한 아이디어를 기반으로 했지만, 플로이드의 순환 감지법보다 빠르게 순환을 감지하는 방법을 사용했다.

4. 소인수분해 예제

$n = 8051$ 이고, $g(x) = (x^2 + 1) \bmod 8051$ 이라고 가정하자.

i	x	y	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이 다시 나올 수도 있다.

5. 변형 및 개선

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

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

6. 적용 및 활용

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

예를 들어, 733MHz의 워크스테이션에서 전혀 최적화하지 않은 이 알고리즘을 구현하면, 0.5초 이내에 6번째 페르마 수 18446744073709551617(20자리 숫자)의 소인수 274177을 발견할 수 있다. 그러나 두 개의 10자리 소수의 곱으로 주어지는 거의 같은 크기의 반소수 10023859281455311421에 대해서는 같은 워크스테이션에서 9초 정도 걸렸다.

7. 복잡도

다음은 ''p''와 ''q''가 10403의 소인수라는 정보를 알고리즘 수행 전에 알 수 없다는 점을 보여주는 표이다. 이 표는 알고리즘의 작동 방식을 설명하기 위해 추가되었다. 초깃값 x^영어 = 2로 설정하고 알고리즘을 적용하면 다음과 같다.

x^영어	x_fixed^영어	x^영어 mod 101	x_fixed^영어 mod 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	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단계에서 x^영어 ≡ x_fixed^영어 (mod 101)이 될 때까지 알고리즘이 알아내지 못한다. 이때 gcd (x^영어 - x_fixed^영어, ''n'') = gcd (2799 - 9970, ''n'')은 ''p'' = 101이 되어 소인수를 찾게 된다.

만약 폴라드 ρ 알고리즘에서 발생하는 의사 난수 x^영어 = g(x^영어)가 실제 난수였다면, 생일 문제에 따라 O^영어(√''p'')≤ O^영어(''n''^1/4)번의 반복 내에 절반의 성공을 거둘 것이다. 이러한 분석이 실제 로(rho) 알고리즘에도 적용된다고 여겨지지만, 이는 경험적인 주장에 불과하며, 알고리즘에 대한 엄밀한 분석은 여전히 해결되지 않은 상태이다.^[6]

이 알고리즘에서는 실행 시간과 소인수 발견 확률이 상반 관계에 있다. ''n''이 같은 자릿수의 두 종류의 소수의 곱일 때, O(''n''^1/4 ''polylog''(''n'')) 단계 실행으로 발견 확률이 약 50%가 된다. 이는 휴리스틱에 의한 근사치이며, 이 알고리즘의 정확한 분석은 미해결 문제이다.

참조

_[1] 논문 A Monte Carlo method for factorization https://www.cs.cmu.e[...]
_[2] 서적 Introduction to Algorithms MIT Press
_[3] 논문 An Improved Monte Carlo Factorization Algorithm http://maths-people.[...]
_[4] 문서 Exercise 31.9-4 in CLRS
_[5] 논문 Factorization of the Eighth Fermat Number
_[6] 서적 Mathematics of Public Key Cryptography https://books.google[...] Cambridge University Press
_[7] 논문
_[8] 서적
_[9] 논문 http://maths-people.[...]
_[10] 논문
_[11] 서적 https://books.google[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com