हम इस अध्याय की शुरुआत एक असामान्य बात से करेंगे — NTT एल्गोरिदम काफी सरल है और इसे 20 से कम लाइन के कोड में लागू (implement) किया जा सकता है। हालाँकि, इसके काम करने के पीछे का जो मुख्य विचार है, अजीब तरह से, उसका कोई औपचारिक गणितीय नाम नहीं है। इसलिए हम इस एल्गोरिदम के पीछे की मुख्य थ्योरम (core theorem) को एक (व्यक्तिगत रूप से) आकर्षक नाम देने की स्वतंत्रता ले रहे हैं:

मल्टीवैल्यूड फंक्शन्स के लिए इमेज प्रिजर्वेशन थ्योरम (The Image Preservation Theorem for Multivalued Functions)

इमेज प्रिजर्वेशन थ्योरम को समझाने के लिए, हम roots of unity के बारे में एक अंतिम (बहुत ही सरल) कॉन्सेप्ट पर चर्चा करेंगे, और फिर थ्योरम को प्रस्तुत करेंगे।

नेस्टेड स्क्वायर रूट्स (nested square roots) के $k$-th रूट्स

“k-th root of unity” की शाब्दिक परिभाषा यह है कि root of unity $a$, $a^k\equiv1$ को संतुष्ट करता है। दूसरे शब्दों में कहें तो:

इसलिए, इसमें कोई आश्चर्य नहीं होना चाहिए कि यदि $\omega$ एक primitive 4-th root of unity है, तो

अब मान लीजिए कि $\omega$ एक primitive 8-th root of unity है, और हम यही ऑपरेशन करते हैं। इसका परिणाम होगा:

और 1 का 8-th रूट सभी 8-th roots of unity उत्पन्न करता है:

ये अवलोकन (observations) केवल परिभाषा का मामला हैं। बेशक, हम 1 का स्क्वायर रूट सीधे (directly) कैलकुलेट नहीं करना चाहते हैं। इसके बजाय, पहले primitive $k$-th root of unity खोजना और फिर $\sqrt[8]{1}$ के लिए उत्तरों का सेट उत्पन्न करना बहुत आसान है। उदाहरण के लिए:

Copy
import galois
Fq = 17
k = 8
assert (Fq - 1) % k == 0, "no such subgroup"

GF = galois.GF(Fq)

pr = GF.primitive_root_of_unity(k)

roots = []
for i in range(0,k):
    roots.append(pr**i)
print(roots)

हम यह भी देख सकते हैं कि:

और इसी तरह। जैसा कि ऊपर बताया गया है, सीधे $\sqrt[k]{1}$ की गणना करना एफ़िशिएंट (efficient) नहीं है। इसके बजाय, हम निम्नलिखित आरेख (diagram) पर विचार करते हैं, जहाँ नीचे की ओर जाने वाला प्रत्येक तीर अपने ऊपर वाली संख्या का स्क्वायर रूट है:

हम 1 से शुरुआत करके और बार-बार स्क्वायर रूट लेकर 8-th roots of unity की गणना कर सकते हैं।

किसी भी arbitrary $k$ के लिए, आरेख इस प्रकार है।

यहाँ स्क्वायर रूट गणनाओं का एक वॉकथ्रू (walkthrough) दिया गया है:

1 का स्क्वायर रूट $\set{1,\omega^{k/2}}$ है। $\omega^{k/2}$, -1 के सर्वांगसम (congruent) है।

पिछले अध्याय से याद करें कि $\omega^m$ का स्क्वायर रूट $\omega^{m/2}$ और $-\omega^{m/2}$ होता है (यह मानते हुए कि $m$ सम/even है)।

इस प्रकार, $\omega^{k/2}$ का स्क्वायर रूट $\set{\omega^{k/4},-\omega^{k/4}}$ है।

यह भी याद रखें कि $\omega^i$ का योज्य प्रतिलोम (additive inverse) $\omega^{i+k/2}$ है।

इसलिए नकारात्मक (negative) चिह्न के बिना $-\omega^{k/4}$ की गणना करने के लिए, हम $\omega^{k/4+k/2}=\omega^{k/4+2k/4}=\omega^{3k/4}$ की गणना करते हैं। अतः $\omega^{k/2}$ का स्क्वायर रूट $\set{\omega^{k/4},\omega^{3k/4}}$ है।

$\omega^{k/4}$ का स्क्वायर रूट ${\omega^{k/8},-\omega^{k/8}}$ है। फिर से, नकारात्मक चिह्न को हटाने के लिए, हम $\omega^{k/8+k/2}=\omega^{5k/8}$ की गणना करते हैं।

$\omega^{3k/4}$ का स्क्वायर रूट $\set{\omega^{3k/8},\omega^{7k/8}}$ क्यों है, यह पाठक के लिए एक अभ्यास (exercise) के रूप में छोड़ दिया गया है।

ट्री (tree) की ऊंचाई $\log_2n$ है

1 का बार-बार स्क्वायर रूट लेकर $k$-th roots of unity की गणना करने पर एक “ट्री” बनता है जिसकी ऊंचाई $\log_2(n)$ होती है।

ट्री की मध्यवर्ती अवस्थाओं (intermediate states) की संकल्पना

सेट

गणितीय रूप से 8-th roots of unity के समतुल्य (equivalent) है। यह सेट इसके भी समतुल्य है:

जो इसके भी समतुल्य है:

दूसरे शब्दों में:

एक त्वरित विषय-अंतर (Quick aside) — मल्टीवैल्यूड फंक्शन्स और इमेजेस (images)

यह सच है कि हमने ऊपर जो अवलोकन किए हैं, वे $k$-th रूट्स की परिभाषा के सामान्य विस्तार (trivial extensions) हैं। इन अवलोकनों के अधिक रोचक निहितार्थ (implications) अगले भाग में दिखाए जाएंगे। हालाँकि, पहले कुछ गणितीय शब्दावली का परिचय देना मददगार होगा:

फंक्शन की इमेज (Image of a function) — यदि हमारे पास बिंदुओं (points) का एक सेट है जिस पर हम किसी फंक्शन का मूल्यांकन करते हैं, तो मूल्यांकनों का सेट इमेज (image) कहलाता है। उदाहरण के लिए, यदि फंक्शन $f(x)=2x$ है और जिस डोमेन (domain) पर हम $f$ का मूल्यांकन करते हैं वह $\set{1,2}$ है, तो इमेज $\set{2,4}$ होगी। किसी फंक्शन की रेंज (range) का अर्थ उन मानों का सेट है जो एक फंक्शन आउटपुट कर सकता है। हमारे संदर्भ में, फंक्शन की इमेज से तात्पर्य दिए गए इनपुट्स के सेट के लिए आउटपुट्स के वास्तविक सेट से है।

मल्टीवैल्यूड फंक्शन (Multivalued function) — एक ऐसा फंक्शन जो डोमेन में एक ही बिंदु के लिए एक से अधिक मूल्यांकन (evaluation) लौटा सकता है। उदाहरण के लिए, 0 पर मूल्यांकित $\sqrt{x}$, 0 लौटाता है, लेकिन 1 पर मूल्यांकित $\sqrt{x}$, $\set{1, -1}$ लौटाता है।

नोट: मल्टीवैल्यूड फंक्शन $f(x)=\sqrt{x}$ की इमेज उसके डोमेन से बड़ी होती है।

इन परिभाषाओं को ध्यान में रखते हुए, पाठक को निम्नलिखित कथनों को समझना चाहिए:

“डोमेन $\set{0,2}$ पर $f(x)=x+1$ की इमेज $\set{1,3}$ है”

“डोमेन $\set{1}$ पर मल्टीवैल्यूड फंक्शन $f(x)=\sqrt{x}$ की इमेज $\set{1,-1}$ है”

अब हम अवलोकनों के एक अधिक रोचक सेट पर आते हैं।

$\set{1,...,\omega^7}$ पर मूल्यांकित $f(x)=x$ की इमेज, $\set{1}$ (k = 8) पर मूल्यांकित $g(x)=\sqrt[8]{x}$ के समान है

यह दावा ऊपर दिखाए गए कॉन्सेप्ट्स का एक सरल पुनर्लेखन है, इसलिए हम इस पर अधिक विस्तार से चर्चा नहीं करेंगे। दिलचस्प बात यह है कि हम इसे अन्य फंक्शन्स के लिए कैसे सामान्यीकृत (generalize) कर सकते हैं।

यहाँ सूक्ष्म बात (nuance) यह है कि $g(x)$ एक मल्टीवैल्यूड फंक्शन है जो आठ एलीमेंट्स (elements) लौटाता है।

4-th roots of unity पर मूल्यांकित $f(x)=ax$ की इमेज, $\set{1}$ (k = 4) पर मूल्यांकित मल्टीवैल्यूड फंक्शन $g(x)=a\sqrt[4]{x}$ के समान है

याद रखें, $\sqrt[4]{1}=\set{1,\omega,\omega^2,\omega^3}$, इसलिए $a\sqrt[4]{1}=\set{a,a\omega,a\omega^2,a\omega^3}$। यह बिल्कुल उसी इमेज के समान है जो प्रत्येक root of unity पर एक-एक करके $f$ का मूल्यांकन करने से प्राप्त होती है। चूँकि $f(x)=ax$

• $f(1)=a$
• $f(\omega)=a\omega$
• $f(\omega^2)=a\omega^2$
• $f(\omega^3)=a\omega^3$

पाठक के लिए अभ्यास: मान लीजिए $f(x)=ax+c$ है। 4-th roots of unity पर $f(x)$ की इमेज क्या है? डोमेन $\set{1}$ पर मल्टीवैल्यूड फंक्शन $g(x)=a\sqrt[4]{x}+b$ की इमेज क्या है?

आने वाले अध्यायों में, हम दिखाएंगे कि $f(x)=x^2+x^3$ जैसे अधिक जटिल मामलों को कैसे सँभाला जाए, लेकिन अभी के लिए, हम दिखाते हैं कि वास्तव में हमारे द्वारा दिखाए गए सरल मामलों के लिए मल्टीवैल्यूड फंक्शन्स की गणना कैसे की जाती है। लेकिन पहले, आइए इमेज समतुल्यता (image equivalence) के बारे में अब तक किए गए अवलोकन को एक औपचारिक परिभाषा देते हैं।

4-th roots of unity पर मूल्यांकित $f(x)=x$ की इमेज, second roots of unity $\set{1,-1}$ (k = 4) पर मूल्यांकित मल्टीवैल्यूड फंक्शन $g(x)=\sqrt{x}$ के समान है

यह उदाहरण ऊपर दिए गए उदाहरण के काफी समान है, सिवाय इसके कि हम डोमेन $\set{1}$ को “लक्षित” (target) नहीं करते हैं, बल्कि $\set{1,-1}$ को करते हैं।

हमारे पास है

• $g(1)=\sqrt{1}=\set{1,-1}$
• $g(-1)=\sqrt{-1}=\set{\omega,-\omega}$

यह $\set{1,\omega,-1,-\omega}$ पर $f$ का मूल्यांकन करने पर प्राप्त इमेज के ही समान है।

संक्षेप में, यदि हम डोमेन को $r$ के फैक्टर से “सिकोड़ते” (shrink) हैं और एक नया मल्टीवैल्यूड फंक्शन $g$ बनाने के लिए $f(x)$ के प्रत्येक $x$ को $\sqrt[r]{x}$ से बदल देते हैं, तो $f$ और $g$ की इमेजेस बिल्कुल समान (identical) होती हैं।

अब हम उस कॉन्सेप्ट को औपचारिक रूप से परिभाषित करेंगे जिसे हम दर्शा रहे हैं।

NTT की मुख्य थ्योरम: मल्टीवैल्यूड फंक्शन्स के लिए इमेज प्रिजर्वेशन थ्योरम

मान लीजिए $\omega$ एक primitive $k$-th root of unity है और $\langle\omega\rangle=\set{1,\omega,\omega^2,...}$, $\mathbb{F}_q$ में परिभाषित $k$-th roots of unity हैं।

मान लीजिए $k$, 2 की पावर है।

मान लीजिए $f(x)$, $\mathbb{F}_q$ में एक बहुपद (polynomial) है। मान लीजिए $r$, 2 की एक पावर है जो $k$ से कम या उसके बराबर है।

मान लीजिए $g(x)$ एक मल्टीवैल्यूड फंक्शन है जिसे $f(x)$ के प्रत्येक $x$ को $\sqrt[r]{x}$ से बदलकर बनाया गया है।

मान लीजिए डोमेन $\langle\omega\rangle^r$, $\set{\omega^r|\omega\in \langle\omega\rangle}$ है। ध्यान दें कि यदि $r=k$ है तो $\langle\omega\rangle^r=\set{1}$।

$\langle\omega\rangle$ पर $f$ की इमेज ठीक $\langle\omega\rangle^r$ पर $g$ की इमेज के बराबर होती है।

यह अत्यंत महत्वपूर्ण है कि पाठक उपरोक्त थ्योरम को समझें, क्योंकि यह वह मुख्य कॉन्सेप्ट है जिस पर Number Theoretic Transform निर्भर करता है!

इस कॉन्सेप्ट को पुख्ता (enforce) करने के लिए यहाँ कुछ उदाहरण दिए गए हैं:

• 4-th roots of unity पर $f(x)=x$ की इमेज, second roots of unity पर $g(x)=\sqrt{x}$ की इमेज के बराबर है (जैसा कि पिछले भाग में दिखाया गया है)।
• 16th roots of unity पर $f(x) =x$ की इमेज, 8th roots of unity पर $g(x)=\sqrt{x}$ की इमेज के बराबर है।
• k-th roots of unity पर $f(x) =x$ की इमेज, k/2-th roots of unity पर $g_1(x)=\sqrt{x}$ की इमेज के बराबर है।
• k/2-th roots of unity पर $g_1(x)=\sqrt{x}$ की इमेज, k/4-th roots of unity पर $g_2(x)=\sqrt[4]{x}$ की इमेज के बराबर है।

अगला भाग ऐसे उदाहरण दिखाता है जहाँ $f(x)$ थोड़ा अधिक जटिल है।

$f(x)=ax+b$ के लिए इमेज प्रिजर्वेशन थ्योरम के उदाहरण

मान लीजिए $f(x)=ax+b$ है और डोमेन 4-th roots of unity $\set{1,\omega,\omega^2,\omega^3}$ है।

मान लीजिए $f_1$ एक मल्टीवैल्यूड फंक्शन $a\sqrt{x}+b$ है और डोमेन $\set{1,-1}$ या समतुल्य रूप से $\set{1,-\omega^2}$ है।

मान लीजिए $f_2$ एक मल्टीवैल्यूड फंक्शन $a\sqrt[4]{x}+b$ है और डोमेन $\set{1}$ है।

$f$, $f_1$, और $f_2$ की इमेजेस समान हैं: $\set{a+b,a\omega+b,a\omega^2+b,a\omega^3+b}$

NTT से संबंध

याद रखें, NTT का लक्ष्य $\mathcal{O}(n\log n)$ समय में $k$-th roots of unity पर $f(x)$ का मूल्यांकन करना है। दूसरे शब्दों में, हम $k$-th roots of unity पर $f$ की इमेज की गणना करना चाहते हैं।

आप शायद अनुमान लगा सकते हैं कि यह किस ओर जा रहा है।

$k$-th roots of unity पर $f(x)$ की इमेज की गणना करना एक नए फंक्शन $g(x)$ की इमेज की गणना करने के समतुल्य है, जिसे इस तरह परिभाषित किया गया है कि $f$ में प्रत्येक $x$ के लिए, $x\rightarrow\sqrt[k]{x}$ का मूल्यांकन $\set{1}$ पर किया गया हो।

हालाँकि, यह एक खुला प्रश्न छोड़ देता है:

$\sqrt[k]{x}$ को $\set{1,...,\omega^{k-1}}$ में विस्तारित (expanding) करने से सीधे तौर पर गति (speedup) नहीं बढ़ती है। एल्गोरिथम के दृष्टिकोण से, $\sqrt[k]{1}$ को $k$-th roots of unity में विस्तारित करना $f(x)$ को $k$ बिंदुओं पर मूल्यांकन करने के समान ही है। $f(x)$ का मूल्यांकन करने का यह वैकल्पिक तरीका हमारी कैसे मदद करता है?

अगले अध्याय में, हम दिखाएंगे कि स्क्वायर रूट विस्तार (square root expansion) का उपयोग करके मल्टी-वैल्यूड फंक्शन्स का मूल्यांकन कैसे किया जाता है और यह समझाएंगे कि यह दृष्टिकोण अनावश्यक गणनाओं (redundant computation) को कैसे रोक सकता है।