소인수분해의 존재와 유일성은 이론적인 구조를 설명하지만, 큰 정수의 소인수를 실제로 찾는 것은 별개의 계산 문제이다. 현대 인수분해법들은 서로 다른 방식으로 관계(relation)를 모은 뒤, 합동식과 GCD 계산을 통해 비자명한 인수를 꺼낸다.
Difference of Squares
기본 항등식
은 여러 인수분해 알고리즘의 출발점이다. 홀수 합성수 에서 가 모두 홀수이면
는 정수이고 이다. 따라서 모든 홀수 합성수는 두 제곱수의 차로 표현된다.
Fermat–Kraitchik Factorization
에서 시작하여 이 완전제곱인지 검사한다. 만약
이면
이다. 두 인수가 근처에 있을수록 가 작아져 빠르게 찾을 수 있다. 반대로 한 인수가 매우 작고 다른 인수가 매우 크면 많은 를 시험해야 한다.
예를 들어 에 대해 이고
이므로
이다.
Congruent Squares
완전한 등식 대신 다음 합동식만 찾아도 된다.
그러면 이다. 만약 이면 보통
이 되어 비자명한 인수를 얻는다. 이것이 Kraitchik 방식과 Quadratic Sieve의 핵심이다.
Pollard’s Method
의 소인수 에 대해 이 작은 소수들의 거듭제곱으로 이루어진 경우를 이용한다. 경계 를 정하고
로 둔다. 만약 이고 이면 Fermat 정리에 의해
이다. 따라서 이고
을 계산하면 를 얻을 가능성이 있다. 다른 소인수 에 대해서는 이어야 으로 붕괴하지 않는다.
이 알고리즘은 이 -smooth, 즉 모든 소인수가 이하일 때 특히 효과적이다.
Smooth Number와 Factor Base
양의 정수가 정해진 소수 집합만을 인수로 가지면 그 집합에 대해 smooth하다고 한다. 예를 들어 factor base가 이면
은 smooth하지만 11을 인수로 포함하는 수는 아니다.
제곱 합동식 기반 알고리즘은 여러 값을 factor base 위에서 분해하고, 지수의 parity만 기록한다. 지수 벡터의 합이 modulo 2에서 0이면 그 곱은 완전제곱이 된다.
Quadratic Sieve
를 근처에서 선택하고
을 계산한다. 여러 가 factor base 위에서 smooth하게 분해되었다고 하자.
각 relation을 parity vector
로 바꾼다. relation 수가 factor base의 크기보다 충분히 많으면 선형대수에 의해 0이 되는 비자명한 벡터 조합이 존재한다. 선택된 relation을 곱하면
이 되어 congruent squares를 얻는다. 마지막으로 을 계산한다.
Three-Step View
Quadratic Sieve와 더 발전된 Number Field Sieve는 세 단계로 이해할 수 있다.
- Relation building: 작은 소수들로 분해되는 관계를 충분히 모은다.
- Elimination: 지수 parity가 모두 짝수가 되는 조합을 선형대수로 찾는다.
- GCD computation: 얻어진 제곱 합동식에서 비자명한 인수를 추출한다.
Number Field Sieve는 정수 하나의 다항식 표현과 대수적 수체를 사용하여 relation을 더 효율적으로 모으는 방식이다. 구현 세부는 훨씬 복잡하지만 최종적으로 제곱 합동식과 GCD를 만드는 철학은 같다.
알고리즘의 적용 범위
- Fermat factorization: 두 인수가 가까울 때 유리하다.
- Pollard : 어떤 소인수 의 이 smooth할 때 유리하다.
- Quadratic Sieve: 중간 크기의 일반적인 합성수에 적합하다.
- Number Field Sieve: 매우 큰 일반 정수에 사용되는 대표적인 방법이다.
인수분해 난이도는 단순히 자릿수만이 아니라 소인수의 구조와 선택한 알고리즘에 따라 달라진다.
정리
Difference of Squares는 인수분해를 제곱 합동식 탐색으로 바꾼다. Pollard 은 소인수의 곱셈군 크기가 smooth한 경우를 노리고, Quadratic Sieve는 smooth relation을 모아 선형대수로 제곱 합동식을 만든다. 서로 다른 알고리즘이지만 마지막에는 GCD 계산으로 인수를 얻는다는 공통점이 있다.
연습 문제
- Fermat factorization으로 2021을 인수분해한다.
- 이고 일 때 왜 GCD가 인수를 줄 수 있는지 설명한다.
- , , 에 대해 Pollard 의 GCD를 계산한다.
풀이
1번
이고
이므로
이다.
2번
합동식에서 이다. 의 모든 소인수가 한쪽 인자에만 몰리지 않으면 또는 가 1과 사이의 값을 갖는다. 는 각각 GCD가 또는 1이 되는 자명한 경우를 제외한다.
3번
이고
이다. 실제로 이며 이다.