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

Last updated on May 5, 2026

जैसा कि पिछले लेख में देखा गया है, Inverse Number Theoretic Transform (INTT) को NTT की तरह ही एक Vandermonde matrix का उपयोग करके निष्पादित किया जाता है। यह दर्शाता है कि NTT के माध्यम से मूल्यांकन (evaluation) और INTT के माध्यम से इंटरपोलेशन (interpolation) दोनों समान संचालन (operations) हैं।

मूल्यांकन या इंटरपोलेशन के लिए सीधे Vandermonde matrix का उपयोग करने में समस्या यह है कि एक $k \times k$ matrix को एक वेक्टर से गुणा करने में $\mathcal{O}(k^2)$ समय लगता है। सौभाग्य से, जब $k$ -th roots of unity का उपयोग किया जाता है, जहाँ $k$ , 2 की घात (power of 2) है, तो एक तेज़ विधि का उपयोग किया जा सकता है जो मैट्रिक्स गुणन (matrix multiplication) पर निर्भर नहीं करती है, जिससे समय जटिलता घटकर $\mathcal{O}(k \log k)$ हो जाती है।

NTT के लिए तेज़ विधि को अध्याय “NTT Algorithm by Hand.” में पेश किया गया था। इस अध्याय में, हम INTT के लिए तेज़ विधि का अध्ययन करेंगे।

विचार सरल है: बहुपद (polynomial) इंटरपोलेशन की व्याख्या एक मूल्यांकन के रूप में करना, जिससे NTT के लिए उपयोग की जाने वाली उसी विधि का उपयोग किया जा सके।

मूल्यांकन और इंटरपोलेशन (Evaluation and Interpolation)

संक्षेप में, NTT हमें अधिकतम $k-1$ डिग्री वाले एक बहुपद को उसके गुणांक (coefficient) रूप से,

\begin{bmatrix}a_0 \\ a_1 \\ ... \\ a_{k-1} \end{bmatrix}

उसके point-value रूप में बदलने की अनुमति देता है,

\begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ ... \\ f(\omega^{k-1}) \end{bmatrix}

बहुपद का $k$ -th roots of unity पर मूल्यांकन करके। इसे मूल्यांकन (evaluation) कहा जाता है।

इंटरपोलेशन (Interpolation) मूल्यांकन के विपरीत है: यह एक बहुपद को उसके point-value रूप से गुणांक रूप में बदलने की प्रक्रिया है।

मूल्यांकन के रूप में इंटरपोलेशन

$k$ -th roots of unity पर मूल्यांकन और इंटरपोलेशन समान संचालन हैं क्योंकि दोनों एक Vandermonde matrix का उपयोग करके निष्पादित किए जाते हैं।

बेहतर ढंग से समझने के लिए, अधिकतम 3 डिग्री वाले एक बहुपद पर विचार करें,

f(x) = a + bx + cx^2 + dx^3,

जिसका $4$ -th roots of unity पर मूल्यांकन किया गया हो

f(1), f(\omega), f(\omega^{2}),f(\omega^{3}).

मूल्यांकन को इस प्रकार लिखा जा सकता है

\begin{aligned}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}=\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega & \omega^2 & \omega^3 \\1 & \omega^2 & \omega^4 & \omega^6 \\1 & \omega^3 & \omega^6 & \omega^9\end{bmatrix}\begin{bmatrix}a \\b \\c \\d\end{bmatrix}.\end{aligned}

इंटरपोलेशन को इस प्रकार लिखा जा सकता है

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

मूल्यांकन संरचना से प्रेरित होकर, हम $\frac{f(1)}{4}, \frac{f(\omega)}{4}, \frac{f(\omega^2)}{4}$ और $\frac{f(\omega^3)}{4}$ को एक नए बहुपद $\tilde{f}(x)$ के गुणांकों के रूप में देख सकते हैं, जिसे इस प्रकार परिभाषित किया गया है:

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big).

इन संदर्भों में, गुणांक $a,b,c$ और $d$ निम्नलिखित बिंदुओं पर $\tilde{f}(x)$ के मूल्यांकन हैं:

\begin{aligned} a &= \tilde{f}(1) \\ b &= \tilde{f}(\omega^{-1}) \\ c &= \tilde{f}(\omega^{-2}) \\ d &= \tilde{f}(\omega^{-3}) \\ \end{aligned}

इसलिए, हम इंटरपोलेशन की व्याख्या किसी अन्य बहुपद के मूल्यांकन के रूप में कर सकते हैं। महत्वपूर्ण अवलोकन यह है कि inverse NTT को किसी मौलिक रूप से अलग एल्गोरिदम की आवश्यकता नहीं होती है।

एक बार जब point-value निरूपण को एक नए बहुपद के गुणांक वेक्टर के रूप में फिर से व्याख्यायित किया जाता है, तो इंटरपोलेशन, roots of unity के एक क्रमपरिवर्तित (permuted) सेट पर मूल्यांकन बन जाता है। इस अर्थ में, मूल्यांकन और इंटरपोलेशन एक ही संचालन हैं।

Roots of unity के व्युत्क्रमों (inverses) के साथ काम करने से बचना

जैसा कि इस परिवर्तन (transformation) में दिखाया गया है

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}, \end{aligned}

इंटरपोलेशन में roots of unity के व्युत्क्रमों (inverses) पर मूल्यांकन शामिल हैं। हालाँकि, हम inverses के साथ काम करने से बच सकते हैं।

$\omega^{-1}$ पर विचार करें। $4$ th roots of unity में, यह वह तत्व है, जिसे $\omega$ से गुणा करने पर 1 प्राप्त होता है। चूँकि

\omega \cdot \omega^3 = \omega^4 \equiv 1,

हमारे पास $\omega^{-1} = \omega^3$ है।

इसी तरह,

\begin{aligned} \omega^{-2} &= \omega^2, \\ \omega^{-3} &= \omega. \end{aligned}

इस प्रकार, गुणांक $a,b,c$ और $d$ निम्नलिखित के मूल्यांकन हैं

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

निम्नलिखित बिंदुओं पर:

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{3}), \\ c &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{2}), \\ d &= \tilde{f}(\omega^{-3}) = f(\omega). \\ \end{aligned}

इस तथ्य का उपयोग करते हुए कि $\omega^2 = -1$ है, हम इन्हें इस प्रकार फिर से लिख सकते हैं:

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{3}) = \tilde{f}(-\omega), \\ c &= \tilde{f}(\omega^{2}) = \tilde{f}(-1), \\ d &= \tilde{f}(\omega^{}). \\ \end{aligned}

INTT को हाथ से करना

अधिकतम $k-1$ डिग्री वाले एक बहुपद, जहाँ $k$ , 2 की घात है, का मूल्यांकन $k$ -th roots of unity पर अध्याय NTT Algorithm by Hand में समझाई गई तेज़ विधि का उपयोग करके किया जा सकता है।

निम्नलिखित का

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

बिंदुओं $\tilde{f}(1), \tilde{f}(-1), \tilde{f}(\omega)$ और $\tilde{f}(-\omega)$ पर मूल्यांकन नीचे दर्शाया गया है।

विचार यह है कि सम (even) और विषम (odd) घातों (powers) को इस प्रकार समूहीकृत किया जाए

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega^2) x^2) + x(f(\omega) + f(\omega^3) x^2)\big),

और $\sqrt{\sqrt{1}}$ पर $\tilde{f}(x)$ का मूल्यांकन किया जाए। सबसे अंदरूनी वर्गमूल (square root) के प्रत्येक मूल्यांकन पर, व्यंजक (expression) दो भागों में बंट जाता है, वर्गमूल के प्रत्येक मान के लिए एक। यह तब तक जारी रहता है जब तक कि कोई वर्गमूल नहीं बचता, जिस बिंदु पर प्रक्रिया समाप्त हो जाती है।

हम प्राप्त करते हैं

\begin{aligned} a&= \tilde{f}(1) = \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b&= \tilde{f}(-\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c&= \tilde{f}(-1) = \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d&= \tilde{f}(\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \\\end{aligned}

आइए पुष्टि करें कि यह Vandermonde matrix से प्राप्त परिणाम से मेल खाता है:

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

इसका उपयोग करते हुए

\begin{aligned} \omega^{-1} &= \omega^3 = - \omega, \\ \omega^{-2} &= \omega^2 = -1, \\ \omega^{-3} &= \omega, \end{aligned}

हम इसे इस प्रकार फिर से लिखते हैं:

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & - \omega & -1 & \omega \\1 & -1 & 1 & -1 \\1 & \omega & -1 & -\omega\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\ f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

इससे प्राप्त होता है

\begin{alignat*}{3} a &= \tilde{f}(1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b &= \tilde{f}(-\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c &= \tilde{f}(-1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d &= \tilde{f}(\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \end{alignat*}

जो वही व्यंजक (expressions) हैं जो तेज़ एल्गोरिदम द्वारा प्राप्त किए गए थे।

मुख्य अंतर यह है कि तेज़ एल्गोरिदम $\mathcal{O}(k \log k)$ समय में चलता है, जबकि सीधे मैट्रिक्स गुणन (matrix multiplication) में $\mathcal{O}(k^2)$ समय लगता है।

$k-1$ डिग्री वाले बहुपद

हमने पिछले अनुभाग में $3$ डिग्री के बहुपद के लिए जो किया, उसे किसी भी डिग्री के बहुपदों तक बढ़ाया जा सकता है।

मान लीजिए कि हमारे पास एक बहुपद $f(x)$ है जिसका $k$ -th roots of unity पर मूल्यांकन किया गया है, जहाँ $k$ , $2$ की घात है:

f(\omega^0), f(\omega^1), f(\omega^2), ..., f(\omega^{k-1})

अधिकतम $k-1$ डिग्री वाले बहुपद $f(x)$ के गुणांकों को प्राप्त करने के लिए, जो इन बिंदुओं से होकर गुजरता है, हम एक नए बहुपद $\tilde{f}(x)$ को इस प्रकार परिभाषित करते हैं:

\tilde{f}(x) = \frac{1}{k}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + ...+ f(\omega^{k-1}) x^{k-1}\big)

तब $f(x)$ के गुणांक इस प्रकार दिए जाते हैं:

\begin{aligned} a_0 &= \tilde{f}(\omega^0) \\ a_1 &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{k-1}) \\ a_2 &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{k-2}) \\ ... \\ a_{k-1} &= \tilde{f}(\omega^{-(k-1)}) = \tilde{f}(\omega^{1}) \\ \end{aligned}

यह लेख हमारी ZK Book में Number Theoretic Transform पर आधारित श्रृंखला का हिस्सा है