소인수 분해는 주어진 정수를 소수들의 곱으로 표현하는 과정으로, 수학적 이론부터 암호학까지 다양한 분야에서 중요한 역할을 합니다. 이번 포스팅에서는 대표적인 소인수 분해 알고리즘들을 소개하고, 각각의 코드 구현과 시간 복잡도를 살펴보겠습니다.
1. 단순 나눗셈 (Trial Division)
알고리즘 소개
단순 나눗셈은 가장 기본적인 소인수 분해 방법으로, 작은 소수들로 주어진 수를 하나씩 나누어 떨어지는지를 확인합니다. 구현이 간단하지만, 큰 수에 대해서는 매우 비효율적입니다.
코드 구현
def trial_division(n):
factors = []
# 2로 나누어 떨어지는 경우 처리
while n % 2 == 0:
factors.append(2)
n //= 2
# 홀수들로 나누기 시작
i = 3
while i * i <= n:
while n % i == 0:
factors.append(i)
n //= i
i += 2
# 남은 소수 추가
if n > 1:
factors.append(n)
return factors
시간 복잡도
- 시간 복잡도: \( O(\sqrt{n}) \)
- 작은 수에 대해서는 효율적이지만, nn이 큰 수일수록 실행 시간이 급격히 증가합니다.
2. 페르마 인수분해법 (Fermat's Factorization Method)
알고리즘 소개
페르마 인수분해법은 주어진 홀수 합성수 NN을 두 제곱수의 차로 표현하여 인수분해하는 방법입니다. 즉, N=x2−y2N = x^2 - y^2 형태로 변환하여 N=(x+y)(x−y)N = (x + y)(x - y)로 인수분해합니다.
코드 구현
import math
def fermat_factorization(n):
x = math.isqrt(n) + 1
while True:
y_squared = x * x - n
y = math.isqrt(y_squared)
if y * y == y_squared:
return [x - y, x + y]
x += 1
시간 복잡도
- 시간 복잡도: \( O(N^{1/4}) \)
- NN이 두 소수의 곱인 경우 빠르게 인수분해할 수 있지만, 인수들이 서로 가까운 수일 때 효과적입니다.
3. 폴라드 로 알고리즘 (Pollard's Rho Algorithm)
알고리즘 소개
폴라드 로 알고리즘은 확률적 방법으로, 작은 인수를 가진 큰 수를 효율적으로 인수분해합니다. 함수의 반복 계산과 최대공약수를 이용하여 인수를 찾습니다.
코드 구현
import random
import math
def pollards_rho(n):
if n % 2 == 0:
return 2
x = random.randrange(2, n)
y = x
c = random.randrange(1, n)
d = 1
while d == 1:
x = (x * x + c) % n
y = (y * y + c) % n
y = (y * y + c) % n
d = math.gcd(abs(x - y), n)
if d == n:
return pollards_rho(n)
return d
시간 복잡도
- 평균 시간 복잡도: \( O(n^{1/4}) \)
- 확률적 알고리즘으로, 일반적으로 빠르게 인수를 찾지만 최악의 경우 시간이 오래 걸릴 수 있습니다.
4. 폴라드 p-1 알고리즘 (Pollard's p-1 Algorithm)
알고리즘 소개
폴라드 p-1 알고리즘은 p−1p - 1이 작은 소인수들로 구성된 소수 pp를 인수로 가진 합성수를 인수분해하는 데 효과적입니다.
코드 구현
import math
def pollards_p_minus_one(n, B=13):
a = 2
for j in range(2, B + 1):
a = pow(a, j, n)
d = math.gcd(a - 1, n)
if 1 < d < n:
return d
else:
return None
시간 복잡도
- 시간 복잡도: \( O(B \times \log n) \)
- BB는 소인수의 크기에 따라 선택되며, 작은 인수를 가진 수에 대해 효율적입니다.
5. 타원곡선 방법 (Elliptic Curve Method, ECM)
알고리즘 소개
ECM은 타원곡선을 이용하여 큰 수의 소인수를 찾는 알고리즘입니다. 작은 인수를 찾는 데 특히 효율적이며, 현재 가장 빠른 알고리즘 중 하나입니다.
시간 복잡도
- 평균 시간 복잡도: \( O(e^{\sqrt{\ln p \ln \ln p}}) \)
- 여기서 pp는 찾고자 하는 소인수입니다.
- 작은 소인수를 찾는 데 매우 효율적입니다.
6. 이차 체 방법 (Quadratic Sieve, QS)
알고리즘 소개
이차 체 방법은 큰 수의 인수분해에 효율적인 알고리즘으로, 병렬 처리가 가능하여 현대 컴퓨터에서 많이 사용됩니다.
시간 복잡도
- 시간 복잡도: \( O(e^{\sqrt{\ln n \ln \ln n}}) \)
- nn이 큰 수에 대해서도 준수한 성능을 보입니다.
7. 수체 체 방법 (Number Field Sieve, NFS)
알고리즘 소개
수체 체 방법은 현재 가장 빠른 일반적인 인수분해 알고리즘으로, 매우 큰 수의 인수분해에 사용됩니다.
시간 복잡도
- 시간 복잡도: \( O(e^{(c(\ln n)^{1/3} (\ln \ln n)^{2/3})}) \)
- 매우 큰 수에 대해서도 효율적입니다.
8. 디슨의 알고리즘 (Dixon's Factorization Method)
알고리즘 소개
디슨의 알고리즘은 합동 관계를 이용하여 합성수를 인수분해하는 확률적 알고리즘입니다. 이차 체 방법의 기반이 되었습니다.
코드 구현
import math
import random
def dixons_factorization(n):
# 기본 구현은 매우 복잡하므로 간단한 버전을 제공합니다.
# 실제로는 선형 대수와 합동 방정식을 사용합니다.
return None # 구현이 복잡하여 생략
시간 복잡도
- 시간 복잡도: \( O(e^{\sqrt{\ln n \ln \ln n}}) \)
- 이차 체 방법보다 비효율적이어서 현재는 잘 사용되지 않습니다.
마무리
소인수 분해는 수학적 흥미뿐만 아니라 실용적인 응용 분야에서도 중요한 문제입니다. 각 알고리즘은 수의 크기와 형태에 따라 효율성이 다르므로, 상황에 맞게 적절한 알고리즘을 선택해야 합니다.