गुणांक रूप और बिंदु रूप में गुणन के बीच तुल्यता सिद्ध करने के लिए कनवोल्यूशन प्रमेय का उपयोग करना

Last updated on Jun 16, 2026

इस सीरीज़ की शुरुआत में, हमने यह तर्क दिया था कि अधिकतम $n$ degree वाले दो polynomials के multiplication को $\mathcal{O}(n)$ complexity time में किया जा सकता है, यदि दोनों polynomials point-value form में हों।

व्यवहार में (In practice), कठिनाई यह है कि polynomials आमतौर पर coefficient form में दिए जाते हैं, और हम चाहते हैं कि multiplication का परिणाम भी coefficient form में ही हो।

सौभाग्य से, इन समस्याओं को NTT और INTT के fast versions का उपयोग करके हल किया जा सकता है।

Coefficient form में दर्शाए गए दो polynomials को $\mathcal{O}(n \log n)$ time में multiply करने की प्रक्रिया इस प्रकार है:

NTT का उपयोग करके, polynomials को coefficient form से point-value form में convert किया जाता है।
Point-value form वाले polynomials को pointwise multiply किया जाता है। इसे $\mathcal{O}(n)$ time complexity में किया जा सकता है, और परिणाम point-value form में प्राप्त होता है।
INTT का उपयोग करके परिणामी polynomial को वापस coefficient form में transform किया जाता है।

$n$ -th roots of unity का उपयोग करके, जहाँ $n$ , $2$ की घात (power) है, step 1 और 3 को $\mathcal{O}(n \log n)$ time में किया जा सकता है।

एकमात्र सीमा (limitation) यह है कि हमें परिणामी polynomial पर अधिकतम degree $n-1$ निर्धारित करनी होगी। इसलिए, जिन दो polynomials को हम multiply करना चाहते हैं, उनकी degrees का योग $n-1$ से अधिक नहीं हो सकता।

व्यवहार में, यह आम तौर पर कोई समस्या नहीं है, क्योंकि हम अक्सर ऐसे fields का उपयोग कर सकते हैं जिनमें पर्याप्त रूप से बड़े $n$ -th roots of unity होते हैं ताकि polynomials की degree अनुमत सीमा (allowed bound) के भीतर रहें।

$n-1$ से कम degree वाले polynomials कोई समस्या उत्पन्न नहीं करते हैं, क्योंकि उन्हें degree $n-1$ तक zero-valued coefficients के साथ pad किया जा सकता है।

Fast NTT और INTT का उपयोग किए बिना, polynomial multiplication की time complexity $\mathcal{O}(n^2)$ होगी।

इस अध्याय का उद्देश्य हमारे दावे को साबित करना है। हम दिखाएंगे कि coefficient form में दो polynomials को multiply करना, प्रत्येक polynomial पर NTT लागू करने, pointwise multiplication करने, और फिर इस operation से प्राप्त परिणामी polynomial पर INTT लागू करने के equivalent है।

Polynomial multiplication के संदर्भ में इस परिणाम को convolution theorem के रूप में जाना जाता है। अधिक सामान्य संदर्भ में, convolution theorem यह बताता है कि

“original domain में convolution, transformed domain में pointwise multiplication के equivalent है।”

इस theorem को ठीक से समझने के लिए, हमें यह परिभाषित करने से शुरुआत करनी होगी कि convolution क्या है।

Mathematics में कम रुचि रखने वाले पाठक continuity खोए बिना इस अध्याय को छोड़ सकते हैं। पाठ के बाकी हिस्से में, हम convolution theorem को साबित करते हैं, लेकिन यदि पाठक केवल इसके application में रुचि रखता है, तो यह स्वीकार करना पर्याप्त है कि इसका उपयोग $\mathcal{O}(n^2)$ के बजाय $\mathcal{O}(n \log n)$ time complexity में polynomials को multiply करने के लिए किया जा सकता है।

Convolution

Coefficient form में दो polynomials को multiply करना convolution operation का एक उदाहरण है।

मान लीजिए कि degree 2 के दो polynomials हैं,

f(x) = a_0 + a_1x + a_2 x^2

और

g(x) = b_0 + b_1 x + b_2 x^2.

Coefficient form में multiplication से यह polynomial प्राप्त होता है:

\begin{aligned} h(x) = f(x)g(x) &= a_0b_0 + a_0b_1 x+a_0b_2x^2 + \\ &+ a_1b_0x + a_1b_1x^2 + a_1b_2x^3 \\ &+ a_2 b_0 x^2 + a_2 b_1 x^3 + a_2b_2x^4. \end{aligned}

इस expression को rearrange करने पर, हमें प्राप्त होता है:

\begin{aligned} h(x) = f(x)g(x) &= a_0b_0 \\ &+ (a_0 b_1 + a_1b_0)x \\ &+ (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 \\ &+ (a_1 b_2 + a_2 b_1) x^3 \\ &+ a_2 b_2 x^4. \end{aligned}

इस प्रकार, $f(x)$ और $g(x)$ के multiplication से प्राप्त polynomial के coefficients हैं:

\begin{aligned} c_0 &= a_0b_0, \\ c_1 &= a_0 b_1 + a_1b_0, \\ c_2 &= a_0 b_2 + a_1 b_1 + a_2 b_0, \\ c_3 &= a_1 b_2 + a_2 b_1, \\ c_4 &= a_2 b_2. \end{aligned}

इन coefficients को सूत्र (formula) द्वारा संक्षिप्त (compactly) रूप में व्यक्त किया जा सकता है:

c_k = \sum_{i=0}^{k} a_i b_{k-i}

$k=0,1,2,3,4$ के लिए, जो polynomial $h(x)$ की degree है। आइए इसे coefficients में से एक, $c_3$ के लिए जाँचें। इस coefficient के लिए, हमारे पास है:

c_3 = \sum_{i=0}^{3} a_i b_{3-i} = a_0 b_3 + a_1 b_ 2 + a_2 b_1 + a_3 b_0.

चूँकि $a_3$ और $b_3$ दोनों शून्य हैं (क्योंकि polynomials $f(x)$ और $g(x)$ की degree 2 है), यह इसमें reduce हो जाता है:

c_3 = a_1 b_2 + a_2 b_1,

जैसा कि अपेक्षित था।

जिस operation को

c_k = \sum_{i=0}^{k} a_i b_{k-i}

द्वारा परिभाषित किया गया है, उसे convolution कहा जाता है और आमतौर पर इसे इस प्रकार लिखा जाता है:

c_k = (a \ast b)_k,

जहाँ $\ast$ convolution operator को दर्शाता है।

The Convolution Theorem

हमारा लक्ष्य यह साबित करना है कि $f(x)$ और $g(x)$ को point-value form में convert करना, corresponding points को multiply करना, और परिणाम को वापस coefficient form में convert करना, $f(x)$ और $g(x)$ के coefficients के convolution को perform करने के equivalent है।

इन polynomials पर विचार करें:

f(x)=a_0 + a_1x+a_2x^2 + ... +a_px^p

और

g(x)=b_0 + b_1x+b_2x^2 + ... +b_qx^q

जिनकी degree $p$ और $q$ हैं।

$f(x)$ और $g(x)$ को multiply करने पर एक नया polynomial $h(x)$ प्राप्त होता है, जिसकी degree क्रमशः $f(x)$ और $g(x)$ की degrees $p$ और $q$ का sum (योग) होती है।

मान लीजिए कि $h(x)$ की degree $n-1$ है।

इस प्रकार, हम यह compute करना चाहते हैं:

h(x) = f(x)g(x) = c_0 + c_1 x + c_2 x^2 + \ldots + c_{n-1} x^{n-1}

यदि degree $n-1$ से कम है, तो हम higher-degree terms के coefficients को शून्य (zeros) के साथ pad कर सकते हैं।

आइए हम polynomials $f(x)$ और $g(x)$ के coefficients को इस प्रकार दर्शाएं:

\begin{aligned} [a_0, a_1, a_2, ..., a_{n-1}], \\ [b_0, b_1, b_2, ..., b_{n-1}]. \end{aligned}

ऊपर दिए गए कुछ higher-degree coefficients शून्य होंगे, क्योंकि $f(x)$ और $g(x)$ की degrees का योग अधिकतम $n-1$ होना चाहिए। यह कोई समस्या नहीं है। हमारी एकमात्र पाबंदी (restriction) यह है कि:

deg⁡(f)+deg⁡(g)=deg⁡(h)≤n−1.

हमारा पहला कदम polynomials $f(x)$ और $g(x)$ को coefficient form से point-value form में convert करना है।

First step: polynomials को point-value form में convert करना।

इन polynomials को point-value form में convert करने के लिए, हम NTT का उपयोग करते हैं। $n$ को $2$ की घात (power) के रूप में चुनकर, हम fast transform लागू कर सकते हैं। हालाँकि, चूँकि अंतिम परिणाम Vandermonde matrix द्वारा multiplication के equivalent है, इसलिए हम matrix formulation प्रस्तुत करेंगे।

उदाहरण के लिए, polynomial $f(x)$ के लिए, $n$ -th roots of unity पर इसके evaluations इस प्रकार दिए गए हैं:

\begin{bmatrix} f(1) \\ f(\omega) \\ f(\omega^2) \\ \vdots \\ f(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2\\ \vdots \\ a_{n-1} \end{bmatrix}.

इसी प्रकार, $g(x)$ के लिए,

\begin{bmatrix} g(1) \\ g(\omega) \\ g(\omega^2) \\ \vdots \\ g(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \\ b_2\\ \vdots \\ b_{n-1} \end{bmatrix}.

इन matrix operations को componentwise इस प्रकार लिखा जा सकता है:

f(\omega^i) = \sum_{r=0}^{n-1} a_r \omega^{ri}

और

g(\omega^i) = \sum_{s=0}^{n-1} b_s \omega^{si}.

उदाहरण के लिए, $f(\omega^2)$ का evaluation इस प्रकार दिया जाता है:

f(\omega^2) = \sum_{r=0}^{n-1} a_r \omega^{r2} = a_0 \omega^{0 \cdot 2} + a_1 \omega^{1 \cdot 2} + a_2 \omega^{2 \cdot 2} + \ldots + a_{n-1} \omega^{{(n-1)} \cdot 2}

Second step: point-value form में polynomials का pointwise multiplication करना।

अब हम product polynomial $h(x)$ के evaluations प्राप्त करने के लिए $f(x)$ और $g(x)$ के evaluations को pointwise multiply करते हैं:

\begin{aligned} h(\omega^0)&= f(\omega^0)g(\omega^0) \\ h(\omega^1)&= f(\omega^1)g(\omega^1) \\ &\vdots \\ h(\omega^{n-1})&= f(\omega^{n-1})g(\omega^{n-1}) \end{aligned}

Index notation में, इसे इस प्रकार लिखा जा सकता है:

h(\omega^i) = f(\omega^i) g(\omega^i).

पिछले step में प्राप्त $f(\omega^i)$ और $g(\omega^i)$ के expressions का उपयोग करते हुए, हमें प्राप्त होता है:

h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si}\right).

संक्षेप में (To recap), हम जो दिखाना चाहते हैं वह यह है कि यदि हम point-value form (उपरोक्त form) में polynomial $h(x)$ पर INTT perform करते हैं, तो परिणाम $f(x)$ और $g(x)$ का convolution perform करने के समान ही होता है।

Last step: point-value form में polynomial $h(x)$ पर INTT लागू करना

$n$ -th roots of unity पर Inverse Number Theoretic Transform (INTT) को Vandermonde matrix $V(\omega^{-1})$ का उपयोग करके perform किया जाता है, जिसे $\frac{1}{n}$ के factor से scale किया गया हो।

इस प्रकार, $h(\omega^i)$ points के सेट पर INTT लागू करके, हम coefficient form में polynomial $h(x)$ प्राप्त करते हैं:

\begin{bmatrix} c_0 \\ c_1 \\ c_2\\ \vdots \\ c_{n-1} \end{bmatrix} = \frac{1}{n}\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(n-1)} \\1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{-(n-1)} & \omega^{-2(n-1)} & \cdots & \omega^{-(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} h(\omega^0) \\ h(\omega^1) \\ h(\omega^2) \\ \vdots \\ h(\omega^{n-1}) \end{bmatrix}

इसे component-wise इस प्रकार लिखा जा सकता है:

c_p = \frac{1}{n} \sum_{i=0}^{n-1} h(\omega^i) \omega^{-ip}.

इस तथ्य का उपयोग करते हुए कि $h(\omega^i)$ इस प्रकार दिया गया है:

h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right),

हमारे पास यह है कि:

c_p = \frac{1}{n} \sum_{i=0}^{n-1} \underbrace{\left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right)}_{h(\omega^i)} \omega^{-ip}.

यह expression बड़ा है, लेकिन इसे roots of unity की orthogonality property लागू करके सरल किया जा सकता है।

सबसे पहले, आइए $\omega$ की सभी powers को group करें:

\begin{aligned} c_p &= \frac{1}{n} \sum_{i=0}^{n-1} \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right) \omega^{-ip} && \text{\small ऊपर प्राप्त expression} \\ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)\,\omega^{ri}\,\omega^{si}\,\omega^{-ip} && \text{\small sums और terms को group करें} \\ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)\,\omega^{i(r+s-p)} && \text{\small }\omega^i\text{\small के exponents को combine करें} \\ &= \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s) \left( \sum_{i=0}^{n-1} \omega^{i(r+s-p)} \right) && \text{\small sum of roots of unity को isolate करें}. \end{aligned}

उपरोक्त expression यह इंगित करता है कि हम इसे सरल बनाने के लिए roots of unity की orthogonality का उपयोग कर सकते हैं।

याद रखें कि roots of unity की orthogonality property इस प्रकार दी गई है:

\sum_{i=0}^{n-1} (\omega^{i})^{r-s}=\begin{cases}n, & \text{यदि } r\equiv s \pmod{n},\\[6pt]0, & \text{अन्यथा}.\end{cases}

$c_p$ में isolated sum of roots of unity के लिए उपरोक्त सूत्र का उपयोग करते हुए, हम ध्यान देते हैं कि:

\sum_{i=0}^{n-1} \omega^{i(r+s-p)}

$n$ के बराबर है यदि $s = p-r \pmod{n}$ (या equivalent रूप से $r=p-s \pmod{n}$ ), और अन्यथा शून्य है।

इसे Kronecker delta से गुणा किए गए $n$ के रूप में represent किया जा सकता है:

\sum_{i=0}^{n-1} \omega^{i(r+s-p)} = n \delta_{s,p-r}

\sum_{i=0}^{n-1} \omega^{i(r+s-p)}

को $c_p$ के expression में replace करने पर, हमें प्राप्त होता है कि:

c_p = \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(n \delta_{s, p-r})

Constants $\frac{1}{n}$ और $n$ आपस में cancel हो जाते हैं:

c_p = \frac{1}{\cancel{n}} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(\cancel{n} \delta_{s, p-r})

अधिक महत्वपूर्ण बात यह है कि index $s$ पर sum करते समय, $s=p-r$ को छोड़कर सभी terms शून्य (vanish) हो जाते हैं। यह roots of unity की orthogonality के कारण है।

परिणामस्वरूप, $s$ पर summation collapse हो जाता है, और हम $b_s$ में summation को एकल (single) element $b_{p-r}$ से replace कर सकते हैं। हमें प्राप्त होता है:

c_p = \sum_{r=0}^{n-1} a_r b_{p-r}

यह बिल्कुल convolution formula ही है!

आइए याद करें कि हमने क्या किया:

हमने polynomials $f(x)$ और $g(x)$ पर NTT लागू किया, उनके coefficient representations को point-value representations में convert किया, यानी वे vectors जिनमें $n$ -th roots of unity पर उनके evaluations शामिल हैं:

\big(f(1), f(\omega), \ldots, f(\omega^{n-1})\big)\quad \text{और} \quad\big(g(1), g(\omega), \ldots, g(\omega^{n-1})\big)

हमने इन evaluation values को pointwise multiply किया, जिसका अर्थ है कि प्रत्येक root of unity $\omega^i$ के लिए हमने यह compute किया:

h(\omega^i)=f(\omega^i)g(\omega^i)

जिससे product polynomial $h(x)$ का point-value representation प्राप्त हुआ।

हमने values के इस vector पर INTT लागू किया:

\big(h(1), h(\omega), \ldots, h(\omega^{n-1})\big)

ताकि $h(x)$ का coefficient representation वापस प्राप्त (recover) किया जा सके।

हमने दिखाया कि ये तीन steps ठीक वही परिणाम देते हैं जो polynomials $f(x)$ और $g(x)$ को multiply करने पर मिलता है, अर्थात, $f(x)$ और $g(x)$ के coefficients का convolution करना।

हालाँकि, जबकि direct convolution की time complexity $\mathcal{O}(n^2)$ होती है, उपरोक्त प्रक्रिया को $\mathcal{O}(n \log n)$ time में execute किया जा सकता है, जिससे वही अंतिम polynomial प्राप्त होता है।

Convolution theorem बिल्कुल यही बताता है। अधिक formal तरीके से, हम इसे इस प्रकार लिख सकते हैं:

मान लीजिए कि $f$ और $g$ उनके coefficient form में दो polynomials हैं। मान लीजिए कि $*$ convolution operation को दर्शाता है और $\cdot$ multiplication को दर्शाता है।

मान लीजिए कि $\mathcal{F}(f)$ , $f$ पर NTT के application को दर्शाता है — अर्थात, जबकि $f$ coefficients का vector है, $\mathcal{F}(f)$ evaluations का vector है — और $\mathcal{F}^{-1}(\mathcal{F}(f))$ , $\mathcal{F}(f)$ पर INTT के application को दर्शाता है। तब,

f *g =\mathcal{F}^{-1}(\mathcal{F}(f)\cdot\mathcal{F}(g)).

Convolution theorem को व्यक्त (express) करने का दूसरा तरीका यह है:

\mathcal{F}(f *g) =\mathcal{F}(f)\cdot\mathcal{F}(g).

यह एक linear transformation है, और इसे इस प्रकार समझा जा सकता है: coefficient domain में convolution, point-value domain में pointwise multiplication के equivalent है।

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