다항식 역원 DSL

초기에는 $g=f_0^{-1}$로 두면 $fg\equiv 1\pmod{x}$이다. 길이 $m$의 역원 $g$를 알고 있을 때 Newton 갱신

$$g' = 2g-fg^2\pmod{x^{2m}}$$

을 사용하면 정밀도를 두 배로 늘릴 수 있다. 일반적인 두 번의 full convolution 구현은 정확하지만 $N=2^{20}$에서 정규화 비용이 약 $24$이므로 만점을 받지 못한다.

만점 구성은 $q=fg^2$의 필요한 높은 절반을 두 종류의 cyclic convolution으로 복원한다. $g$의 길이는 $m$이고 $f$는 길이 $2m$로 잘라서 사용한다.

먼저 길이 $2m$의 cyclic convolution으로

$$u=q\bmod (x^{2m}-1)$$

을 계산한다. 이는 길이 $2m$의 DFT 두 번과 IDFT 한 번으로 얻는다.

다음으로 $r$을 원시 $4m$제곱근으로 잡고 $j=r^m$이라 하자. 계수에 $r^i$를 곱하고 $f$를 FOLD로 $x^m-1$에 대해 접은 뒤 길이 $m$의 cyclic convolution을 계산한다. 역변환 뒤 $r^{-i}$를 곱하면

$$v_k=q_k+jq_{k+m}-q_{k+2m}-jq_{k+3m}$$

을 얻는다.

$0\le k<m$에 대해

$$A=q_k,\quad B=q_{k+m},\quad C=q_{k+2m},\quad D=q_{k+3m}$$

라 두면

$$u_{\mathrm{low}}=A+C,\qquad u_{\mathrm{high}}=B+D,$$ $$v=A+jB-C-jD.$$

또한 $fg\equiv 1\pmod{x^m}$이므로 $q=fg^2\equiv g\pmod{x^m}$이고 $A=g_k$이다. 따라서

$$-B=\frac{j(u_{\mathrm{low}}+v-2g)-u_{\mathrm{high}}}{2}.$$

Newton 갱신에서 새 높은 절반은 정확히 $-B$이므로 위 식을 그대로 계산하여 $g$의 뒤에 붙이면 된다.

각 단계는 길이 $2m$ 변환 세 번과 길이 $m$ 변환 세 번을 사용한다. $N=2^K$일 때 총 비용은

$$3\sum_{k=0}^{K-1}\left(D(2^{k+1})+D(2^k)\right) =(9K-12)N+12.$$

따라서 $N=2^{20}$에서

$$C=8.400000572\ldots<9$$

이므로 만점을 받는다. $N$이 $2$의 거듭제곱이 아니면 각 단계에서 $0$으로 패딩하고 마지막에 길이 $N$으로 자르면 된다.

DFT의 주파수 순서를 알 필요는 없다. 같은 길이의 두 DFT 결과를 원소별로 곱하는 연산만 사용하므로 명세가 보장하는 opaque-order 성질만으로 충분하다.

Solution written by GPT5.6