NTT एल्गोरिदम हाथ से

Last updated on Nov 12, 2025

NTT (Number Theoretic Transform) एल्गोरिथम एक finite field में एक polynomial को coefficient form से point form में बदलता है।

यदि किसी polynomial की degree $d$ है, तो हम इसे unity के $k$ -th roots पर evaluate करते हैं जहाँ $k\gt d$ होता है।

$f(x)$ polynomial को unity के $k$ -th roots के सेट, $\set{1,\omega,\omega^2,...,\omega^{k-1}}$ के प्रत्येक बिंदु पर evaluate करने के बजाय, हम image preservation theorem for multivalued functions का उपयोग करते हैं। इसका उपयोग डोमेन $\set{1}$ पर $f$ में $x$ को $\sqrt[k]{x}$ से बदलकर बनाए गए multivalued function को evaluate करने के लिए किया जाता है। इसके बाद हम square root के evaluations को $\set{1}$ से $\set{1,\omega^{k/2}}$ तक, फिर $\set{1,\omega^{k/4},\omega^{k/2},-\omega^{k/4}}$ तक और इसी तरह iteratively expand करते हैं, जब तक कि evaluation unity के $k$ -th roots तक expand नहीं हो जाता।

इस विधि का रनटाइम $\mathcal{O}(n \log n)$ है।

unity के 4-th roots पर $f(x)=a_0+a_1x+a_2x^2+a_3x^3$ को evaluate करना

सबसे पहले, हम $x^2$ की occurrences को अधिकतम (maximize) करने के लिए फ़ंक्शन को factor करते हैं, क्योंकि $2=k/2$ और $x^{k/2}$ को root of unity पर evaluate करना आसान है (यह केवल $\set{1,-1}$ में परिणाम देता है, जो इस बात पर निर्भर करता है कि root of unity की घात (power) सम (even) है या विषम (odd))।

यह निम्नलिखित फ़ंक्शन बनाता है:

f(x)=a_0+a_2x^2+x(a_1+a_3x^2)

इसके बाद, हम $f$ को transform करते हैं ताकि $x\rightarrow\sqrt[4]{x}$ हो जाए, जिससे हमें मिलता है:

f(x)=a_0+a_2\sqrt{x}+\sqrt[4]{x}(a_1+a_3\sqrt{x})

यहाँ square root expansion आरेख (diagram) दिया गया है:

अब हम परिणाम की तुलना unity के 4-th roots पर $f(x)$ को एक-एक करके evaluate करने से करते हैं:

\begin{align*} f(1) &= a_0 &+& a_1(1) &+& a_2(1)^2 &+& a_3(1)^3\\ f(-1) &= a_0 &+& a_1(-1) &+& a_2(-1)^2 &+& a_3(-1)^3\\ f(\omega) &= a_0 &+& a_1(\omega) &+& a_2(\omega)^2 &+& a_3(\omega)^3\\ f(-\omega) &= a_0 &+& a_1(-\omega) &+& a_2(-\omega)^2 &+& a_3(-\omega)^3 \end{align*}

हमारे पास $\omega^2=(-\omega^2)=-1$ और $\omega^3=-\omega$ और $(-\omega)^3=(-1)^3(\omega)^3=-\omega^3=-(-\omega)=\omega$ हैं। substitution द्वारा, हमें प्राप्त होता है:

\begin{align*} f(1) &= a_0 &+& a_1 &+& a_2 &+& a_3\\ f(-1) &= a_0 &-& a_1 &+& a_2 &-& a_3\\ f(\omega) &= a_0 &+& a_1\omega &-& a_2 &-& a_3\omega\\ f(-\omega) &= a_0 &-& a_1\omega &-& a_2 &+& a_3\omega \end{align*}

Exercise: unity के 4-th roots पर $a_0+a_1x+a_2x^2$ को evaluate करने के लिए उपरोक्त विधि का उपयोग करें। Hint: ऊपर दिए गए उदाहरण का उपयोग करें और $a_3=0$ सेट करें।

Tree की ऊँचाई $\log n$ है और हम प्रत्येक पंक्ति पर $\mathcal{O}(n)$ ऑपरेशन्स करते हैं, इसलिए रनटाइम $\mathcal{O}(n \log n)$ है।

unity के 8-th roots पर $f(x)=a_0+a_1x+...+a_7x^7$ को evaluate करना

सबसे पहले, हम $x^4$ terms की संख्या को अधिकतम करने के लिए polynomial को पुनर्व्यवस्थित (rearrange) करते हैं (चूंकि k = 8)। इससे हमें मिलता है:

f(x)=a_0+a_4x^4+x^2(a_2+a_6x^4)+x((a_1+a_5x^4)+x^2(a_3+a_7x^4))

अब हम अपना multivalued function $g(x)$ प्राप्त करने के लिए $x\rightarrow\sqrt[8]{x}$ substitute करते हैं:

g(x)=a_0+a_4\sqrt{x}+\sqrt[4]{x}(a_2+a_6\sqrt{x})+\sqrt[8]{x}((a_1+a_5\sqrt{x})+\sqrt[4]{x}(a_3+a_7\sqrt{x}))

चूँकि evaluation tree को एक ही चित्र में बनाना काफी बड़ा होगा, इसलिए हम tree का बायां हिस्सा (left side) बनाएंगे जहाँ हम $\sqrt{1}=1$ को evaluate करते हैं और पहले उसका आरेख (diagram) दिखाएंगे:

ऊपर दिए गए चित्र से, हम देख सकते हैं कि:

\begin{align*} f(1)=((a_0+a_4)+(a_2+a_6))+((a_1+a_5)+(a_3+a_7))\\ f(-1)=((a_0+a_4)+(a_2+a_6))+((a_1+a_5)+(a_3+a_7))\\ f(\omega^2)=((a_0+a_4)-(a_2+a_6))+\omega((a_1+a_5)-(a_3+a_7))\\ f(-\omega^2)=((a_0+a_4)-(a_2+a_6))-\omega((a_1+a_5)-(a_3+a_7))\\ \end{align*}

अब हम tree के दाएं हिस्से (right side) को expand करते हैं जहाँ $\sqrt{x}=-1$ है:

उस परिणाम से, हमें प्राप्त होता है:

\begin{align*} f(\omega)=((a_0-a_4)+\omega^2(a_2-a_6))+\omega((a_1-a_5)+\omega^2(a_3-a_7))\\ f(-\omega)=((a_0-a_4)+\omega^2(a_2-a_6))-\omega((a_1-a_5)+\omega^2(a_3-a_7))\\ f(\omega^3)=((a_0-a_4)-\omega^2(a_2-a_6))+\omega^3((a_1-a_5)-\omega^2(a_3-a_7))\\ f(-\omega^3)=((a_0-a_4)-\omega^2(a_2-a_6))-\omega^3((a_1-a_5)-\omega^2(a_3-a_7)) \end{align*}

Evaluations को मिलाने और omega terms को वितरित (distribute) करने पर, हमें मिलता है:

\begin{align*} f(1) &= a_0 &+ a_4 &+ a_2 &+ a_6 &+ a_1 &+ a_5 &+ a_3 &+ a_7\\f(-1) &= a_0 &+ a_4 &+ a_2 &+ a_6 &- a_1 &- a_5 &- a_3 &- a_7\\f(\omega^2) &= a_0 &+ a_4 &- a_2 &- a_6 &+ a_1\omega^2 &+ a_5\omega^2 &- a_3\omega^2 &- a_7\omega^2\\f(-\omega^2)&= a_0 &+ a_4 &- a_2 &- a_6 &- a_1\omega^2 &- a_5\omega^2 &+ a_3\omega^2 &+ a_7\omega^2\\f(\omega) &= a_0 &- a_4 &+ a_2\omega^2 &- a_6\omega^2 &+ a_1\omega &- a_5\omega &+ a_3\omega^3 &- a_7\omega^3\\f(-\omega) &= a_0 &- a_4 &+ a_2\omega^2 &- a_6\omega^2 &- a_1\omega &+ a_5\omega &- a_3\omega^3 &+ a_7\omega^3\\f(\omega^3) &= a_0 &- a_4 &- a_2\omega^2 &+ a_6\omega^2 &+ a_1\omega^3 &- a_5\omega^3 &+ a_3\omega &- a_7\omega\\f(-\omega^3)&= a_0 &- a_4 &- a_2\omega^2 &+ a_6\omega^2 &- a_1\omega^3 &+ a_5\omega^3 &- a_3\omega & a_7\omega\end{align*}

इसके बाद, हम coefficients को आरोही क्रम (ascending order) में रखते हैं:

\begin{align*} f(1) &= a_0 &+ a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &+ a_6 &+ a_7\\ f(-1) &= a_0 &- a_1 &+ a_2 &- a_3 &+ a_4 &- a_5 &+ a_6 &- a_7\\ f(\omega^2) &= a_0 &+ a_1\omega^2 &- a_2 &- a_3\omega^2 &+ a_4 &+ a_5\omega^2 &- a_6 &- a_7\omega^2\\ f(-\omega^2)&= a_0 &- a_1\omega^2 &- a_2 &+ a_3\omega^2 &+ a_4 &- a_5\omega^2 &- a_6 &+ a_7\omega^2\\ f(\omega) &= a_0 &+ a_1\omega &+ a_2\omega^2 &+ a_3\omega^3 &- a_4 &- a_5\omega &- a_6\omega^2 &- a_7\omega^3\\ f(-\omega) &= a_0 &- a_1\omega &+ a_2\omega^2 &- a_3\omega^3 &- a_4 &+ a_5\omega &- a_6\omega^2 &+ a_7\omega^3\\ f(\omega^3) &= a_0 &+ a_1\omega^3 &- a_2\omega^2 &+ a_3\omega &- a_4 &- a_5\omega^3 &+ a_6\omega^2 &- a_7\omega\\ f(-\omega^3)&= a_0 &- a_1\omega^3 &- a_2\omega^2 &- a_3\omega &- a_4 &+ a_5\omega^3 &+ a_6\omega^2 &+ a_7\omega \end{align*}

अब evaluations को $f(1)$ , $f(\omega)$ , … , $f(\omega^7)$ के क्रम में जाने के लिए पुनर्व्यवस्थित (rearrange) करते हैं:

\begin{align*} f(1) &= a_0 &+ a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &+ a_6 &+ a_7\\ f(\omega) &= a_0 &+ a_1\omega &+ a_2\omega^2 &+ a_3\omega^3 &- a_4 &- a_5\omega &- a_6\omega^2 &- a_7\omega^3\\ f(\omega^2) &= a_0 &+ a_1\omega^2 &- a_2 &- a_3\omega^2 &+ a_4 &+ a_5\omega^2 &- a_6 &- a_7\omega^2\\ f(\omega^3) &= a_0 &+ a_1\omega^3 &- a_2\omega^2 &+ a_3\omega &- a_4 &- a_5\omega^3 &+ a_6\omega^2 &- a_7\omega\\ f(-1) &= a_0 &- a_1 &+ a_2 &- a_3 &+ a_4 &- a_5 &+ a_6 &- a_7\\ f(-\omega) &= a_0 &- a_1\omega &+ a_2\omega^2 &- a_3\omega^3 &- a_4 &+ a_5\omega &- a_6\omega^2 &+ a_7\omega^3\\ f(-\omega^2)&= a_0 &- a_1\omega^2 &- a_2 &+ a_3\omega^2 &+ a_4 &- a_5\omega^2 &- a_6 &+ a_7\omega^2\\ f(-\omega^3)&= a_0 &- a_1\omega^3 &- a_2\omega^2 &- a_3\omega &- a_4 &+ a_5\omega^3 &+ a_6\omega^2 &+ a_7\omega \end{align*}

यदि हम इसकी तुलना unity के 8-th roots के लिए Vandermonde matrix से करते हैं, तो हम देख सकते हैं कि हमने $\omega$ की powers की सही गणना की है।

\mathbf{V} =\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & -1 & -\omega & -\omega^{2} & -\omega^{3} \\ 1 & \omega^{2} & -1 & -\omega^{2} & 1 & \omega^{2} & -1 & -\omega^{2} \\ 1 & \omega^{3} & -\omega^{2} & \omega & -1 & -\omega^{3} & \omega^{2} & -\omega \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -\omega & \omega^{2} & -\omega^{3} & -1 & \omega & -\omega^{2} & \omega^{3} \\ 1 & -\omega^{2} & -1 & \omega^{2} & 1 & -\omega^{2} & -1 & \omega^{2} \\ 1 & -\omega^{3} & -\omega^{2} & -\omega & -1 & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

Vandermonde matrix की गणना

ऊपर दी गई Vandermonde matrix को निम्न प्रकार से प्राप्त किया गया था। प्रत्येक पंक्ति $x=\set{1,\omega,\omega^2,...,\omega^7}$ पर $f(x)=a_0+a_1x+...+a_7x^7$ के लिए $x$ की powers है:

\mathbf{V}= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{8} & \omega^{10} & \omega^{12} & \omega^{14}\\ 1 & \omega^{3} & \omega^{6} & \omega^{9} & \omega^{12} & \omega^{15} & \omega^{18} & \omega^{21}\\ 1 & \omega^{4} & \omega^{8} & \omega^{12} & \omega^{16} & \omega^{20} & \omega^{24} & \omega^{28}\\ 1 & \omega^{5} & \omega^{10} & \omega^{15} & \omega^{20} & \omega^{25} & \omega^{30} & \omega^{35}\\ 1 & \omega^{6} & \omega^{12} & \omega^{18} & \omega^{24} & \omega^{30} & \omega^{36} & \omega^{42}\\ 1 & \omega^{7} & \omega^{14} & \omega^{21} & \omega^{28} & \omega^{35} & \omega^{42} & \omega^{49} \end{bmatrix}

इसके बाद, हम 8 के गुणकों (multiples) को factor out करते हैं:

\mathbf{V}= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{8} & \omega^{8}\omega^{2} & \omega^{8}\omega^{4} & \omega^{8}\omega^{6}\\ 1 & \omega^{3} & \omega^{6} & \omega^{8}\omega & \omega^{8}\omega^{4} & \omega^{8}\omega^{7} & \omega^{16}\omega^{2} & \omega^{16}\omega^{5}\\ 1 & \omega^{4} & \omega^{8} & \omega^{8}\omega^{4} & \omega^{16} & \omega^{16}\omega^{4} & \omega^{24} & \omega^{24}\omega^{4}\\ 1 & \omega^{5} & \omega^{8}\omega^{2} & \omega^{8}\omega^{7} & \omega^{16}\omega^{4} & \omega^{24}\omega & \omega^{24}\omega^{6} & \omega^{32}\omega^{3}\\ 1 & \omega^{6} & \omega^{8}\omega^{4} & \omega^{16}\omega^{2} & \omega^{24} & \omega^{24}\omega^{6} & \omega^{32}\omega^{4} & \omega^{40}\omega^{2}\\ 1 & \omega^{7} & \omega^{8}\omega^{6} & \omega^{16}\omega^{5} & \omega^{24}\omega^{4} & \omega^{32}\omega^{3} & \omega^{40}\omega^{2} & \omega^{48}\omega\\ \end{bmatrix}

8 के factors को हटाने पर हमें मिलता है:

\mathbf{V} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & 1 & \omega^{2} & \omega^{4} & \omega^{6}\\ 1 & \omega^{3} & \omega^{6} & \omega & \omega^{4} & \omega^{7} & \omega^{2} & \omega^{5}\\ 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4}\\ 1 & \omega^{5} & \omega^{2} & \omega^{7} & \omega^{4} & \omega & \omega^{6} & \omega^{3}\\ 1 & \omega^{6} & \omega^{4} & \omega^{2} & 1 & \omega^{6} & \omega^{4} & \omega^{2}\\ 1 & \omega^{7} & \omega^{6} & \omega^{5} & \omega^{4} & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

$\omega^4=-1$ , $\omega^5=-\omega$ , $\omega^6=-\omega^2$ , $\omega^7=-\omega^3$ को replace करने के बाद हमारे पास मूल (original) Vandermonde matrix है:

\mathbf{V} =\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & -1 & -\omega & -\omega^{2} & -\omega^{3} \\ 1 & \omega^{2} & -1 & -\omega^{2} & 1 & \omega^{2} & -1 & -\omega^{2} \\ 1 & \omega^{3} & -\omega^{2} & \omega & -1 & -\omega^{3} & \omega^{2} & -\omega \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -\omega & \omega^{2} & -\omega^{3} & -1 & \omega & -\omega^{2} & \omega^{3} \\ 1 & -\omega^{2} & -1 & \omega^{2} & 1 & -\omega^{2} & -1 & \omega^{2} \\ 1 & -\omega^{3} & -\omega^{2} & -\omega & -1 & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

Exercise: unity के 8-th roots पर $f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6$ को evaluate करें। फिर से, ध्यान दें कि आप $a_7=0$ सेट कर सकते हैं।

Exercise: $\mathbb{F}_q$ में unity के 4-th roots पर $f(x)=3 +2x+9x^2+x^3$ को evaluate करें जहाँ $q=17$ है। एक शुरुआती बिंदु (starting point) के रूप में primitive 4-th root of unity खोजने के लिए Python का उपयोग करें।

सारांश

Square root expansion का उपयोग करके unity के $k$ -th roots पर एक polynomial को evaluate करने से वही evaluations मिलते हैं जो unity के roots पर polynomial को एक-एक करके evaluate करने पर मिलते हैं। यह Image Preservation Theorem for Multivalued Functions के कारण सत्य होता है क्योंकि हम केवल डोमेन $\set{1}$ पर multivalued function को evaluate कर रहे हैं।

यह विधि computation cost बचाती है क्योंकि प्रत्येक चरण (step) में, आधे square roots को evaluate किया जाता है और उस coefficient या coefficients के योग (sum) से गुणा किया जाता है जिसके साथ उन्हें जोड़ा (paired) गया है। बचे हुए evaluations के लिए, परिणामों को फिर से evaluate करने के बजाय केवल नीचे कॉपी कर लिया जाता है।