Number Theoretic Transform (NTT) एक एल्गोरिथम है जो एक finite field में एक polynomial को n मानों पर O(n log n) समय में evaluate करता है।
आमतौर पर, एक polynomial को evaluate करने में O(n) समय लगता है, इसलिए polynomial को n बार evaluate करने में O(n²) समय लगेगा।
NTT polynomial evaluations के बीच काम का पुन: उपयोग (reusing) करके रनटाइम को कम करता है। NTT एल्गोरिथम polynomial गुणा (multiplication) और भाग (division) को भी तेज़ करने में सक्षम बनाता है। यह ट्यूटोरियल सीरीज़ सिखाती है कि NTT एल्गोरिथम कैसे काम करता है और यह क्यों काम करता है। यह लेख NTT ट्यूटोरियल सीरीज़ का परिचय देता है और अंत में बाकी ट्यूटोरियल्स के लिए विषय सूची (table of contents) प्रदान करता है।
यह एक Fast Fourier Transform ट्यूटोरियल सीरीज़ भी है
हमने इस बात पर काफी विचार किया कि इसे “Fast Fourier Transform ट्यूटोरियल सीरीज़” कहा जाए या “Number Theoretic Transform ट्यूटोरियल सीरीज़”। कार्यात्मक रूप से (Functionally), ये एल्गोरिदम बिल्कुल समान (identical) हैं — एकमात्र अंतर यह है कि हम finite field का उपयोग करते हैं या complex numbers का।
जो पाठक यह सीखने में रुचि रखते हैं कि Fast Fourier Transform कैसे काम करता है, वे भी इस सीरीज़ को फॉलो कर सकते हैं और दोनों को समझ सकते हैं।
इस NTT ट्यूटोरियल सीरीज़ के बारे में
हालांकि NTT एल्गोरिथम का संक्षेप में वर्णन करना संभव है (अगला भाग देखें), यह समझना कि यह कैसे काम करता है आश्चर्यजनक रूप से कठिन है। यह ट्यूटोरियल सीरीज़:
- उन गणितीय ट्रिक्स (mathematical tricks) को क्रमिक रूप से पेश करती है जिन पर NTT निर्भर करता है
- पाठकों को मूल सिद्धांतों (first principles) से NTT की फिर से खोज करने की यात्रा पर मार्गदर्शन करती है
- जो पाठक गहराई में जाना चाहते हैं, उनके लिए रास्ते में सटीकता के वैकल्पिक गणितीय प्रमाण (mathematical proofs) प्रदान करती है
NTT एल्गोरिथम काफी छोटा है और इसे AI द्वारा एक ही बार (one shot) में प्रॉम्प्ट किया जा सकता है। नीचे Gemini के आउटपुट पर विचार करें। अभी कोड को समझने की चिंता न करें; अभी के लिए, बस यह ध्यान दें कि यह कितना छोटा है। हम इस पूरी सीरीज़ में समझेंगे कि यह क्या कर रहा है।
Prompt: create the NTT algorithm in Python. Show it evaluates the polynomial f(x) = x^2 + 2x + 3 correctly. Use the finite field order 17.
यहाँ परिणामी कोड दिया गया है (पढ़ने में आसानी बनाने और जगह बचाने के लिए बहुत मामूली संपादन के साथ)।
def ntt(a, omega, q):
"""
Performs the Number Theoretic Transform (NTT) on list 'a'
over the finite field modulo 'q' using primitive root 'omega'.
"""
N = len(a)
if N == 1:
return a
# Split into even and odd coefficients
a_even = ntt(a[0::2], (omega * omega) % q, q)
a_odd = ntt(a[1::2], (omega * omega) % q, q)
y = [0] * N
w = 1
for i in range(N // 2):
w_a_odd = (w * a_odd[i]) % q
y[i] = (a_even[i] + w_a_odd) % q
y[i + N // 2] = (a_even[i] - w_a_odd) % q
w = (w * omega) % q
return y
def direct_evaluate(x, q):
"""Directly evaluates f(x) = x^2 + 2x + 3 mod q"""
return (x**2 + 2 * x + 3) % q
# --- Configuration ---
q = 17 # Finite field order
omega = 4 # Primitive 4th root of unity mod 17
# f(x) = 3 + 2x + 1x^2 + 0x^3
coefficients = [3, 2, 1, 0]
# 1. Run NTT
ntt_result = ntt(coefficients, omega, q)
# 2. Run Direct Evaluation for Verification
evaluation_points = [(omega**k) % q for k in range(4)]
direct_result = [direct_evaluate(x, q) for x in evaluation_points]
assert (
ntt_result == direct_result
), "Mismatch between NTT and direct evaluation!"
print("\nSuccess! The NTT evaluated the polynomial correctly.")
खाली लाइनों को छोड़कर, लगभग सारा काम कोड की इन 14 लाइनों में किया जा रहा है:
N = len(a)
if N == 1:
return a
# Split into even and odd coefficients
a_even = ntt(a[0::2], (omega * omega) % q, q)
a_odd = ntt(a[1::2], (omega * omega) % q, q)
y = [0] * N
w = 1
for i in range(N // 2):
w_a_odd = (w * a_odd[i]) % q
y[i] = (a_even[i] + w_a_odd) % q
y[i + N // 2] = (a_even[i] - w_a_odd) % q
w = (w * omega) % q
return y
हालाँकि, एल्गोरिथम का संक्षिप्त रूप इसकी जटिलता को छुपाता है।
FFT / NTT पर अधिकांश ट्यूटोरियल कहाँ गलती करते हैं
उपरोक्त कोड को सरसरी तौर पर देखने पर, पाठक देख सकते हैं कि NTT एल्गोरिथम, अपने मूल में, polynomial coefficients को सम (even) और विषम (odd) भागों में विभाजित करने पर निर्भर करता है, और इस विषय पर कई ट्यूटोरियल (साथ ही AI स्पष्टीकरण) even-odd विभाजन के नज़रिए से NTT को समझाने का प्रयास करते हैं।
हालाँकि, जैसा कि हम जानेंगे, coefficients को उनके सम या विषम होने के आधार पर विभाजित करना उन गहरी गणितीय ट्रिक्स के लिए प्रासंगिक (incidental) है जिन पर NTT निर्भर करता है।
मौलिक रूप से, NTT की फिर से खोज करने के लिए इस प्रश्न का उत्तर देने की आवश्यकता है कि “polynomial evaluations के बीच गणनाओं (calculations) का पुन: उपयोग करना क्यों संभव है?” न कि “even और odd विभाजन के बारे में ऐसा क्या खास है?”
उदाहरण के लिए, मान लीजिए कि हम बिंदुओं और पर polynomial को evaluate करते हैं। ऊपरी तौर पर देखने पर, हमें इस बारे में कुछ नहीं बताता कि किसके बराबर होना चाहिए। उदाहरण के लिए, का वर्ग (squaring) करने से आपको इस बारे में कोई जानकारी नहीं मिलती है कि का वर्ग क्या है।
यह तुरंत स्पष्ट नहीं होता है कि polynomials को evaluate करना से तेज़ हो सकता है।
इस सीरीज़ में हमारा लक्ष्य मूल सिद्धांतों (first principles) से यह फिर से खोजना है कि कैसे एक बिंदु पर polynomial को evaluate करने से दूसरे बिंदु पर इसे evaluate करने के लिए आवश्यक काम कम हो जाता है।
पाठक को नीचे दिए गए क्रम में इस सीरीज़ से गुज़रना चाहिए। प्रत्येक अध्याय एक छोटे, समझने में आसान उप-अवधारणा (subconcept) का परिचय देता है जिसे आत्मसात किया जाना चाहिए क्योंकि बाद के अध्याय एक-दूसरे पर आधारित होते हैं।
इस ट्यूटोरियल सीरीज़ के लिए प्रेरणा (Motivation)
कोई सोच सकता है कि, यह देखते हुए कि आधुनिक इंजीनियरिंग के लिए NTT एल्गोरिथम कितना मौलिक है, ऐसे बहुत सारे ट्यूटोरियल होंगे जो इसके काम करने के तरीके का वर्णन करने से आगे जाते हैं और समझाते हैं कि यह क्यों काम करता है। हालाँकि, हमने मौजूदा स्पष्टीकरणों को अपर्याप्त पाया, इसलिए हमने इसे बनाया। आपको इस सीरीज़ में कई नए दृष्टिकोण मिलेंगे जो आपको कहीं और नहीं मिलेंगे। हमने नए, सरल मानसिक मॉडल (mental models) विकसित करने का प्रयास किया है, न कि मौजूदा सामग्री को संक्षेप में प्रस्तुत करने का।
इसके अलावा, NTT एल्गोरिथम संरचनात्मक रूप से FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) को दर्शाता है। यह गहराई से जानना कि NTT एल्गोरिथम क्यों काम करता है, FRI एल्गोरिथम को सीखना आसान बनाता है।
वास्तव में, FRI में “Fast” शब्द इस तथ्य से आता है कि FRI एल्गोरिथम काफी हद तक Fast Fourier Transform (NTT एल्गोरिथम) के समान है।
इस ट्यूटोरियल सीरीज़ के लिए पूर्वापेक्षाएँ (Prerequisites)
हम finite fields and modular arithmetic के साथ बुनियादी परिचितता की उम्मीद करते हैं। हम इस सीरीज़ में एक “subgroup” को परिभाषित करेंगे, इसलिए पाठक को पहले से ही एक group की अवधारणा से परिचित होना चाहिए। ZK Book के पहले छह अध्याय पढ़ना पर्याप्त होना चाहिए।
हम linear algebra, जैसे कि matrix inverses के बुनियादी ज्ञान की भी उम्मीद करते हैं।
abstract algebra की गहरी समझ की आवश्यकता नहीं है। हमें केवल ऊपर सूचीबद्ध बुनियादी शब्दावली के साथ प्रवाह (fluency) की आवश्यकता है।
abstract algebra के प्रति एक प्रेरित दृष्टिकोण (A motivated approach to abstract algebra)
कई पाठकों को finite field में subgroups और roots of unity के बारे में हमारी व्याख्या एक सामान्य गणितीय व्याख्या की तुलना में अधिक आकर्षक लगेगी क्योंकि हम इन अवधारणाओं को उन संदर्भों में प्रस्तुत करते हैं जहाँ वे “वास्तविक दुनिया (in the real world)” में दिखाई देते हैं।
हम कवर किए गए abstract algebra विषयों की पूरी व्याख्या देने का प्रयास नहीं करते हैं, केवल उन हिस्सों का जो:
- वास्तविक दुनिया में दिखाई देते हैं (इस मामले में, NTT एल्गोरिथम)
- वास्तविक दुनिया के अनुप्रयोगों (applications) को समझने के लिए आवश्यक शर्तें (prerequisites) हैं
- वास्तविक दुनिया की अवधारणाओं के लिए सरल फ्रेमवर्क प्रदान करते हैं
बाकी सभी चीज़ों को हम बेदर्दी से हटा देते हैं या अधिक गणितीय झुकाव वाले पाठकों के लिए वैकल्पिक (optional) पढ़ने की सामग्री के रूप में चिह्नित करते हैं। हमने यह सीरीज़ सॉफ्टवेयर इंजीनियरों के लिए लिखी है, गणितज्ञों के लिए नहीं।
अशुद्धियां और फीडबैक (Errata and Feedback)
यदि आपको पाठ में कोई गलती या समस्या दिखाई देती है, तो कृपया https://github.com/RareSkills/zk-book/tree/prod पर एक issue या pull request ओपन करें।
विषय सूची (Table of Contents)
Polynomial Multiplication in Point Form. यह अध्याय सब-क् क्वाड्रेटिक (sub-quadratic) समय में एक polynomial को evaluate करने की आवश्यकता को प्रेरित करता है।
Multiplicative Subgroups. Subgroups, roots of unity को समझने के लिए एक पूर्वापेक्षा (prerequisite) हैं।
Fundamental Theorem of Cyclic Groups. Roots of unity एक cyclic subgroup बनाते हैं, और यह प्रमेय (theorem) दर्शाता है कि वे कैसे व्यवहार करते हैं।
Roots of Unity in Finite Fields. NTT एल्गोरिथम केवल तभी काम करता है जब हम “roots of unity” पर एक polynomial को evaluate करते हैं, जिसे यह अध्याय प्रस्तुत करता है। जो लोग Fast Fourier Transform को समझने के लिए इस सीरीज़ को पढ़ रहे हैं, उनके लिए finite field में roots of unity बिल्कुल complex numbers में roots of unity के समान व्यवहार करते हैं, यानी ।
Roots of Unity Congruent to -1. चूँकि roots of unity एक subgroup बनाते हैं, इसलिए प्रत्येक root of unity का एक inverse होता है (जिसकी गणना कुशलतापूर्वक की जा सकती है)।
Visualizing Roots of Unity on the Unit Circle. यह अध्याय दिखाता है कि एक unit circle पर finite field में roots of unity को कैसे प्लॉट किया जाए और roots of unity के subgroup में additive inverses की आसानी से कैसे कल्पना की जाए।
Vandermonde Matrices. Vandermonde matrices, polynomial evaluation को polynomial coefficients और उन बिंदुओं के गुणन (multiplication) के रूप में दर्शाते हैं जिन पर उनका मूल्यांकन किया जाता है।
Squaring Roots of Unity. यह अध्याय Image Preservation Theorem अध्याय के लिए एक पूर्वापेक्षा (prerequisite) है।
Roots of Unity Raised to k/2. यह अध्याय (भी) Image Preservation Theorem अध्याय के लिए एक पूर्वापेक्षा है।
Square Roots of Roots of Unity. यह अध्याय Image Preservation Theorem अध्याय के लिए (एक और) पूर्वापेक्षा है।
Image Preservation Theorem. अजीब बात है कि जिस मुख्य विचार पर NTT निर्भर करता है, उसका कोई औपचारिक नाम नहीं है, इसलिए हमने “image preservation theorem” नाम का आविष्कार किया। यह अध्याय इस विचार का परिचय देता है कि एक छोटे डोमेन पर polynomial को evaluate करने से बड़े डोमेन में गणना के पुन: उपयोग (computation reuse) की अनुमति मिलती है।
Square Root Multivalued Functions. एक multivalued function एकल मान के बजाय मानों का एक सेट (set of values) लौटाता है। यह हमें “एक की कीमत पर दो मूल्यांकन (two evaluations for the price of one)” देता है।
NTT By Hand. NTT एल्गोरिथम के कई कार्यान्वयन संस्करण (implementation variants) हैं। हमने अपना स्वयं का कार्यान्वयन बनाया है जो पेन और पेपर पर गणना करने के लिए उपयुक्त है ताकि शिक्षार्थी एल्गोरिथम का गहराई से अनुभव कर सकें।
FFT Friendly Finite Fields. यह लेख उन finite fields को सूचीबद्ध करता है जिनका उपयोग व्यवहार में NTT और zero knowledge proofs के लिए किया जाता है।
Orthogonality of the Roots of Unity. यह अध्याय Inverse Number Theoretic Transform और Inverse of a Vandermonde Matrix के लिए एक पूर्वापेक्षा है।
Inverse Number Theoretic Transform. Inverse Number Theoretic Transform, Number Theoretic Transform को “अन्डू (undoes)” करता है। यह बिंदुओं का एक सेट लेता है और coefficient फॉर्म में एक polynomial लौटाता है।
Inverse of a Vandermonde Matrix. यह अध्याय सिद्ध करता है कि एक Vandermonde matrix का matrix inverse एक अन्य Vandermonde matrix होता है। यह तथ्य Inverse Number Theoretic Transform एल्गोरिथम की सटीकता को साबित करना बहुत आसान बना देता है।
Inverse Number Theoretic Transform by Hand. पिछले तीन अध्याय यह स्थापित करते हैं कि एक Vandermonde matrix का inverse भी एक Vandermonde matrix होता है। इसलिए, हम Number Theoretic Transform एल्गोरिथम को केवल एक छोटे से बदलाव के साथ Inverse Number Theoretic Transform के रूप में फिर से उपयोग कर सकते हैं।
Convolution Theorem (वैकल्पिक)। Convolution theorem हमें एक सुंदर प्रमाण बनाने की अनुमति देता है कि प्रारंभिक polynomial multiplication, NTT करने, pointwise multiplication करने और फिर INTT करने के समतुल्य (equivalent) है।
Signal Flow Graphs. NTT को अक्सर signal flow graphs के साथ मॉडल किया जाता है। यह अध्याय इस विषय पर एक त्वरित पुनश्चर्या (quick refresher) है।
Signal Flow Graphs in NTT. यहाँ, हम NTT by Hand में प्रस्तुत एल्गोरिथम के लिए signal flow graph बनाते हैं। परिणामी ग्राफ का उपयोग एल्गोरिथम के बारे में तर्क (reason) करने के लिए किया जाएगा।
Decimation in Time and Decimation in Frequency. NTT की मैन्युअल रूप से गणना करने के लिए हमने जिस एल्गोरिथम का उपयोग किया है, वह कार्यात्मक रूप से (functionally) उत्पादन (production) NTT एल्गोरिथम कार्यान्वयन के समतुल्य है, लेकिन इसमें कुछ छोटे बदलाव (variations) हैं। इस अध्याय में, हम उत्पादन में उपयोग किए जाने वाले वास्तविक NTT कार्यान्वयन दिखाते हैं।
Radix-2 DIT Algorithm in Python. NTT के कई एल्गोरिथम संस्करण हैं, जिनमें से दो DIF (Decimation in Frequency) और DIT (Decimation in Time) हैं। पहले वाले को पिछले अध्याय में समझाया गया था; इस अध्याय में, हम बाद वाले की व्याख्या करते हैं।
NTT, INTT, and Fast Polynomial Multiplication in Python. यहाँ, हम Python में NTT और INTT दोनों को लागू करते हैं और O(n log n) समय में polynomial multiplication करने के लिए इन एल्गोरिदम का उपयोग करते हैं।
यह लेख हमारी ZK Book में Number Theoretic Transform पर आधारित एक सीरीज़ का हिस्सा है