다항식 기초: FFT와 NTT
이 문서는 다항식 연산의 기본 개념을 다룹니다. 특히 빠른 푸리에 변환(FFT)과 빠른 수론 변환(NTT)을 중심으로 설명합니다.
FFT: 다항식 곱셈의 효율적 구현
FFT는 다항식을 단위근에서의 점값 표현으로 변환하는 과정을 가속화하는 알고리즘입니다. 주어진 다항식 F(x) = Σ aᵢxⁱ를 ωₙ⁰, ωₙ¹, ..., ωₙ^(n-1)에서 평가하는 과정을 분할 정복 방식으로 수행합니다.
핵심 ...
7월 31일 20:45에 게시됨