도구스개발

수론적 변환(NTT) 다항식 곱셈 계산기

FFT를 복소수 대신 소수 모듈로에서 하는 수론적 변환으로 다항식을 곱하고 중간 배열을 단계별로 보여 줍니다. 반올림 오차가 아예 없다는 것과, 998244353 같은 소수를 골라야 하는 이유를 함께 확인할 수 있습니다.

낮은 차수부터. 공백이나 쉼표로 나눕니다

낮은 차수부터

곱셈 결과

18x^4 + 27x^3 + 28x^2 + 13x + 4

변환 길이 8, 단위근 ω = 372528824입니다. 곧이곧대로 계산한 값과 같습니다.

A3x^2 + 2x + 1
B6x^2 + 5x + 4
결과 계수4, 13, 28, 27, 18
곧이곧대로 O(n²) 합성곱4, 13, 28, 27, 18
두 값이 같은가같습니다

고른 소수

p998244353
원시근 g3
p − 1을 2로 나눌 수 있는 횟수23번 → 길이 2^23 = 8,388,608까지
이번 변환 길이 n8
n차 단위근 ω = g^((p−1)/n)372528824

단계별 배열

① A를 변환한 점값6, 485306495, 825076915, 238954792, 2, 991679905, 173167434, 280547518
② B를 변환한 점값15, 344897463, 565325761, 966633581, 5, 612586635, 432918588, 72371043
③ 점별 곱90, 640413164, 213927693, 867635919, 10, 500364718, 784316648, 986319202
④ 역변환 후 n⁻¹ 곱하기4, 13, 28, 27, 18

점값 표현에서는 곱셈이 «점마다 그냥 곱하기»가 됩니다. 다항식을 계수로 곱하면 O(n²) 인데 점값으로 바꾸면 O(n)이고, 오가는 변환이 각각 O(n log n)이라 전체가 O(n log n)이 됩니다.

연산 횟수 어림

곧이곧대로 O(n²)9번
NTT O(n log n)72번쯤

항이 몇십 개 수준이면 곧이곧대로가 오히려 빠릅니다 — 상수가 작기 때문입니다. NTT가 이기는 것은 항이 수백·수천 개를 넘어갈 때입니다.

복소수를 정수로 바꾼 것이 전부입니다. FFT가 쓰는 단위근 e^(2πi/n)의 자리에 «n제곱하면 1이 되는 정수»를 놓습니다. 짜임새(비트 반전 재배치 + 나비 연산)는 그대로 인데 모든 연산이 정수라 반올림이 생길 자리가 없습니다.
아무 소수나 되는 것이 아닙니다. 길이 n의 단위근은 n이 p−1을 나눌 때만 있으므로 p = c·2ᵏ+1 꼴을 고릅니다. 998244353 = 119·2²³+1이 널리 쓰이는 이유가 이것이고, 원시근 3에서 ω = 3^((p−1)/n)으로 필요한 단위근을 그때그때 만들어 씁니다.
계수가 소수를 넘으면 접혀 버립니다. 계수가 최대 M인 다항식 두 개를 길이 n으로 곱하면 결과 항이 최대 n·M²이라 이 값이 p보다 작아야 합니다. 넘어야 한다면 서로 다른 소수 여러 개로 계산하고 중국인의 나머지 정리로 합칩니다.
결과는 0 이상 p 미만으로 나옵니다. 음수 계수를 넣으면 원래 부호가 아니라 p를 더한 값으로 보입니다. 원래대로 보시려면 p의 절반보다 큰 값에서 p를 빼면 됩니다.

사용 방법

  1. 1두 다항식의 계수를 낮은 차수부터 넣습니다. "1 2 3"은 1 + 2x + 3x²입니다.
  2. 2쓸 소수를 고릅니다. 998244353이 가장 널리 쓰입니다.
  3. 3변환 길이 n과 그때의 단위근 ω가 나옵니다.
  4. 4두 다항식의 점값 표현, 점별 곱, 역변환 결과가 단계별로 나옵니다.
  5. 5계수가 소수를 넘어 접힐 수 있으면 경고합니다 — 그때는 결과가 틀립니다.

자주 묻는 질문

반올림 오차가 아예 없기 때문입니다. FFT는 복소수 단위근 e^(2πi/n)을 쓰는데 이것이 부동소수점이라 계수가 크면 오차가 답을 망칩니다. NTT는 같은 짜임새를 소수 모듈로 위에서 하므로 모든 연산이 정수이고 반올림이 생길 자리가 없습니다. 정수 계수를 정확히 곱해야 하는 곳에서는 NTT가 정답입니다.

길이 n짜리 변환을 하려면 n차 원시단위근이 있어야 하고, 그것은 n이 p−1을 나눌 때만 존재하기 때문입니다. 그래서 p = c·2ᵏ+1 꼴로 고릅니다. 998244353 = 119·2²³+1이라 길이 2²³ = 8388608까지 다룰 수 있고, 원시근이 3이라 계산도 간단합니다. 아무 소수나 쓰면 2의 거듭제곱 길이의 단위근이 없어 알고리즘이 돌지 않습니다.

접혀서 틀린 답이 나옵니다. 998244353을 쓸 때 계수가 최대 M인 다항식 두 개를 길이 n으로 곱하면 결과 항이 최대 n·M²이므로 이 값이 소수보다 작아야 합니다. 이 계산기는 그 한계를 넘을 수 있으면 미리 경고합니다. 실제로 넘어야 한다면 서로 다른 소수 여러 개로 계산하고 중국인의 나머지 정리로 합칩니다.

복잡도가 다릅니다. 카라츠바는 O(n^1.585)이고 NTT는 O(n log n)이라, 항이 수천 개를 넘어가면 NTT가 확실히 빠릅니다. 대신 NTT는 소수와 원시근을 골라야 하고 계수 크기에 한계가 있습니다. 항이 몇십 개 수준이면 곧이곧대로 O(n²)가 더 빠를 때도 많습니다 — 상수가 작기 때문입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.

알아두면 좋은 점

  • 계수 1024개까지 다룹니다. 설명을 위한 계산기라 중간 배열을 모두 들고 있기 때문입니다.
  • 음수 계수도 넣을 수 있지만 결과는 0 이상 p 미만으로 나옵니다. 원래 부호로 보려면 p의 절반보다 큰 값에서 p를 빼면 됩니다.
  • BigInt로 계산합니다. 실제 구현은 몽고메리 곱셈이나 배럿 리덕션으로 모듈러 곱셈을 빠르게 합니다.
  • 무작위 다항식 2000쌍에서 O(n²) 곧이곧대로 합성곱과 대조했고, 변환 자체도 정의대로 구한 DFT와 맞췄습니다.

함께 보면 좋은 도구

합성곱두 수열의 선형 합성곱과 순환 합성곱을 구하고 자리마다 어떤 곱이 더해졌는지 보입니다.DFT 계산표본 수열을 이산 푸리에 변환해 주파수 성분의 크기와 위상을 보여 줍니다.카라츠바 곱셈두 수를 반으로 쪼개 네 번이 아니라 세 번의 곱셈으로 처리하는 과정을 재귀 단계별로 보입니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.

마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.