폴라드의 P-1 알고리즘

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

1. 개요
2. 기본 개념
3. 알고리즘
4. 실행 시간
5. 예시
6. 여러 소인수
7. 2단계 변형
8. 응용
9. 다른 소인수분해 알고리즘과의 관계
참조

1. 개요

폴라드의 p-1 알고리즘은 합성수 n의 소인수를 찾는 정수 인수분해 알고리즘이다. 페르마 소정리를 기반으로 하며, n의 소인수 p에 대해 p-1이 작은 소수들의 곱으로 표현될 때 효과적으로 작동한다. 이 알고리즘은 평활도 경계 B를 설정하고, B 이하의 소수들의 거듭제곱을 곱하여 M을 계산한다. 임의의 정수 a를 선택하여 a^M - 1과 n의 최대공약수를 계산하고, 그 결과가 1과 n 사이의 값이면 n의 약수를 찾은 것이다. 알고리즘의 실행 시간은 B의 값에 따라 달라지며, GIMPS와 같은 소인수분해 프로젝트에서 메르센 수의 약수를 찾는 데 활용된다.

더 읽어볼만한 페이지

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

폴라드의 P-1 알고리즘
알고리즘 정보
종류	정수 인수분해 알고리즘
개발자	존 폴라드
발표 연도	1974년
작동 방식
기본 원리	p-1이 작은 소인수들의 곱으로 이루어진 경우, n의 약수 p를 찾음
시간 복잡도	O(B√n) (B는 소인수 크기의 상한)
공간 복잡도	O(1)
최적 조건	인수 p에 대해, p-1이 작은 소수들의 곱으로 표현될 때 효과적임
단점	모든 소인수 p에 대해 p-1이 큰 소수를 포함하면 비효율적임

2. 기본 개념

''n''이 어떤 소인수 p를 가지고 있는 합성수라고 하자. 페르마 소정리에 따르면, p와 서로소인 어떤 양의 정수 a와 모든 양의 정수 K에 대하여 다음 관계가 성립한다.

: $a^{K(p-1)} \equiv 1\pmod{p}$

만약 어떤 수 x가 n의 약수로 나눴을 때 나머지가 1이라면, gcd(x-1, n)은 그 약수로 나누어떨어진다.

이 알고리즘은 어떤 한계값인 ''B'' 미만의 소수들의 거듭제곱수들을 곱하여 이 수를 많은 소인수들을 가지고 있는 매우 큰 p-1의 배수로 만든다. 그 후, 임의의 정수 ''x''와 앞에서 구한 p-1의 배수인 w로 $x^w \bmod n$ 를 계산하면서 gcd(''x'' - 1, ''n'')이 n의 약수가 되는지 확인한다.

3. 알고리즘

''n''이 어떤 소인수 p를 가지고 있는 합성수라고 할 때, 페르마 소정리에 따르면, p와 서로소인 어떤 양의 정수 a와 모든 양의 정수 K에 대하여 다음 관계가 성립한다.^[1]

: $a^{K(p-1)} \equiv 1\pmod{p}$

만약 어떤 수 x가 n의 약수로 나눴을 때 나머지가 1이라면, gcd(x-1, n)은 그 약수로 나누어떨어진다.^[1]

이 알고리즘은 어떤 한계값인 ''B'' 미만의 소수들의 거듭제곱수들을 곱하여 이 수를 많은 소인수들을 가지고 있는 매우 큰 p-1의 배수로 만든다. 그 후, 임의의 정수 ''x''와 앞에서 구한 p-1의 배수인 w로 $x^w \bmod n$ 를 계산하면서 gcd(''x'' - 1, ''n'')이 n의 약수가 되는지 확인한다.^[1]

기본 알고리즘은 다음과 같이 작성할 수 있다.^[1]

:'''입력:''' 어떤 합성수 n

:'''출력:''' n의 비자명한 약수 또는 실패

:# 어떤 수 ''B''를 고른다.

:# $M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$ 으로 M의 값을 구한다.

:# 무작위로 n과 서로소인 수 a를 고른다. 만약 n이 홀수라면, 항상 a를 2로 정해도 된다.

:# ''g'' = gcd(''a''^''M'' − 1, ''n'')를 이용하여 g의 값을 구한다.

:# 만약 1 < ''g'' < ''n'' 이면 ''g''를 출력한다.

:# 만약 ''g'' = 1인 경우 더 큰 ''B''를 선택하고 2 단계로 이동하거나 실패를 출력한다.

:# 만약 ''g'' = n인 경우 더 작은 ''B''를 선택하고 2단계로 이동하거나 실패를 출력한다.

이 알고리즘의 실행 시간은 O(''B'' × log ''B'' × log² ''n'')이다. 1단계에서 정한 ''B''의 값이 클수록 실행 속도가 느려지지만 비자명한 약수를 출력할 가능성이 커진다.^[1]

4. 실행 시간

이 알고리즘의 실행 시간은 O(''B'' × log ''B'' × log² ''n'')이다. 여기서 ''B''는 처음에 정하는 값으로, ''B'' 값이 클수록 실행 속도는 느려지지만 비자명한 약수를 찾을 가능성이 더 커진다.^[1]

알고리즘은 점증적이므로 경계를 지속적으로 증가시키면서 계속 실행할 수 있다.^[1]

''p''가 ''n''의 가장 작은 소인수일 때, ''p'' - 1을 보다 작은 크기의 난수로 모델링할 수 있다고 가정한다. 딕슨의 정리에 따르면, 그러한 수의 가장 큰 인수가 (''p'' - 1)^''1/ε''보다 작을 확률은 대략 ''ε''^-''ε''이며, 따라서 ''B'' 값이 ''n''^1/6일 때 인수분해를 얻을 확률은 약 3^-3 = 1/27이다.^[1]

실제로 인수가 어느 정도 커지면 타원 곡선 방법이 폴라드 ''p'' - 1 방법보다 빠르다. ''p'' - 1 방법을 ''B'' = 2³²까지 실행하면 모든 64비트 인수의 1/4과 모든 96비트 인수의 1/27을 찾을 수 있다.^[1]

5. 예시

''n'' = 299를 소인수분해하는 과정은 다음과 같다.

# ''B'' = 5를 선택한다.

# ''M'' = 2² × 3¹ × 5¹이다.

# ''a'' = 2를 선택한다.

# ''g'' = gcd(''a''^''M'' - 1, ''n'') = 13이다.

# 1 < 13 < 299 이므로 13을 출력한다.

# 299 / 13 = 23이 소수이므로 299 = 13 × 23으로 완전히 소인수분해된다.

6. 여러 소인수

''n''이 어떤 소인수 p를 가지고 있는 합성수라고 하자. 페르마 소정리에 따르면, p와 서로소인 어떤 양의 정수 a, 그리고 모든 양의 정수 K에 대하여 다음 관계가 성립한다.^[1]

: $a^{K(p-1)} \equiv 1\pmod{p}$

만약 어떤 수 x가 n의 약수로 나눴을 때 나머지가 1이라면, gcd(x-1, n)은 그 약수로 나누어떨어진다.^[1]

이 알고리즘은 어떤 한계값인 ''B'' 미만의 소수들의 거듭제곱수들을 곱하여 이 수를 많은 소인수들을 가지고 있는 매우 큰 p-1의 배수로 만든다. 그 후, 임의의 정수 ''x''와 앞에서 구한 p-1의 배수인 w로 $x^w \bmod n$ 를 계산하면서 gcd(''x'' - 1, ''n'')이 n의 약수가 되는지 확인한다.^[1] 만약 n의 소인수인 p에 대하여 p-1이 여러 작은 소인수들로 나누어떨어지면, 어떤 특정한 값 이후로는 이 알고리즘은 다시 n을 결과로 출력할 수도 있다.^[1] ''n''의 모든 소인수 ''p''에 대해, ''p'' - 1이 작은 소수로 나누어 떨어질 수 있으며, 이 경우 폴라드 ''p'' - 1 알고리즘은 단순히 ''n''을 반환한다.^[1]

7. 2단계 변형

기본 알고리즘의 변형이 사용되기도 한다. ''p'' − 1이 모든 인수를 ''B''보다 작도록 요구하는 대신, 한 개의 인수를 제외한 모든 인수가 ''B''₁보다 작고, 나머지 인수는 ''B''₂ ≫ ''B''₁|B2 >> B1^영어보다 작도록 요구한다. 기본 알고리즘과 동일한 첫 번째 단계를 완료한 후, 새로운

: $M' = \prod_{\text{소수 }q \le B_2} q^{ \lfloor \log_q B_2 \rfloor }$

를 ''B''₂에 대해 계산하고, gcd(''a''^''M''' − 1, ''n'')|gcd(a^M' − 1, n)^영어을 확인하는 대신,

: $Q = \prod_{\text{소수 } q \in (B_1, B_2]} (H^q - 1)$

를 계산하며 여기서 ''H'' 이고, gcd(''Q'', ''n'')|gcd(Q, n)^영어가 ''n''의 비자명한 인수를 생성하는지 확인한다. 이전과 마찬가지로 지수 연산은 모듈로 ''n''으로 수행할 수 있다.

{''q''₁, ''q''₂, …}를 구간 (''B''₁, ''B''₂]|(B1, B2]^영어에서 연속적인 소수라고 하고, ''d''_''n'' = ''q''_''n'' − ''q''_''n''−1를 연속적인 소수 사이의 차이라고 하자. 일반적으로 ''B''₁ > 2|B1 > 2^영어이므로 ''d''_''n''|dn^영어은 짝수이다. 소수의 분포는 ''d''_''n''이 모두 비교적 작도록 한다. ''d''_''n'' ≤ ln² ''B''₂|dn ≤ ln² B2^영어가 제안된다. 따라서 ''H''²|H²^영어, ''H''⁴|H⁴^영어, ''H''⁶|H⁶^영어, … (mod ''n'') 값을 표에 저장할 수 있으며, ''H''^''q''_''n''|H^qn^영어은 ''H''^{''q''_''n''−1}⋅''H''^''d''_''n''|H^qn-1⋅H^dn^영어에서 계산하여 지수 연산의 필요성을 줄일 수 있다.

8. 응용

GIMPS에서는 어떤 메르센 수의 약수를 구할 때 이 알고리즘을 개선한 방법으로 약수를 구하기도 한다.^[1]

https://gitlab.inria.fr/zimmerma/ecm GMP-ECM 패키지는 ''p'' − 1 방법의 효율적인 구현을 포함하고 있다. Prime95와 MPrime은 Great Internet Mersenne Prime Search의 공식 클라이언트로, 잠재적인 후보를 제거하기 위해 p - 1 알고리즘의 수정된 버전을 사용한다.

9. 다른 소인수분해 알고리즘과의 관계

GIMPS에서는 어떤 메르센 수의 약수를 구할 때 이 알고리즘을 개선한 방법으로 약수를 구하기도 한다.^[1] 실제로 인수가 어느 정도 커지면 타원 곡선 방법이 폴라드 ''p'' − 1 방법보다 빠르다.^[1]

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

문의하기 : help@durumis.com