소인수분해의 존재와 유일성은 이론적으로 완전한 설명을 제공하지만, 큰 정수의 소인수를 실제로 찾는 일은 별개의 계산 문제이다. 이 글에서는 두 제곱수의 차에서 출발해 제곱 합동식 기반 인수분해의 원리를 살펴보고, 소인수분해를 이용해 약수의 개수와 합을 계산한다.
Difference of Squares
기본 항등식
은 인수분해 알고리즘의 출발점이다. 홀수 합성수 에서 가 홀수이고 라 하면
는 정수이고
이다. 따라서 모든 홀수 합성수는 두 제곱수의 차로 표현된다. 문제는 적절한 를 얼마나 빨리 찾는가이다.
Fermat–Kraitchik Factorization
홀수 에 대해 에서 시작해 이 완전제곱인지 확인한다.
이면
이므로 인수를 얻는다.
이 방법은 두 인수 가 서로 가까울수록 빠르다. 왜냐하면 가 에 가까워지기 때문이다. 반대로 한 인수가 매우 작고 다른 인수가 크면 많은 를 시험해야 한다.
예제: 인수분해
이므로 부터 시작한다.
따라서
이다.
Congruent Squares와 인수분해
정확히 을 찾지 않아도 다음과 같은 합동식을 찾으면 인수를 얻을 수 있다.
이는
를 뜻한다. 만약 이면 두 인수 중 어느 하나가 전체를 포함하지 않으므로
에서 비자명한 인수를 얻을 가능성이 높다.
“가능성이 높다”라고 표현하는 이유는 얻은 GCD가 1 또는 이 될 수도 있기 때문이다. 좋은 제곱 합동식은 를 만족해야 한다.
작은 예제
에서
이므로 이다. 따라서
을 얻고 이다.
Quadratic Sieve의 아이디어
Quadratic Sieve는 하나의 이 완전제곱이 되기를 기다리는 대신, 여러 값을 작은 소수들의 곱으로 분해한 뒤 조합하여 제곱을 만든다.
대략적인 흐름은 다음과 같다.
- 를 주변에서 여러 개 선택하고 을 계산한다.
- 작은 소수 집합인 factor base를 정한다.
- 가 factor base 소수들만으로 분해되는 경우를 모은다. 이런 수를 smooth number라고 한다.
- 각 소수 지수의 짝·홀만 기록한 벡터를 만든다.
- 여러 벡터의 합이 모두 짝수가 되는 조합을 선형대수로 찾는다.
- 그 조합을 곱하여 을 만들고 GCD를 계산한다.
핵심은 “완전제곱” 조건이 소인수 지수가 모두 짝수라는 조건과 같다는 점이다. 지수의 parity를 modulo 2 벡터로 다루면, 적절한 곱을 찾는 문제가 이진 선형대수 문제가 된다.
이 글에서는 알고리즘의 원리만 다룬다. 실제 구현에서는 factor base 선택, sieving, sparse matrix 계산 등 추가적인 최적화가 필요하다.
Number-Theoretic Functions
정수의 산술적 성질을 값으로 대응시키는 함수를 number-theoretic function 또는 arithmetic function이라고 한다. 여기서는 두 가지 대표 함수를 살펴본다.
- : 의 양의 약수 개수
- : 의 양의 약수 합
예를 들어 의 양의 약수는 이므로
이다. 일부 문헌에서는 약수 개수 함수를 또는 으로도 쓴다.
소인수분해와 모든 약수의 표현
의 소인수분해가
라고 하자. 가 의 양의 약수일 필요충분조건은
이다.
증명
이면 인 양의 정수 가 존재한다. Fundamental Theorem of Arithmetic에 의해 에 나타나는 소수는 에 나타나는 소수뿐이며, 각 지수는 의 대응 지수를 넘을 수 없다.
반대로 위 형태의 에 대해
라 두면 이므로 이다.
Divisor-Counting Function
각 지수 는 중 하나를 독립적으로 선택할 수 있다. 가능한 선택 수는 각각 개이므로 Product Rule에 의해
이다.
예를 들어
이므로
이다.
Sum-of-Divisors Function
모든 약수를 한 번씩 더한 식은 다음 곱을 전개한 것과 같다.
곱을 전개할 때 각 괄호에서 하나를 선택하므로 모든 약수 가 정확히 한 번씩 등장한다. 등비수열 합 공식을 적용하면
이다.
에 대해
이다.
Prime Characterization
에 대해
이다. 양의 약수가 1과 자기 자신뿐이라는 소수의 정의와 같다. 또한
이다.
이 조건은 소수 판별의 정의적 특징이지만, 큰 의 이나 을 소인수분해 없이 계산하는 것은 쉽지 않다. 따라서 실용적인 소수 판별법으로 바로 쓰기보다는 산술 함수의 성질을 이해하는 데 의미가 있다.
정리
Fermat factorization은 홀수 합성수를 두 제곱수의 차로 표현한다. 더 일반적으로 비자명한 제곱 합동식 을 찾으면 GCD를 통해 인수를 얻을 수 있으며, Quadratic Sieve는 여러 smooth relation을 결합해 이런 합동식을 만든다. 소인수분해는 모든 약수를 지수 선택으로 표현하게 하고, 여기서 과 의 곱 공식이 나온다.
연습 문제
- Fermat factorization으로 을 인수분해한다.
- 의 양의 약수 개수와 합을 구한다.
- 이어도 항상 비자명한 인수를 얻지 못하는 예를 설명한다.
풀이
1번
이므로 에서 시작한다.
이므로
이다.
2번
이므로
이다. 약수 합은
이다.
3번
이면 당연히 이지만
이 되어 인수를 얻지 못한다. 이면 이 된다. 따라서 인 비자명한 제곱 합동식이 필요하다.