[나만 보는 정리노트] NTT

https://velog.io/@sqrt_3/%EB%82%98%EB%A7%8C-%EB%B3%B4%EB%8A%94-%EC%A0%95%EB%A6%AC%EB%85%B8%ED%8A%B8-FFT-%EA%B8%B0%EC%B4%88

FFT에서 1의 거듭제곱근 $w$를 사용하는데, $n$번 제곱할 때마다 한 번씩 $1$로 돌아오는 주기성을 가지고 있기 때문이다. 이와 비슷한 성질을 가지는 개념이 원시근이다.

따라서 소수 $p=a\times 2^b+1$의 원시근 $w$에 대해 $w^{\frac{p-1}{n}}≡1(\mod p)$임을 이용하여 FFT를 돌릴 수 있다. (단, $n≤2^b$여야 한다.)

대표적인 $p$로 $998,244,353$이 있다. 원시근은 $3$이다.