Dividing Polynomials

다항식의 나눗셈이란, \(x\)에 대한 \(n\)차 다항식 \(f(x)\)와 \(x\)에 대한 \(m\)차 다항식 \(g(x)\)에 대하여, 다음을 만족하는 \(x\)에 대한 \(n-m\)차 다항식 \(q(x)\)와 \(m-1\)차 다항식 \(r(x)\)를 구하는 것을 말한다. (\(n \ge m\))

\[f(x)=g(x)q(x)+r(x)\]

이는 높은 차수부터 하나씩 지워 나가는 것으로 \(O(n^2)\) 시간 안에 행할 수 있지만, 여기서는 Discrete Fourier Transform을 이용하여 \(O(n \log n)\)의 시간에 행하는 방법을 소개한다.

~

먼저, \(x\)에 \(z^{-1}\)을 대입하고, 양변에 \(z^n\)을 곱해보자.

\[z^nf(z^{-1})=(z^m g(z^{-1}))(z^{n-m}q(z^{-1}))+z^{n-m+1}(z^{m-1}r(z^{-1}))\]

여기서 \(z^nf(z^{-1})\), \(z^m g(z^{-1})\), \(z^{n-m}q(z^{-1})\) 그리고 \(z^{m-1}r(x)\)는 \(f(x)\), \(g(x)\), \(q(x)\), \(r(x)\)의 계수 순서를 바꾸고 \(x\) 대신에 \(z\)를 적은 것임을 알 수 있다.

이제부터 이들을 \(F(z)\), \(G(z)\), \(Q(z)\), \(R(z)\)라 하자. 그러면 다음처럼 정리할 수 있다.

\[F(z)=G(z)Q(z)+R(z)z^{n-m+1}\]

여기서 \(Q(z)\)는 \(z\)에 대한 \(n-m\)차 다항식임에 유의하자. 만약 \(G(z)H(z)=1\mod z^{n-m+1}\)을 만족하는 다항식 \(H(z)\)가 존재한다면, 우리는 \(Q(z)\)를 다음처럼 나타낼 수 있다.

\[Q(z)=F(z)H(z) \mod z^{n-m+1}\]

\(H(z)\)를 찾을 수만 있다면 Fast Fourier Transform을 이용하여 \(Q(z)\)를 \(O(n\log n)\)의 시간에 구할 수 있다. 이후 계수 순서만 바꾸면 \(q(x)\)를 구할 수 있다.

또한 \(r(x)=f(x)-g(x)q(x)\)인 점을 이용하여 \(r(x)\)도 \(O(n \log n)\)의 시간에 구할 수 있다.

~

그렇다면 \(G(z)H(z)=1\mod z^{n-m+1}\)을 만족하는 다항식 \(H(z)\)는 어떻게 구할까?

\(g(x)\)의 차수가 \(m\)이라고 했으므로, \(G(z)\)의 상수항은 \(0\)이 아님을 알 수 있다.

따라서 \(G(z)\)의 상수항을 \(c\)라 하면, \(G(z)(1/c)=1 \mod x\)임을 알 수 있다.

\(G(z)U(z)=1 \mod x^k\)을 만족하는 다항식 \(U(z)\)를 알고 있다고 할 때, \(G(z)V(z)=1 \mod x^{2k}\)를 만족하는 다항식 \(V(z)\)는 다음의 꼴을 가진다.

\[V(z)=U(z)+T(z)z^k \mod z^{2k}\]

\(G(z)\)를 \(k-1\)차 다항식 \(G_0(z)\)와 \(m-k+1\)차 다항식 \(G_1(z)\)에 대하여 \(G(z)=G_0(z)+G_1(z)z^k\)꼴로 나타냈을 때 \(G_0(z)U(z)=1+W(z)z^k\)라 하면

\[G(z)V(z)=(G_0(z)+G_1(z)z^k) (U(z)+T(z)z^k)=1+(W(z)+G_0(z)T(z)+G_1(z)U(z))z^k \mod z^{2k}\]

\[W(z)+G_0(z)T(z)+G_1(z)U(z)=0 \mod z^k\]

여기서 우리는 \(G_0(z)U(z)=1 \mod z^k\)임을 알고 있으므로

\[U(z)W(z)+T(z)+G_1(z)U^2(z)=0\mod z^k\]

\[T(z)=-U(z)(W(z)+G_1(z)U(z))\mod z^k\]

이상을 정리하면

\[V(z)=U(z)(1-W(z)z^k-G_1(z)U(z)z^k)=U(z)(2-G_0(z)U(z)-G_1(z)U(z)z^k)=U(z)(2-G(z)U(z))\mod z^{2k}\]

\(k\ge n-m+1\)이 될 때까지 이를 반복하면 \(G(z)H(z)=1\mod z^{n-m+1}\)을 만족하는 다항식 \(H(z)\)를 구할 수 있다.

\(G(z)U(z)\)를 구하는 부분에서 Fast Fourier Transform을 사용하면 \(O(n\log n)\)의 시간에 \(H(z)\)를 구할 수 있다.

~

즉, \(f(x)/g(x)\)를 구하는 과정은 다음과 같다.

1. \(f(x), g(x)\)의 계수 순서를 바꿔 \(F(z), G(z)\)를 만든다.

2. \(G(z)\)의 상수항을 \(c\)라고 할 때, \(H(z)\leftarrow1/c, k\leftarrow1\)로 놓는다.

3. 다음 과정을 \(k\ge n-m+1\)이 될 때까지 반복한다.

3-1. \(k\leftarrow2k\)

3-2. \(H(z)\leftarrow H(z)(2-G(z)H(z)) \mod z^k\)

4. \(Q(z)\leftarrow F(z)H(z) \mod z^{n-m+1}\)

5. \(Q(z)\)의 계수 순서를 바꿔 \(q(x)\)를 구한다.

6. \(r(x)\leftarrow f(x)-g(x)q(x)\)

여기서 모든 다항식 곱셈에는 Fast Fourier Transform을 사용하고, \(\mod z^k\)인 경우 \(k\)차 이상의 항을 무시하고 계산하면 \(O(n\log n)\)의 시간에 나눗셈을 행할 수 있다.