पॉलीनोमियल मल्टीप्लिकेशन (Polynomial multiplication) का व्यापक रूप से zero-knowledge proofs और गणितीय क्रिप्टोग्राफी (mathematical cryptography) में उपयोग किया जाता है। लेकिन पॉलीनोमियल्स को गुणा करने का ब्रूट फोर्स (brute force) या पारंपरिक तरीका $\mathcal{O}(n^2)$ में चलता है, जो छोटे इनपुट के लिए तो ठीक है लेकिन पॉलीनोमियल की डिग्री बढ़ने के साथ काफी महंगा हो जाता है। यह लेख पॉलीनोमियल मल्टीप्लिकेशन को तेज़ बनाने के तरीकों का पता लगाने के लिए इस पर विस्तृत नज़र डालता है।

• हम स्कूली/पारंपरिक पॉलीनोमियल अंकगणित (polynomial arithmetic) की समीक्षा से शुरुआत करते हैं
• इसके बाद पॉलीनोमियल्स के निरूपण (representation) के विभिन्न रूपों का अध्ययन करेंगे
• हम इन विभिन्न रूपों में पॉलीनोमियल अंकगणित की जांच और तुलना करते हैं
• अंत में, हम देखेंगे कि ये रूप कैसे संभावित रूप से पॉलीनोमियल मल्टीप्लिकेशन को तेज़ कर सकते हैं - और कैसे वे Number Theoretic Transform (NTT) नामक एल्गोरिथ्म का आधार बनाते हैं

पॉलीनोमियल मल्टीप्लिकेशन - पारंपरिक तरीका

मान लीजिए दो पॉलीनोमियल्स $p_1(x)$ और $p_2(x)$ हैं, जिनमें से प्रत्येक की डिग्री $n$ है:

जोड़ के ऊपर गुणा के वितरण (distribution of multiplication over addition) के सरल तरीके का उपयोग करके इन दो पॉलीनोमियल्स को गुणा करने में $\mathcal{O}(n^2)$ समय लगता है। यहाँ, $p_1(x)$ के प्रत्येक पद (term) को $p_2(x)$ के प्रत्येक पद से गुणा किया जाता है:

उदाहरण के लिए,
मान लें कि $p_1(x) = 1 + 2x$,
और $p_2(x) = 3 + 4x$ है।

तब,

जब इसे प्रोग्राम किया जाता है, तो इसे नेस्टेड लूप्स (nested loops) के रूप में लागू किया जाता है।

Copy
# Let A be array representing the coefficients of p1(x)
A = [a0, a1, ..., an]
# Let B be array representing the coefficients of p2(x)
B = [b0, b1, ..., bn]
# Let C be the array storing coefficients of p1(x).p2(x)

function multiply_polynomials(A, B):
    n = len(A)
    m = len(B)
    C = array of zeros of length (n + m - 1)

    for i from 0 to n - 1:
        for j from 0 to m - 1:
            C[i + j] += A[i] * B[j]
    return C

आपको परिणाम इस प्रकार मिलेगा:

बाहरी लूप के प्रत्येक $n$ इटरेशन (iterations) के लिए, आंतरिक लूप n बार चलता है (समान डिग्री $m=n$ मानते हुए), इस प्रकार n गुणा n, यानी $\mathcal{O}(n^2)$ का रनटाइम मिलता है।

अब हम यह देखना चाहते हैं कि क्या हम इसे ऑप्टिमाइज़ (optimize) कर सकते हैं और बेहतर कर सकते हैं। या सीधे शब्दों में कहें तो, क्या पॉलीनोमियल मल्टीप्लिकेशन को तेज़ बनाने का कोई तरीका है?

पॉलीनोमियल को निरूपित (Represent) करने के तरीके

पॉलीनोमियल को निरूपित करने के दो तरीके हैं: कोएफ़िशिएंट फॉर्म (coefficient form) और पॉइंट फॉर्म (point form)।

कोएफ़िशिएंट फॉर्म (Coefficient Form)

पॉलीनोमियल्स को आमतौर पर मोनोमियल बेसिस (monomial basis) या कोएफ़िशिएंट फॉर्म में व्यक्त किया जाता है, जिसका अर्थ है कि इसे वेरिएबल (variable) की घातों (powers) के लीनियर कॉम्बिनेशन (linear combination) के रूप में लिखा जाता है।

उदाहरण के लिए, जब $n$ डिग्री के पॉलीनोमियल को इस प्रकार व्यक्त किया जाता है

तो यह मोनोमियल बेसिस में व्यक्त होता है, क्योंकि यह अपने गुणांकों (coefficients), जो $a_0, a_1, a_2, .., a_x$ हैं, के आधार के रूप में $[1, x, x^2, …, x^n]$ का उपयोग कर रहा है।

इस निरूपण में, $p(x)$ के कोएफ़िशिएंट्स को एक वेक्टर (vector) या ऐरे (array) के रूप में लिखा जा सकता है, जैसे $[a_0, a_1, …, a_n]$, जहाँ पहला एलीमेंट (element) अचर पद (constant term) या $x^0$ के कोएफ़िशिएंट से मेल खाता है, जबकि अंतिम एलीमेंट $x^n$ के कोएफ़िशिएंट से मेल खाता है।

आपको ध्यान देना चाहिए कि हमने पहले जिस डिस्ट्रीब्यूटिव मल्टीप्लिकेशन (distributive multiplication) विधि (रनटाइम $\mathcal{O}(n^2)$) को देखा था, वह पॉलीनोमियल्स के कोएफ़िशिएंट फॉर्म पर लागू की गई थी।

पॉइंट (या वैल्यू) फॉर्म

पॉइंट (या वैल्यू) फॉर्म निरूपण इस तथ्य पर आधारित है कि $n$ डिग्री के प्रत्येक पॉलीनोमियल को इस पर स्थित $n+1$ अलग-अलग बिंदुओं के एक सेट द्वारा निरूपित किया जा सकता है।

उदाहरण के लिए, एक क्वाड्रेटिक पॉलीनोमियल (quadratic polynomial) (डिग्री $2$) पर विचार करें:

अब इस वक्र (curve) पर स्थित कोई भी $3$ बिंदु (चूँकि $n=2$) लें, मान लीजिए $(0,1)$, $(1,0)$ और $(2,3)$। हम कह सकते हैं कि ये $3$ बिंदु दिए गए पॉलीनोमियल का प्रतिनिधित्व करते हैं। वैकल्पिक रूप से, यदि हमें केवल ये बिंदु दिए गए हैं, तो उस जानकारी से पॉलीनोमियल $2x^2 -3x+1$ को पुनर्प्राप्त करना संभव है। यह काम कैसे करता है? या हम $n+1$ बिंदुओं के साथ $n$ डिग्री वाले पॉलीनोमियल को समतुल्य रूप से कैसे निरूपित करने में सक्षम हैं?

ऐसा इसलिए है क्योंकि:

$n+1$ अलग-अलग बिंदुओं के प्रत्येक सेट के लिए, अधिकतम $n$ डिग्री का एक अद्वितीय सबसे कम डिग्री (unique lowest degree) वाला पॉलीनोमियल मौजूद होता है जो उन सभी से होकर गुजरता है।

इस सबसे कम डिग्री वाले पॉलीनोमियल को Lagrange Polynomial कहा जाता है।

उदाहरण के लिए,
दिए गए दो बिंदुओं $(1, 2)$ और $(3, 4)$ से होकर गुजरने वाला डिग्री $1$ का एक अद्वितीय पॉलीनोमियल (एक रेखा) मौजूद है:

इसी प्रकार,
तीन बिंदुओं $(0, 1)$, $(1, 4)$, और $(2, 9)$ को देखते हुए, इन बिंदुओं से होकर गुजरने वाला डिग्री $2$ का Lagrange polynomial है:

बिंदुओं का एक सेट दिए जाने पर इस विशेष पॉलीनोमियल की गणना कैसे की जाती है, इस पर Lagrange interpolation के इस लेख में चर्चा की गई है।

Lagrange Polynomial की विशिष्टता (Uniqueness)

आपको यह ध्यान रखना चाहिए कि बिंदुओं के एक सेट के लिए, एक दी गई डिग्री के कई पॉलीनोमियल्स होते हैं जो उन सभी से होकर गुजरते हैं। लेकिन केवल सबसे कम डिग्री वाला पॉलीनोमियल ही अद्वितीय (unique) होता है।

उदाहरण के लिए, ऊपर दिए गए बिंदुओं $(1, 2)$ और $(3, 4)$ के उदाहरण में, इन दो बिंदुओं से होकर गुजरने वाले कई पॉलीनोमियल्स मौजूद हैं:
$x^2 -3x +4$ और $2x^2 -7x +7$, डिग्री $2$ (क्वाड्रेटिक) के कई पॉलीनोमियल्स में से दो हैं जो इन दो बिंदुओं से होकर गुजरते हैं।

इसी तरह, यदि आप डिग्री $3$ पर विचार करते हैं, तो बिंदुओं $(1,2)$ और $(3,4)$ से गुजरने वाले दो उदाहरण पॉलीनोमियल्स $x^3 -5x^2 +8x-2$ और $-x^{3}+4x^{2}-2x+1$ हैं।

लेकिन सबसे कम डिग्री के लिए, यहाँ $1$, सबसे कम डिग्री का केवल एक ही पॉलीनोमियल मौजूद है, और वह $p(x) = 1 + x$ है। यह अद्वितीय (unique) है, और डिग्री $1$ का कोई अन्य पॉलीनोमियल नहीं है जो इन दो दिए गए बिंदुओं से गुजर सके।

यह सबसे कम डिग्री कैसे निर्धारित की जाती है?

$n+1$ अलग-अलग बिंदुओं के प्रत्येक सेट के लिए, अधिकतम $n$ डिग्री का एक अद्वितीय पॉलीनोमियल होता है जो उनसे होकर गुजरता है। यदि कुछ बिंदु संरेख (collinear) हैं या किसी निचली डिग्री के पॉलीनोमियल पर स्थित हैं, तो अद्वितीय पॉलीनोमियल की डिग्री $n$ से कम होती है। इसलिए, हम “अधिकतम $n$” (at most $n$) शब्द का उपयोग उस मामले को कवर करने के लिए करते हैं जहाँ डिग्री बिल्कुल $n$ है, साथ ही उन मामलों में भी जहाँ डिग्री कम है।

उदाहरण के लिए,
बिंदुओं $(1,2),(2,4),$ और $(3,6)$ को देखते हुए, उनसे होकर गुजरने वाला सबसे कम डिग्री का पॉलीनोमियल $y=2x$ है। ऐसा इसलिए है क्योंकि बिंदु संरेख (collinear) हैं, यानी वे एक रेखा पर स्थित हैं। कोई भी जाँच कर सकता है कि उनमें से किसी भी जोड़े के बीच का ढलान (slope) समान है:

इसलिए, सबसे कम डिग्री $1$ है, और $y=2x$ अद्वितीय Lagrange polynomial है।

इसी तरह,
पाँच बिंदु $(-2,1), (-1,0), (0,1), (1,4), (2,9)$ दिए जाने पर, हम पाते हैं कि वे सभी एक पैराबोला (parabola) पर स्थित हैं जिसका समीकरण है

यह एक ऐसा मामला है जहाँ सभी दिए गए बिंदु कम डिग्री वाले पॉलीनोमियल पर स्थित हैं, यहाँ डिग्री $2$ है, और इस प्रकार Lagrange polynomial की डिग्री $2$ है, जो $n$ से कम है (यहाँ, $n=4$ है)।

सबसे कम डिग्री वाले पॉलीनोमियल की विशिष्टता (uniqueness) के प्रमाण के लिए अंत में परिशिष्ट (Appendix) देखें।

कोएफ़िशिएंट फॉर्म और पॉइंट फॉर्म के बीच रूपांतरण (Conversion)

चूँकि कोएफ़िशिएंट फॉर्म और पॉइंट फॉर्म समतुल्य (equivalent) हैं, हम आसानी से उनके बीच रूपांतरण कर सकते हैं जैसा कि हम अब दिखा रहे हैं।

इंटरपोलेशन (पॉइंट फॉर्म → कोएफ़िशिएंट फॉर्म)

पॉइंट फॉर्म से कोएफ़िशिएंट फॉर्म में रूपांतरण, जिसे इंटरपोलेशन (interpolation) कहा जाता है, उस सबसे कम डिग्री के पॉलीनोमियल की गणना करना है जो सभी दिए गए बिंदुओं से होकर गुजरता है। इसे करने की सबसे प्रसिद्ध विधियों में से एक Lagrange Interpolation का उपयोग करना है, जिसका उल्लेख हमने पहले किया था। यदि आप इससे परिचित नहीं हैं, तो आप इस लेख को पढ़ सकते हैं।

संक्षेप में, $(n+1)$ अलग-अलग बिंदुओं का एक सेट दिए जाने पर

हम Lagrange interpolation के सूत्र का उपयोग करके अधिकतम $n$ डिग्री वाले अद्वितीय सबसे कम डिग्री के पॉलीनोमियल $p(x)$ को ढूँढ सकते हैं, इस प्रकार कि:

आपको यह ध्यान में रखना चाहिए कि Lagrange interpolation का रनटाइम $\mathcal{O}(n^2)$ है।

इवैल्यूएशन (कोएफ़िशिएंट फॉर्म → पॉइंट फॉर्म)

कोएफ़िशिएंट फॉर्म से पॉइंट फॉर्म में रूपांतरण, जिसे इवैल्यूएशन (evaluation) कहा जाता है, में $x$ के मानों (values) पर पॉलीनोमियल का मूल्यांकन किया जाता है ताकि $y$ के संबंधित मान प्राप्त किए जा सकें, और इस प्रकार $(x_i, y_i)$ बिंदुओं का एक सेट मिलता है, जो पॉलीनोमियल का प्रतिनिधित्व करते हैं। इसे करने का एक सामान्य तरीका Horner’s rule का उपयोग करना है (जिस पर भविष्य के एक लेख में विस्तार से चर्चा की जाएगी)।

संक्षेप में, पॉलीनोमियल $p(x)$ के कोएफ़िशिएंट्स $[a_0, a_1, \dots, a_n]$ और एक मान $x_i$ दिए जाने पर, Horner’s Method $p(x_i)$ का मूल्यांकन इस प्रकार करता है:

यह विधि $x$ की कॉमन घातों (powers) को एक-एक करके फैक्टर आउट (factor out) करती है, जब तक कि सभी पदों को प्रोसेस न कर लिया जाए। इसे बेहतर ढंग से समझने के लिए आइए एक उदाहरण देखें।

दिए गए पॉलीनोमियल $p(x) = 2 + 3x + 5x^2 + x^3$ और एक मान $x = 2$ के साथ, हम समीक्षा करेंगे कि Horner’s rule $p(2)$ का मूल्यांकन कैसे करता है।

हम $p(x)$ को इस प्रकार फिर से लिख सकते हैं (जैसा कि ऊपर सामान्यीकृत अभिव्यक्ति में दिखाया गया है):

$x = 2$ प्रतिस्थापित (substitute) करने पर:

ध्यान दें कि कैसे इन चरणों में बारी-बारी से गुणा (multiplications) और जोड़ (additions) शामिल हैं। उपरोक्त गणना के चरण 1, 3 और 5 गुणा हैं, जबकि चरण 2, 4 और 6 जोड़ हैं। कुल मिलाकर, $n$ गुणा और $n$ जोड़ हैं (यहाँ $n=3$ है), जिससे कुल रनटाइम $\mathcal{O}(n)$ मिलता है। इस तरह Horner’s rule $x$ के दिए गए मान पर $n$ डिग्री के पॉलीनोमियल का $\mathcal{O}(n)$ में मूल्यांकन करता है।

इसलिए, $n+1$ अलग-अलग $x$-मानों पर पॉलीनोमियल का मूल्यांकन करने - इस नियम का उपयोग करके कोएफ़िशिएंट से पॉइंट फॉर्म में परिवर्तित करने - में $n$ गुना $n+1$, यानी $\mathcal{O}(n^2)$ का समय लगता है।

कोएफ़िशिएंट फॉर्म बनाम (VS) पॉइंट फॉर्म

हमने कहा कि पॉलीनोमियल का कोएफ़िशिएंट फॉर्म और पॉइंट फॉर्म समतुल्य हैं, और एक को दूसरे में परिवर्तित किया जा सकता है। यानी, जब किसी भी रूप में जोड़ (addition) और गुणा (multiplication) किया जाता है, तो अंतिम परिणामों में कोई अंतर नहीं होता है। आइए पहले जोड़ के एक उदाहरण के साथ इसकी जांच करें।

कोएफ़िशिएंट फॉर्म में जोड़ (Addition)

कोएफ़िशिएंट फॉर्म में दिए गए दो पॉलीनोमियल्स पर विचार करें,

या उनके संबंधित कोएफ़िशिएंट्स के ऐरे:

अब, दोनों पॉलीनोमियल्स को जोड़ने का मतलब है बस दोनों ऐरे को एलीमेंट-वाइज (element-wise) जोड़ना, और परिणामी कोएफ़िशिएंट ऐरे अंतिम पॉलीनोमियल का प्रतिनिधित्व करता है। आइए इसे सत्यापित (verify) करें:

या सीधे तौर पर, $[(1+4), (2+0),(3+1)] = [5,\ 2,\ 4]$

$n$ डिग्री के दो पॉलीनोमियल्स के लिए, हम योग (sum) का निरूपण प्राप्त करने के लिए $n+1$ बार जोड़ करते हैं। इसलिए, कोएफ़िशिएंट फॉर्म में जोड़ का रनटाइम $\mathcal{O}(n)$ है।

पॉइंट फॉर्म में जोड़

उन्हीं दो पॉलीनोमियल्स पर विचार करें,

सबसे पहले, हमें उन्हें कोएफ़िशिएंट फॉर्म से पॉइंट फॉर्म में बदलना होगा। चूँकि दोनों पॉलीनोमियल्स की डिग्री $2$ है, इसलिए उनके योग की डिग्री भी अधिकतम $2$ होगी। इसलिए, हमें योग को निरूपित करने के लिए तीन बिंदुओं (डिग्री प्लस एक: $n + 1$) की आवश्यकता है, जिसके लिए $p_1(x)$ और $p_2(x)$ प्रत्येक के $3$ मूल्यांकनों (evaluations) की आवश्यकता होती है।

आइए अपने बिंदु प्राप्त करने के लिए $x = 0, 1, 2$ पर $p_1(x)$ और $p_2(x)$ का मूल्यांकन करें।

नोट: हम सरलता के लिए केवल $x=0,1,2$ चुन रहे हैं। आप मूल्यांकन के लिए कोई अन्य $3$ बिंदु चुन सकते हैं।

• $p_1(0) = 1, \quad p_1(1)= 6, \quad p_1(2)=17$
• $p_2(0) = 4, \quad p_2(1)= 5, \quad p_2(2)=8$

अब, दो पॉलीनोमियल्स को जोड़ने के लिए संबंधित मूल्यांकनों को एलीमेंट-वाइज जोड़ना आवश्यक है, यानी:

• $p_{\text{sum}}(0) = (1+4) =5$
• $p_{\text{sum}}(1) = (6+5) =11$
• $p_{\text{sum}}(2) = (17+8) =25$

ये तीन बिंदु $(0, 5), (1, 11)$ और $(2, 25)$ हमें योग का पॉइंट निरूपण देते हैं। आइए हम सत्यापित करें कि क्या वे हमारे द्वारा पहले गणना किए गए पॉलीनोमियल को संतुष्ट करते हैं:

• $p_{\text{sum}}(0) = 5$
• $p_{\text{sum}}(1) = 5 + 2 + 4 = 11$
• $p_{\text{sum}}(2) = 5 + 4 + 16 = 25$

इसलिए, आप देखते हैं कि दोनों रूपों में जोड़ समान परिणाम देता है, या समान पॉलीनोमियल देता है, बस अलग-अलग तरीकों से निरूपित किया गया है।

पॉइंट फॉर्म जोड़ में, $n$ डिग्री के दो पॉलीनोमियल्स के लिए, उनमें से प्रत्येक का प्रतिनिधित्व करने वाले $n+1$ बिंदु होते हैं, और इस प्रकार हम योग के प्रतिनिधि बिंदुओं को प्राप्त करने के लिए $n+1$ बार एलीमेंट-वाइज जोड़ करते हैं। इसलिए, पॉइंट फॉर्म में जोड़ का रनटाइम $\mathcal{O}(n)$ है।

अब, आइए गुणा (multiplication) को भी करीब से देखें।

कोएफ़िशिएंट फॉर्म में गुणा

कोएफ़िशिएंट फॉर्म में दिए गए दो पॉलीनोमियल्स पर विचार करें:

या उनके संबंधित कोएफ़िशिएंट ऐरे:
$p_1 = [1,\ 2]$ और $p_2 = [3,\ 4]$

पहले चर्चा की गई डिस्ट्रीब्यूटिव विधि का उपयोग करके उन्हें गुणा करने पर प्राप्त होता है:

परिणामी पॉलीनोमियल $p_{\text{prod}}(x) = 3 + 10x + 8x^2$ है, जिसे कोएफ़िशिएंट ऐरे $[3,\ 10,\ 8]$ द्वारा दर्शाया गया है। कोएफ़िशिएंट फॉर्म मल्टीप्लिकेशन की डिस्ट्रीब्यूटिव विधि में $\mathcal{O}(n^2)$ का समय लगता है, जैसा कि हमने इस लेख की शुरुआत में देखा था।

पॉइंट फॉर्म में गुणा

अब हम उन्हीं पॉलीनोमियल्स पर विचार करते हैं और उन्हें उनके पॉइंट फॉर्म में परिवर्तित करते हैं।

चूँकि दोनों पॉलीनोमियल्स की डिग्री $1$ है, उनके गुणनफल (product) की डिग्री अधिकतम $2$ होगी, जिसका अर्थ है कि इसे निरूपित करने के लिए हमें $3$ बिंदुओं की आवश्यकता है, जिसके लिए $p_1(x)$ और $p_2(x)$ प्रत्येक के 3 मूल्यांकनों की आवश्यकता होती है।

तो, आइए $x = 0, 1, 2$ पर $p_1(x)$ और $p_2(x)$ का मूल्यांकन करें।

• $p_1(0) = 1,\quad p_1(1) = 3,\quad p_1(2) = 5$
• $p_2(0) = 3,\quad p_2(1) = 7,\quad p_2(2) = 11$

अब, उनके गुणनफल का प्रतिनिधित्व करने वाले बिंदु प्राप्त करने के लिए, हम मूल्यांकनों को एलीमेंट-वाइज गुणा करते हैं:

• $p_{\text{prod}}(0) = 1 \cdot 3 = 3$
• $p_{\text{prod}}(1) = 3 \cdot 7 = 21$
• $p_{\text{prod}}(2) = 5 \cdot 11 = 55$

तो तीन बिंदु $(0, 3), (1, 21)$ और $(2, 55)$ हमें परिणामी गुणनफल का पॉइंट निरूपण देते हैं।

आइए सत्यापित करें कि क्या वे उस पॉलीनोमियल गुणनफल को संतुष्ट करते हैं जो हमें पहले मिला था:

• $p_{\text{prod}}(0) = 3$
• $p_{\text{prod}}(1) = 3 + 10 + 8 = 21$
• $p_{\text{prod}}(2) = 3 + 20 + 32 = 55$

इसलिए, आप देख सकते हैं कि दोनों रूपों में गुणा करने पर समान पॉलीनोमियल मिलता है, बस अलग-अलग तरीकों से निरूपित किया गया है।

संक्षेप में, $n$ डिग्री के दो पॉलीनोमियल्स $p_1(x)$ और $p_2(x)$ के लिए, उनके गुणनफल की डिग्री अधिकतम $2n$ होगी, जिसका अर्थ है कि हमें इसे निरूपित करने के लिए $2n+1$ बिंदुओं की आवश्यकता है। इस प्रकार, हम उन्हें पॉइंट फॉर्म में बदलने के लिए $x$ के समान मानों पर प्रत्येक पॉलीनोमियल के लिए $2n+1$ मूल्यांकन करते हैं:

फिर हम इन दो सेटों को एलीमेंट-वाइज गुणा करके पॉइंट फॉर्म मल्टीप्लिकेशन करते हैं, जिसमें $2n+1$ बार गुणा किया जाता है, यानी $\mathcal{O}(n)$ का रनटाइम लगता है।

यह हमें वे $2n+1$ बिंदु देता है जो गुणनफल $p_1(x).p_2(x)$ का प्रतिनिधित्व करते हैं:

यहाँ ध्यान देने वाली अद्भुत बात यह है कि, जबकि कोएफ़िशिएंट और पॉइंट फॉर्म दोनों में जोड़ में समान समय $\mathcal{O}(n)$ लगता है, पॉइंट फॉर्म में गुणा कोएफ़िशिएंट फॉर्म की तुलना में काफी तेज़ है। पॉइंट फॉर्म में, हम $2n+1$ बार एलीमेंट-वाइज गुणा करते हैं, जिससे $\mathcal{O}(n)$ का रनटाइम मिलता है, जो कोएफ़िशिएंट फॉर्म गुणा के लिए आवश्यक $\mathcal{O}(n^2)$ से काफी बेहतर है!

हालाँकि, अभी भी एक समस्या है- हमने पॉइंट फॉर्म में और इसके विपरीत (vice versa) परिवर्तित करने के ओवरहेड (overhead) पर विचार नहीं किया है।

तो, आइए पॉइंट फॉर्म में गुणा करने की पूरी प्रक्रिया पर नज़र डालें, जिसमें तीन चरण शामिल हैं:

1. कोएफ़िशिएंट से पॉइंट फॉर्म में रूपांतरण
   हम गुणा किए जाने वाले $n$ डिग्री के दो पॉलीनोमियल्स का $x$ के $(2n+1)$ मानों पर मूल्यांकन करते हैं, ताकि प्रत्येक के लिए $(2n+1)$ मूल्यांकनों का एक सेट प्राप्त हो सके। Horner’s Method का उपयोग करने पर इसमें $\mathcal{O}(n^2)$ का समय लगता है।
2. पॉइंट फॉर्म निरूपण में एलीमेंट-वाइज गुणा
   हम इन दो सेटों को एलीमेंट-वाइज गुणा करते हैं ताकि $(2n+1)$ मूल्यांकन प्राप्त हो सकें जो उनके गुणनफल का पॉइंट फॉर्म निरूपण देते हैं। इसमें $\mathcal{O}(n)$ का समय लगता है।
3. पॉइंट से कोएफ़िशिएंट फॉर्म में रूपांतरण
   हम उस अद्वितीय सबसे कम डिग्री वाले पॉलीनोमियल (कोएफ़िशिएंट फॉर्म) की गणना करते हैं जो सभी परिणामी $(2n+1)$ बिंदुओं से होकर गुजरता है। Lagrange interpolation का उपयोग करने पर इसमें $\mathcal{O}(n^2)$ का समय लगता है।

इसलिए, उपरोक्त चरणों के लिए समग्र रनटाइम (overall runtime) है:

जो कि जहाँ से हमने शुरू किया था, उससे बेहतर नहीं है। इस प्रकार, हमें यह पता लगाने की आवश्यकता है कि क्या कोई ऑप्टिमाइज़ेशन इस प्रक्रिया को तेज़ बना सकता है।

रूपांतरण (Conversion) को ऑप्टिमाइज़ करना

ध्यान में रखने वाली मुख्य बात यह है कि कोएफ़िशिएंट फॉर्म में गुणा करने में $\mathcal{O}(n^2)$ समय लगता है, जबकि पॉइंट फॉर्म (एलीमेंट-वाइज) में गुणा करने में $\mathcal{O}(n)$ समय लगता है। इसलिए, यदि हम कोएफ़िशिएंट फॉर्म को पॉइंट फॉर्म में और इसके विपरीत (ऊपर बताए गए चरण 1 और 3) $\mathcal{O}(n^2)$ की तुलना में अधिक तेज़ी से परिवर्तित करने का कोई तरीका खोज सकें, तो हम गुणा को सब-क्वाड्रेटिक टाइम (sub-quadratic time) में चलाने के लिए ऑप्टिमाइज़ कर सकते हैं।

यह ध्यान रखना महत्वपूर्ण है कि हम पॉलीनोमियल जोड़ को ऑप्टिमाइज़ नहीं कर सकते हैं, क्योंकि कोएफ़िशिएंट फॉर्म और पॉइंट फॉर्म दोनों में जोड़ $\mathcal{O}(n)$ में चलता है।

तो अब आइए कुछ ऐसे तरीकों पर विचार करें जिनसे हम कोएफ़िशिएंट से पॉइंट फॉर्म में रूपांतरण को तेज़ बना सकते हैं।

क्या हो अगर हम एक ऐसा बिंदु जानते हों जिसका मूल्यांकन हमें कई संबंधित बिंदुओं के मान दे सके, जिससे हम बार-बार की जाने वाली गणनाओं से बच सकें?

उदाहरण के लिए, यदि हमारे पास एक सममित ग्राफ (symmetric graph) वाला पॉलीनोमियल है, तो एक बिंदु का मूल्यांकन हमें उसके संबंधित सममित बिंदु के लिए भी मूल्यांकन बता देगा।

पॉलीनोमियल $p(x)= x^2$ पर विचार करें।
ध्यान दें कि कैसे,

या, अधिक सरलता से, ध्यान दें कि कैसे सभी $x_i$ के लिए,

यह केवल $p(x)=x^2$ के लिए ही सही नहीं है, बल्कि उन सभी पॉलीनोमियल्स के लिए सामान्यीकृत (generalizes) होता है जिनमें केवल सम घात (even powered) वाले कोएफ़िशिएंट्स होते हैं, जिन्हें ईवन पॉलीनोमियल्स (even polynomials) भी कहा जाता है।

उदाहरण के लिए, ईवन पॉलीनोमियल (जिसमें $x$ की सम घातों वाले ही पद हों) पर विचार करें:

ऊपर दिए गए ग्राफ में, यह देखना आसान है कि

दृश्य रूप से (Visually) कहें, तो ईवन पॉलीनोमियल्स के ग्राफ $y$-अक्ष (y-axis) के ओर मिरर (mirrored) होते हैं, और वे किसी भी दिए गए $x$ के धनात्मक (positive) और ऋणात्मक (negative) दोनों मानों के लिए समान $y$ का मूल्यांकन करते हैं।

उन ऑड (odd) पॉलीनोमियल्स के बारे में क्या जिनमें केवल विषम घात (odd powered) वाले कोएफ़िशिएंट्स होते हैं?
$p(x) = x^3$ पर विचार करें।
ध्यान दें कि कैसे

ऊपर दिए गए ग्राफ में, ध्यान दें कि कैसे, सभी $x_i$ के लिए,

फिर से, यह केवल $p(x)=x^3$ के लिए ही सच नहीं है, बल्कि सभी ऑड पॉलीनोमियल्स के लिए सामान्यीकृत होता है, यानी वे पॉलीनोमियल्स जिनमें $x$ की विषम घात वाले ही पद होते हैं। उदाहरण के लिए, इस पॉलीनोमियल पर विचार करें

ऊपर दिए गए ग्राफ में, ध्यान दें कि

दृश्य रूप से, सभी ऑड पॉलीनोमियल्स के ग्राफ मूल बिंदु (origin) के बारे में सममित (symmetric) होते हैं, जो उपरोक्त समानता (equality) को उन सभी के लिए सत्य बनाता है।

अब आप देख सकते हैं कि कुछ बिंदुओं का मूल्यांकन करने के बाद, हम बिना किसी अतिरिक्त गणना के अन्य बिंदुओं पर मूल्यांकन प्राप्त कर सकते हैं। उदाहरण के लिए, ऊपर दिए गए उदाहरणों में, ईवन और ऑड पॉलीनोमियल्स के लिए, $p(x)$ के लिए मूल्यांकन जानने से हमें $p(-x)$ के लिए भी मूल्यांकन मिल जाता है।

हम पॉलीनोमियल मल्टीप्लिकेशन को तेज़ बनाने के लिए इस तथ्य का लाभ उठा सकते हैं, जो बिल्कुल वही है जो Number Theoretic Transform (NTT) नामक एक शानदार एल्गोरिथ्म हमें करने की अनुमति देता है। NTT कुछ बिंदुओं की समरूपता (symmetries) के गुणों का पुनरावर्ती (recursively) उपयोग करके $\mathcal{O}(n \log n)$ में मूल्यांकन और इंटरपोलेशन को सक्षम बनाता है, जिससे रूपांतरण सब-क्वाड्रेटिक बन जाता है।

लेकिन चूंकि NTT एक सीमित क्षेत्र (finite field) पर काम करता है, इसलिए हमारे पास काम करने के लिए $x$ के कोई ऋणात्मक (negative) मान नहीं हैं। यहीं पर मल्टीप्लिकेटिव सबग्रुप्स (multiplicative subgroups), साइक्लिसिटी (cyclicity) और रूट्स ऑफ़ यूनिटी (roots of unity) की अवधारणाएं (concepts) सामने आती हैं। ये अवधारणाएँ हमें पॉलीनोमियल मल्टीप्लिकेशन को अधिक कुशलता से करने के लिए सीमित क्षेत्रों (finite fields) में मौजूद समरूपता (symmetries) का लाभ उठाने की अनुमति देंगी। हम आने वाले लेखों में विस्तार से जानेंगे कि NTT कैसे काम करता है।

परिशिष्ट (Appendix)

सबसे कम डिग्री वाले पॉलीनोमियल की विशिष्टता (Uniqueness) का प्रमाण

हम दिखाते हैं कि यदि समान डिग्री के दो पॉलीनोमियल्स $p(x)$ और $q(x)$ हैं जो बिंदुओं के एक सेट को इंटरपोलेट करते हैं, तो एक पॉलीनोमियल $r(x)$ इस तरह मौजूद होना चाहिए कि $r(x) = p(x)-q(x)$ हो।

फिर हम दिखाएंगे कि $r(x)$ के लिए एकमात्र संभव समाधान $r(x) = 0$ है, अन्यथा हमारे पास एक ऐसा पॉलीनोमियल बचता है जिसकी जड़ों (roots) की संख्या उसकी डिग्री से अधिक है, जिसे हम दिखाते हैं कि यह असंभव है। आइए अब इन चरणों को विस्तार से देखें।

मान लेते हैं कि सबसे कम डिग्री का Lagrange polynomial अद्वितीय नहीं है। तो सबसे कम डिग्री के कम से कम दो अलग-अलग पॉलीनोमियल्स हैं जो सभी दिए गए $n+1$ बिंदुओं से होकर गुजरते हैं। मान लें कि ये दो पॉलीनोमियल्स $p(x)$ और $q(x)$ हैं। अब, पॉलीनोमियल $r(x)$ को $p(x)$ और $q(x)$ के बीच के अंतर के रूप में परिभाषित करें।

अब, यदि हम दिखाते हैं कि $x$ के सभी मानों के लिए $r(x)$ $0$ है, तो हम यह दिखा चुके होंगे कि $p(x)$, $q(x)$ के बराबर है, और इसलिए Lagrange polynomial अद्वितीय है।

चूँकि $p(x)$ और $q(x)$ दोनों की डिग्री अधिकतम $n$ है, यह सरल बीजगणितीय घटाव (algebraic subtraction) से स्पष्ट होता है कि $r(x)$ की डिग्री भी अधिकतम $n$ होनी चाहिए।
इसके अलावा, चूंकि $p(x)$ और $q(x)$ दोनों एक ही $n+1$ बिंदुओं से होकर गुजरते हैं, वे प्रत्येक $x$-मान के लिए समान $y$-मान का मूल्यांकन करेंगे।

नोट: ग्राफ़िक रूप से, जब दो अलग-अलग पॉलीनोमियल्स किसी दिए गए $x$ के लिए समान $y$-मान का मूल्यांकन करते हैं, तो इसका मतलब है कि वे उस बिंदु पर एक-दूसरे को काटते (intersect) हैं। उदाहरण के लिए:

$x=2$ पर, दोनों $y=4$ देते हैं, इसलिए वे बिंदु $(2,4)$ पर प्रतिच्छेद (intersect) करते हैं। इस मामले में, हम अलग-अलग पॉलीनोमियल्स से निपट रहे हैं। किसी दिए गए $x$ के लिए समान $y$ होने की एक और संभावना यह है कि वे वास्तव में एक ही पॉलीनोमियल हैं! उस स्थिति में, उनके पास $x$ के सभी मानों के लिए समान $y$ होगा, न कि केवल $x$ के कुछ विशेष मानों के लिए।

$p(x)$ और $q(x)$ के मामले में, वे $x$ के कम से कम n + 1 अलग-अलग मानों के लिए समान हैं। इसे गणितीय रूप से इस प्रकार व्यक्त किया जा सकता है:

इसलिए, सभी $n+1$ बिंदुओं पर $p(x)$ और $q(x)$ के बीच का अंतर शून्य होगा। अर्थात,

इसलिए, $n+1$ बिंदुओं पर $r(x)$ का मूल्यांकन शून्य होता है, जिसका अर्थ है कि यह एक ज़ीरो पॉलीनोमियल (zero polynomial) है। आइए अधिक स्पष्ट रूप से देखें कि ऐसा क्यों है।

एक ज़ीरो पॉलीनोमियल वह होता है जो $x$ के सभी मानों के लिए शून्य का मूल्यांकन करता है। ज़ीरो पॉलीनोमियल का सबसे सरल उदाहरण है:

इसे देखने का एक और तरीका यह है कि, यदि पॉलीनोमियल मूल्यांकन का हमारा डोमेन (domain) - उन बिंदुओं का सेट जिन पर पॉलीनोमियल का मूल्यांकन किया जा सकता है - मान लीजिए, $S=\{x_0, x_1 \cdots, x_{n-1}\}$ है, तो इस डोमेन के लिए ज़ीरो पॉलीनोमियल यह हो सकता है:

क्योंकि,

हमारे पास डोमेन $S$ के लिए कई और ज़ीरो पॉलीनोमियल्स हो सकते हैं जैसे:

ध्यान दें कि $f_1(x), f_2(x)$ और $f_3(x)$ में से प्रत्येक डोमेन $S$ के लिए शून्य का मूल्यांकन करता है, और इस प्रकार यह एक ज़ीरो पॉलीनोमियल है। हमारे पास ऐसे कई और हो सकते हैं। सबसे प्रारंभिक (primitive) $f_3(x)=0$ है, यानी स्वयं अचर (constant) शून्य।

नोट: यदि डोमेन $S$ को सभी वास्तविक संख्याओं (real numbers) के सेट के रूप में लिया जाता है, तो हमारे पास केवल एक ही ज़ीरो पॉलीनोमियल हो सकता है और वह है $f(x)=0$, क्योंकि कोई अन्य पॉलीनोमियल सभी वास्तविक संख्याओं के लिए शून्य का मूल्यांकन नहीं करेगा।

अब हमारे द्वारा देखे गए प्रत्येक उदाहरण ज़ीरो पॉलीनोमियल्स के लिए जड़ों (roots) की संख्या और डिग्री (degree) का निरीक्षण करें।

किसी पॉलीनोमियल की जड़ें डोमेन में वे मान होती हैं जिनके लिए पॉलीनोमियल शून्य का मूल्यांकन करता है, जबकि पॉलीनोमियल की डिग्री वेरिएबल की उच्चतम घात होती है, जैसा कि आप अच्छी तरह जानते हैं।

• $f_1(x):$ जड़ें- $n$, डिग्री- $n$
• $f_2(x):$ जड़ें- $n$, डिग्री- $2n$
• $f_3(x):$ जड़ें- $n$, डिग्री- $0$

वे सभी $S$ पर शून्य का मूल्यांकन करते हैं; इसलिए, जड़ों की संख्या $n$ है, जबकि $p(x)$, जिसकी डिग्री $n$ है, को संशोधित करके डिग्री को बदला जा सकता है।

यह भी ध्यान दें कि $f_3(x)=0$ में जड़ों की संख्या उसकी डिग्री से अधिक है। यह केवल ज़ीरो पॉलीनोमियल के मामले में ही संभव है, विशेष रूप से प्रारंभिक (primitive) वाले $f_3(x)=0$ के मामले में। अन्यथा, जड़ों की संख्या हमेशा डिग्री से कम या उसके बराबर होती है।

$n$ डिग्री के एक नॉन-ज़ीरो पॉलीनोमियल (non-zero polynomial) पर विचार करें; इसकी अधिकतम $n$ जड़ें हो सकती हैं (या $x$-अक्ष के साथ प्रतिच्छेदन/intersections)। प्रारंभिक ज़ीरो पॉलीनोमियल ही एकमात्र अपवाद (exception) है, क्योंकि इसकी जड़ें इसकी डिग्री से अधिक होती हैं।

उदाहरण के लिए,
डिग्री $2$ का एक क्वाड्रेटिक समीकरण, जैसे $q(x)=x^2-3x+2$, के दो रूट होते हैं, यानी $x=1$ और $x=2$।

एक क्वाड्रेटिक समीकरण के दो से अधिक रूट होने के लिए, यह शून्य के बराबर होना चाहिए, यानी $q(x)=0$।

अब, अपने तर्क (argument) पर वापस आते हैं: चूंकि $r(x)$ $n+1$ बिंदुओं पर शून्य का मूल्यांकन करता है, इसलिए इसके कम से कम $n+1$ रूट होने चाहिए, जो इसकी डिग्री $n$ से अधिक है। इसलिए $r(x)$ शून्य के बराबर होना चाहिए।

इसका तात्पर्य है कि $p(x)=q(x)$ है, जिसका अर्थ है कि वे एक ही पॉलीनोमियल हैं। इसलिए, $n+1$ अलग-अलग बिंदुओं के सेट को इंटरपोलेट करने वाला सबसे कम डिग्री का पॉलीनोमियल अद्वितीय (unique) होता है।