O(N^{1/4+e}) 시간 복잡도에 소인수 분해하기

소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 "어려운" 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다.

소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다 빠른 알고리즘을 찾는 것은 쉽지 않다. 일반적으로 가장 자주 사용되는 알고리즘은 Pollard-rho라는 알고리즘이다. 이 알고리즘은 대회에 사용될 수 있을 정도로 복잡하지 않고, 평균 $O(N^{1/4})$ 시간 복잡도라는, 굉장히 효율적인 편인 시간 복잡도에 작동하지만, 정말 모든 숫자에 대해서 $O(N^{1/4})$ 에 작동하는가가 증명되거나 반증되지 않은 휴리스틱 알고리즘이다.

한편, 정말 $O(N^{1/4 + \epsilon})$ 시간 복잡도에 결정론적으로 작동하는 소인수 분해 알고리즘이 존재한다. 이 때 $\epsilon$ 은 0 이상의 임의의 양수로, 복잡도가 $O(N^{1/4})$ 는 아니지만 $1/4$ 초과의 임의의 지수부에 대해서 맞다는 뜻이다. 나의 경우, $\epsilon > 0, k > 0$ 일 때 $\lim_{n \rightarrow \infty}{\frac{N^{\epsilon}}{\log^{k}N}} = 0$ 이 항상 만족된다는 맥락에서 이러한 기호를 사용한다. (정확히는 $O(N^{1/4}\log^3 N)$ 이다.) 알고리즘은 전혀 대회에 사용될 수 있을 정도로 간단하지 않으나, 알고리즘을 이해하는 것은 어렵지 않고, 여러 교육적인 내용을 포함하고 있어서 설명해 본다.

이 글은 독자가 FFT를 통해 다항식 곱셈이 가능하다는 사실을 알고 있음을 가정한다.

Preliminaries

먼저 소인수 분해를 다음과 같은 문제로 변환한다. Pollard-rho 같은 다른 알고리즘에서도 사용하는 변환들이라서, 특별히 이 알고리즘에만 해당되는 내용이 아니다.

Input. 소수가 아닌 2 이상의 자연수 $N$

Output. $2 \le x \le N - 1$ 이며 $N\mod x = 0$ 인 $x$ 를 반환

이러한 문제를 해결한다면, 일반적으로 알고 있는 소인수 분해를 해결할 수 있다. $N$ 이 주어졌을 때, 이것이 소수임을 판별하고 (AKS / Miller-Rabin 등의 다항 시간 알고리즘 사용), 소수라면 자신을 반환한 후, 소수가 아니라면, 위 문제를 해결한 후, $N / x, x$ 에 대한 소인수 분해를 따로 합쳐주면 (Divide and conquer) 되기 때문이다. 또한, 위 문제를 $O(N^{1/4}\log^k N)$ 에 해결했다면, 전체 문제 역시 $O(N^{1/4}\log^k N)$ 에 해결됨을 보일 수 있다. ($N/2, 2$ 로 나눠지는 것이 성능상 최악의 경우이고, 이 때식을 쓰면 등비급수의 합의 형태로 항들이 사라진다)

이제 이 문제를 또 한번 다음과 같이 변형한다:

Input. 소수가 아닌 2 이상의 자연수 $N$

Output. $2 \le x \le \sqrt N $ 이며 $N\mod x = 0$ 인 $x$ 를 반환

$N$ 이 $x$ 로 나눠진다면, $N$ 은 $N/x$ 로도 나눠지고, 둘 중 하나는 $\sqrt N$ 이하이기 때문이다.

그리고 이 문제를 또 한번 다음과 같이 변형한다:

Input. 소수가 아닌 2 이상의 자연수 $N$

Output. $2 \le x \le \sqrt N $ 이며 $gcd(N, x) \neq 1$ 인 $x$ 를 반환

약수일 경우 $gcd(N, x)\neq 1$ 을 자명히 만족하고, 만약 $gcd(N, x) \neq 1$ 이라면 해당 gcd 값은 무조건 $x$ 의 약수이기 때문에 상관이 없다.

닭 잡는데 소 잡는 칼 쓰기

우리는 특정한 정수 구간에서 $gcd(N, x) \neq 1$, 즉 $N$과 서로소인 $x$ 의 존재 여부를 찾고 싶다. 이 구간을 $[s, e]$ 라고 하였을 때, 다음과 같은 Lemma가 성립한다.

Lemma. $gcd(\frac{e!}{(s-1)!} \mod N, N) \neq 1$ 이면, 구간 $[s, e]$ 에 $N$ 과 서로소가 아닌 수가 존재한다.

증명은 Euclid algorithm을 생각해 보면 자명하니 생략한다. 고로, $s \times (s+1) \times (s+2) \times \ldots \times e \mod N$ 을 빠르게 구할 수 있다면 문제를 해결할 수 있다. 갑자기 도대체 무슨 소리인가 싶지만, 어쨌든 된다. 그건 사실이다.

이제 위 함수를 어떻게인지 모르겠지만 아무튼 빠르게 계산할 수 있다고 가정하자. 이미 한번 $\sqrt N$ 으로 쪼갰지만, 이를 또 한번 루트로 쪼개서 $N^{1/4}$ 단위의 sqrt decomposition을 해 보자. 위 함수를 $O(1)$ 에 계산한다 치면, 다음과 같은 알고리즘을 사용해서 소인수 분해를 $O(N^{1/4})$ 에 해결할 수 있다:

• $(0, N^{1/4}]$ 구간에 서로소가 아닌 수가 있는지 확인하고 ($O(1)$), 있으면 Brute force로 찾아서 반환
• $(N^{1/4}, 2 \times N^{1/4}]$ 구간에 서로소가 아닌 수가 있는지 확인하고 ($O(1)$), 있으면 Brute force로 찾아서 반환
• $(2\times N^{1/4}, 3\times N^{1/4}]$ 구간에 서로소가 아닌 수가 있는지 확인하고 ($O(1)$), 있으면 Brute force로 찾아서 반환
• ...

이 함수를 그래서 빠르게 계산할 수 있을까? 그렇다! 이제 다음 단락에서 이 함수를 $O(N^{1/4} \log^2 N)$ 에 계산할 수 있는 알고리즘을 소개한다.

Polynomial Evaluation with Fast Fourier Transform

편의상 $N^{1/4}$ 가 정수라고 가정하자 (정수가 아니어도 그렇게 쉽게 바꿔줄 수 있다). 모든 $x = 0 \mod N^{1/4}$ 에 대해서 $\frac{(x + N^{1/4})!}{x!} \mod N$ 을 계산할 수 있을 경우, 위에서 말한 "서로소 확인" 을 할 수 있으니 문제가 해결된다. 위 식은 다음과 같이 풀어 쓸 수 있다:

$(x + 1) \times (x + 2) \times \ldots \times (x + N^{1/4}) \mod N$

그런데 사실 이것은 $x$ 에 대한 $N^{1/4}$ 다항식이다. 이를 $f(x)$ 라 두자. 우리가 원하는 것은 다음과 같은 값들이다:

$f(0), f(N^{1/4}), f(2 \times N^{1/4}), \ldots, f(N^{1/2})$

이렇게 되면 문제는 갑자기 정수론 문제에서 다항식 계산 문제로 바뀐다. $B = N^{1/4}$ 라 두자.다음과 같은 두 문제를 해결할 수 있으면 전체 문제를 바로 해결할 수 있다.

• 1. $(x + 1) \times (x + 2) \times \ldots \times (x +B) \mod N$ 을 어떻게 빠르게 전개하는가?
• 2. $B$ 차 다항식 $f(x)$, 그리고 $B$ 개의 쿼리 $q_0 = 0, q_1 = B, q_2 = 2B, \ldots$ 가 주어졌을 때, $f(q_0), f(q_1), f(q_2) \ldots$ 를 어떻게 빠르게 계산하는가?

첫 번째 문제는 분할 정복에 FFT를 더해 해결할 수 있다. $solve(S, E)$ 함수를, $(x + S) \times (x + S + 1) \times \ldots \times (x + E) \mod N$ 라는 다항식을 반환하는 함수라고 정의하자. $solve(1, B)$ 를 호출하면 문제를 해결할 수 있다. 이제 재귀적으로 분할 정복을 사용하여 다항식을 구해야 하는데, 이는 단순하게 $solve(S, (S+E)/2), solve((S+E)/2+1, E)$ 를 호출한 후 두 다항식을 빠른 푸리에 변환 (FFT) 를 사용하여 곱셈해 주면 된다. FFT는 $O(N\log N)$ 에 작동하고, $T(N) = 2T(N/2) + O(N\log N)$ 이기 때문에, $T(B) = O(B\log^2 B)$ 에 다항식 계산이 가능하다.

두 번째 문제를 해결하기 위해서 한 가지 사실을 짚고 넘어가자: 어떠한 두 다항식 $f(x), g(x)$ 가 존재한다고 하자. $g(x)$ 의 최고차항이 1일 경우 우리는 $f(x)$ 를 $g(x)$ 로 나눈다 라는 것을 정의할 수 있다. $f(x)$ 가 $n$ 차 다항식, $g(x)$ 가 $m$ 차 다항식이라면, $f(x) - g(x)h(x)$ 가 $n-m-1$ 차 이하의 다항식인 어떠한 다항식 $h(x)$ 가 존재하며 이를 쉽게 $O(nm)$ 시간 복잡도에 구할 수 있다. 여기서 재미있는 것은, FFT와 분할 정복을 통해서 $f(x) / g(x)$ 를 이보다 빠른 $O(n \log n)$ 시간에 구할 수 있다는 것이다. 이러한 알고리즘에 대해서는 여기서 배울 수 있다. 이 부분에 대해서는 따로 설명하지 않고, 꽤 어려운 내용이니, 그냥 이러한 알고리즘이 존재한다는 것만 알고 있어도 괜찮다.

이제 닭 잡는 데 소 잡는 칼을 또 한번 쓰자. 다항식 $f(x)$ 가 주어질 때, $f(q_0)$ 은, $f(x)$ 를 $(x - q_0)$ 으로 나눈 나머지 로 계산할 수 있다. 고로 두 번째 문제를 해결하는 것은, 다항식 $f(x)$ 에 대해서 이를 $(x - q_0), (x - q_1), (x - q_2) \ldots$ 로 나눈 나머지를 각각 계산하는 것으로 해석할 수 있다.

이 문제를 또 다시 분할 정복으로 해결할 것이나, 아까보다 조금 더 복잡한 방법을 사용한다. 이제는 Segment Tree 라는 자료 구조를 사용하자. Segment tree는 각각의 쿼리 $q_0, q_1, \cdots, q_{B-1}$ 을 인덱스로 가지며, $[S, E]$ 구간을 대표하는 노드에는 다항식을 저장한다. 저장된 다항식 값은 $(x - q_S) \times (x - q_{S+1}) \times \ldots \times (x - q_E)$ 임을 알 수 있다. 이러한 Segment Tree를 계산하는 것은 첫 번째 문제를 푸는 방식과 똑같은 방식으로 할 수 있다. 단말 노드를 만들어 주면, 그 위 단말이 아닌 노드들은 양쪽 자식에 들어있는 다항식을 곱한 값을 부모 노드로 설정해 준다. 이러한 Segment Tree는 아까와 똑같이 $T(B) = O(B\log^2 B)$ 시간에 구성할 수 있다.

이러한 Segment Tree를 사용하면 위 값을 빠르게 계산해 줄 수 있을까? 위 값을 계산하기 어려웠던 이유는, 분모로 들어오는 다항식이 매우 작음에도 불구하고 분자로 들어오는 다항식이 매우 크기 때문이다. 어떠한 구간 $[S, E]$ 에서 쿼리를 계산할 때, 맨 처음 $(x - q_S) \times (x - q_{S+1}) \times \ldots \times (x - q_E)$ 로 나눈 나머지를 계산해 주고 다항식의 크기를 $E - S$ 차 이하로 줄였다고 생각하자. 이러한 경우 만약 구간의 크기가 충분히 작다면, 아까와 같이 매우 큰 다항식을 전부 확인할 필요가 사라진다.

이제 진짜 문제를 해결하자. Segment Tree를 순회하면서, 단말 노드를 도달할 때마다 나머지 값을 알 수 있도록 구성할 것이다. 이를 위해, $solve(S, E, poly)$ = 해당 구간에 있는 모든 쿼리에 대한 결과를 계산하는 함수라고 정의하자. 이 함수는

• $poly$ 를$(x - q_S) \times (x - q_{S+1}) \times \ldots \times (x - q_E)$ 로 나눈 후 나머지만 남기고 (이 다항식은 Segment Tree 계산 과정에서 전처리 되어 있으니 계산할 필요 없다.)
• $E - S \geq 1$일 경우 $solve(S, M, poly), solve(M + 1, E, poly)$ 를 호출
• 아니면 $poly$ 는 상수항이니 해당 값을 출력.

이 함수의 시간 복잡도를 계산하자. 맨 처음 solve가 호출될 때를 제외한 모든 경우, $poly$ 의 차수는 해당 구간의 크기의 2배 이하임이 보장된다. 맨 처음 호출에서도, 다항식의 크기가 $B$ 이하이기 때문에 구간 크기의 2배 이하임이 여전히 성립한다. 고로 나머지를 연산하는 과정은 $T(N) = O(N \log N) + 2T(N/2) = O(N\log^2 N)$ 이다. 전체 문제가 $O(N^{1/4} \log^2 N)$ 에 해결된다.

여담으로, 이러한 방법을 그대로 사용하여 $N! \mod M$ 을 $\sqrt N \log^2 N$ 에도 해결할 수 있다. :)

Polynomial Interpolation with Fast Fourier Transform

이 글에서는 설명하지 않지만, 다른 방법을 사용하면 이 문제를 $\sqrt N \log N$ 에도 해결할 수 있다. 위 방법과는 접근 방법이 다르며, 다항식을 재귀적으로 만들어나가고 크기를 늘리는 방식의 풀이이다. 이 풀이 역시 실제 대회에 쓸만큼 빠르지는 않지만 그래도 Naive한 알고리즘과는 확실히 의미있는 차이를 보인다.

이 풀이에 대해서는 따로 설명하지는 않고 Min_25의 글을 링크로 건다. 이 방법을 사용하여 N! mod P (2), N! mod P (3) 문제를 해결할 수 있다.