यह लेख एक सीरीज़ का तीसरा भाग है। हम ज़ीरो-नॉलेज प्रूफ़्स के लिए सर्किट्स के संदर्भ में फाइनाइट फील्ड्स (finite fields) को प्रस्तुत करते हैं। पिछले अध्याय P vs NP and its Application to Zero Knowledge Proofs और Arithmetic Circuits हैं।

एरिथमेटिक सर्किट पर पिछले अध्याय में, हमने एक सीमा की ओर इशारा किया था कि हम संख्या $2/3$ को एनकोड नहीं कर सकते क्योंकि इसे बाइनरी का उपयोग करके सटीक रूप से दर्शाया नहीं जा सकता है। हमने यह भी बताया था कि हमारे पास स्पष्ट रूप से ओवरफ़्लो (overflow) को संभालने का कोई तरीका नहीं था।

इन दोनों समस्याओं को अंकगणित के एक प्रकार के साथ सहजता से नियंत्रित किया जा सकता है, जो सामान्य क्रिप्टोग्राफी में लोकप्रिय है, जिसे फाइनाइट फील्ड्स कहा जाता है।

फाइनाइट फील्ड्स (Finite fields)

एक अभाज्य संख्या (prime number) p दिए जाने पर, हम पूर्णांकों के सेट $\set{0, 1, 2, …, p-1}$ को लेकर p तत्वों (elements) के साथ एक फाइनाइट फील्ड बना सकते हैं और जोड़ (addition) तथा गुणा (multiplication) को मॉड्यूलो (modulo) $p$ के रूप में परिभाषित कर सकते हैं। हम शुरुआत में खुद को उन फील्ड्स तक सीमित रखेंगे जहां तत्वों की संख्या एक अभाज्य संख्या है।

उदाहरण के लिए, यदि अभाज्य संख्या $p$, $7$ है, तो फाइनाइट फील्ड में तत्व $\set{0, 1, 2, 3, 4, 5, 6}$ हैं। इस सीमा के बाहर की किसी भी संख्या ($≥ p$ या $< 0$) को हमेशा मॉड्यूलो का उपयोग करके इस सीमा में एक “समकक्ष” (equivalent) संख्या पर मैप किया जाता है। “समकक्ष” के लिए तकनीकी शब्द congruent (सर्वांगसम) है।

मॉड्यूलो संख्या को अभाज्य संख्या से विभाजित करने पर शेषफल (remainder) की गणना करता है। उदाहरण के लिए, यदि हमारा मॉड्यूलो 7 है, तो संख्या 12, 5 के congruent है यानी $12 \pmod 7 = 5$, और संख्या 14, 0 के congruent है। इसी तरह, जब हम दो संख्याएं जोड़ते हैं, मान लें 3 + 5, तो परिणामी योग 8, 1 के congruent होता है (8 mod 7 = 1)। नीचे दिया गया एनिमेशन इसे दर्शाता है:

Python में, ऊपर दिखाई गई गणना की इस प्रकार गणना की जा सकती है:

Copy
p = 7
result = (3 + 5) % p
print(result) # prints 1

इस अध्याय में, जब भी हम गणना करते हैं, हम अपने परिणाम को $0…(p-1)$ की सीमा में एक संख्या के रूप में व्यक्त करेंगे, जो हमारे फाइनाइट फील्ड p में तत्वों का सेट है। उदाहरण के लिए, 2 * 5 = 10, जिसे हम “सरल” करके 3 (मॉड्यूलो 7) कर देते हैं।

ध्यान दें कि कैसे 3 + 5 ने 6 की सीमा को “ओवरफ़्लो” किया। फाइनाइट फील्ड्स में, ओवरफ़्लो कोई बुरी बात नहीं है, हम ओवरफ़्लो होने वाले व्यवहार को गणना का हिस्सा मानते हैं। 7 मॉड्यूलो वाले फाइनाइट फील्ड में, 5 + 3 को 1 के रूप में परिभाषित किया गया है।

अंडरफ़्लो (Underflows) को भी इसी तरह संभाला जाता है। उदाहरण के लिए, $3 - 5 = - 2$, लेकिन मॉड्यूलो 7 में हमें $5$ मिलता है क्योंकि $7 - 2 = 5$ होता है।

मॉड्यूलर अंकगणित कैसे काम करता है

एक सामान्य प्रोग्रामिंग भाषा में, हम फाइनाइट फील्ड में जोड़ को (6 + 1) % 7 == 0 के रूप में लिखते हैं, लेकिन गणितीय संकेतन में, हम आमतौर पर कहते हैं

या अधिक सामान्यतः,

जहां $a$ और $b$ फाइनाइट फील्ड में संख्याएं हैं, $c$ वह शेषफल है जो $≥ p$ और $< 0 $ वाली किसी भी संख्या को वापस सेट $\set{0, 1, …, p - 1}$ में मैप करता है।

संकेतन $\pmod p$ का अर्थ है कि सभी अंकगणित मॉड्यूलो $p$ में किए जाते हैं। उदाहरण के लिए,

यह (Python या C में) (a + b) % p == (c + d) % p के समतुल्य है।

गुणा भी इसी तरह काम करता है, जहां संख्याओं को एक साथ गुणा करके उनका मॉड्यूलो लिया जाता है:

उपरोक्त गुणा संचालन (multiplication operation) को दो तरीकों से विज़ुअलाइज़ किया जा सकता है:

या वैकल्पिक रूप से:

हम फाइनाइट फील्ड में किसी संख्या को “तत्व” (element) कहते हैं।

$p$ और फील्ड का ऑर्डर

जिस संख्या के साथ हम मॉड्यूलो लेते हैं, उसे हम $p$ कहेंगे। हमारे सभी उदाहरणों में यह एक अभाज्य संख्या है। गणित के व्यापक क्षेत्र में, $p$ आवश्यक रूप से अभाज्य नहीं भी हो सकता है, लेकिन हम केवल उन मामलों पर विचार करेंगे जहाँ $p$ अभाज्य है।

इस प्रतिबंध के कारण, फील्ड का ऑर्डर (order) हमेशा $p$ के बराबर होता है। ऑर्डर फील्ड में तत्वों की संख्या है। जिस संख्या के साथ हम मॉड्यूलो लेते हैं, उसके लिए सामान्य शब्द फील्ड की विशेषता (characteristic) है।

उदाहरण के लिए, यदि हमारे पास $p = 5$ है, तो तत्व $\set{0, 1, 2, 3, 4}$ हैं। यहाँ 5 तत्व हैं, इसलिए उस फील्ड का ऑर्डर 5 है।

$p$ योगात्मक पहचान (addition identity)

किसी भी तत्व में $p$ जोड़ने पर वही तत्व मिलता है। उदाहरण के लिए, $(3 + 7) \pmod 7 = 3$। निम्नलिखित एनिमेशन में उदाहरणों पर विचार करें:

योगात्मक प्रतिलोम (Additive Inverse)

विचार करें कि $5 + (-5) = 0$।

गणित में, $a$ का योगात्मक प्रतिलोम वह संख्या $b$ है जिसके लिए $a + b = 0$ हो। आम तौर पर, हम किसी संख्या का योगात्मक प्रतिलोम उसके सामने एक ऋणात्मक चिह्न लगाकर व्यक्त करते हैं। परिभाषा के अनुसार, $-a$ वह संख्या है जिसे $a$ के साथ जोड़ने पर 0 मिलता है।

योगात्मक प्रतिलोम के सामान्य नियम

• शून्य अपना स्वयं का योगात्मक प्रतिलोम है।
• प्रत्येक संख्या का ठीक एक योगात्मक प्रतिलोम होता है

योगात्मक प्रतिलोम के ये नियम फाइनाइट फील्ड्स पर भी लागू होते हैं। हालाँकि हमारे पास $-5$ जैसे ऋणात्मक चिह्न वाले तत्व नहीं होते हैं, फिर भी मॉड्यूलो ऑपरेटर का उपयोग करके कुछ तत्व एक-दूसरे के संबंध में ऋणात्मक संख्याओं की तरह “व्यवहार” कर सकते हैं।

नियमित अंकगणित में, $-5$ वह संख्या है जिसे $5$ में जोड़ने पर परिणाम $0$ आता है। यदि हमारा फाइनाइट फील्ड $p = 7$ है, तो $2$ को $-5$ माना जा सकता है क्योंकि $(5 + 2) \pmod 7 = 0$ होता है। इसी तरह, $5$ को $-2$ माना जा सकता है क्योंकि वे एक-दूसरे के योगात्मक प्रतिलोम हैं। सटीक रूप से कहें तो, $-2$, $5$ के congruent है या $-2 \equiv 5 \pmod 7$।

किसी तत्व का योगात्मक प्रतिलोम निकालने के लिए, बस $p - a$ की गणना करें जहां $a$ वह तत्व है जिसका हम योगात्मक प्रतिलोम खोजने का प्रयास कर रहे हैं। उदाहरण के लिए, 14 मॉड्यूलो 23 का योगात्मक प्रतिलोम खोजने के लिए, हम $23 - 14 = 9$ की गणना करते हैं। हम देख सकते हैं कि $14 + 9 \pmod {23} = 0$ है। $p$ शून्य के congruent है, इसलिए यह $-5$ की गणना $0 - 5$ के रूप में करने के समतुल्य है।

वास्तविक संख्याओं की तरह:

• फाइनाइट फील्ड में प्रत्येक तत्व का ठीक एक योगात्मक प्रतिलोम होता है
• शून्य अपना स्वयं का योगात्मक प्रतिलोम है।

फाइनाइट फील्ड में योगात्मक प्रतिलोम का सामान्य पैटर्न यह है कि फाइनाइट फील्ड के पहले आधे हिस्से के तत्व दूसरे आधे हिस्से के तत्वों के योगात्मक प्रतिलोम होते हैं, जैसा कि नीचे दिए गए चित्र में दिखाया गया है। शून्य एक अपवाद है क्योंकि यह अपना स्वयं का योगात्मक प्रतिलोम है। फील्ड $p = 7$ में हरी रेखा से जुड़ी संख्याएं एक-दूसरे की योगात्मक प्रतिलोम हैं:

Exercise: मान लें कि हम एक $p \geq 3$ चुनते हैं। कौन से गैर-शून्य (non-zero) मान, यदि कोई हों, अपने स्वयं के योगात्मक प्रतिलोम हैं?

गुणात्मक प्रतिलोम (Multiplicative inverse)

विचार करें कि $5 × (1/5) = 1$।

$a$ का गुणात्मक प्रतिलोम वह संख्या $b$ है जिसके लिए $ab = 1$ हो। शून्य को छोड़कर हर तत्व का एक गुणात्मक प्रतिलोम होता है। “नियमित संख्याओं” के साथ, गुणात्मक प्रतिलोम $1 / \text{num}$ होता है। उदाहरण के लिए, $5$ का गुणात्मक प्रतिलोम $1/5$ है, और $19$ का गुणात्मक प्रतिलोम $1/19$ है।

हालाँकि फाइनाइट फील्ड्स में हमारे पास भिन्न (fractional) संख्याएँ नहीं होती हैं, फिर भी हम संख्याओं के ऐसे जोड़े ढूँढ सकते हैं जो एक साथ जोड़े या गुणा किए जाने पर भिन्नों की तरह “व्यवहार” करते हैं।

उदाहरण के लिए, फाइनाइट फील्ड $p = 7$ में $4$ का गुणात्मक प्रतिलोम $2$ है, क्योंकि $4 * 2 = 8$, और $8 \pmod 7 = 1$। इस प्रकार, $2$ फाइनाइट फील्ड में $1/4$ की तरह “व्यवहार” करता है, या सटीक रूप से कहें तो, $1/4$, $2 \pmod 7$ के congruent है।

फाइनाइट फील्ड अंकगणित में गुणात्मक प्रतिलोम के सामान्य नियम:

• 0 का कोई गुणात्मक प्रतिलोम नहीं होता
• 1 अपना स्वयं का गुणात्मक प्रतिलोम है
• प्रत्येक संख्या (0 को छोड़कर) का ठीक एक गुणात्मक प्रतिलोम होता है (जो वह स्वयं भी हो सकता है)
• मान $(p - 1)$ वाला तत्व अपना स्वयं का गुणात्मक प्रतिलोम होता है। उदाहरण के लिए, $p = 103$ वाले फाइनाइट फील्ड में, $1$ और $102$ अपने स्वयं के गुणात्मक प्रतिलोम हैं। $p = 23$ वाले फाइनाइट फील्ड में, $1$ और $22$ अपने स्वयं के गुणात्मक प्रतिलोम हैं (इसका कारण आगामी अनुभाग में समझाया गया है)। एक और उदाहरण: मॉड्यूलो 5 वाले फाइनाइट फील्ड में, 1 अपना स्वयं का प्रतिलोम है, और 4 अपना स्वयं का प्रतिलोम है। $4 \times 4 = 16$, और $16 \pmod 5 = 1$।

मान $p - 1$ वाला तत्व अपना स्वयं का गुणात्मक प्रतिलोम क्यों है

जब हम $-1$ को उसी से गुणा करते हैं, तो हमें $1$ मिलता है। इसलिए, वास्तविक संख्याओं के लिए $-1$ अपना स्वयं का गुणात्मक प्रतिलोम है। मान $(p - 1)$ वाला तत्व $-1$ के congruent होता है। इसलिए, हम उम्मीद करते हैं कि $(p - 1)$ अपना स्वयं का गुणात्मक प्रतिलोम होगा, और वास्तव में ऐसा ही है।

$p - 1$ अपना स्वयं का गुणात्मक प्रतिलोम क्यों है, यह देखने के एक और तरीके के रूप में, विचार करें कि $(p - 1)(p - 1) = p² - 2p + 1$। चूंकि $p$, $0$ के congruent है, तो $p² - 2p + 1$ सरल होकर $0^2 - 2*0 + 1 = 1$ हो जाता है।

फाइनाइट फील्ड्स पर एरिथमेटिक सर्किट्स के समाधान

यदि हम नियमित संख्याओं पर निम्नलिखित एरिथमेटिक सर्किट पर विचार करते हैं, तो हम उम्मीद करते हैं कि x = -1 ही एकमात्र संतुष्ट करने वाला असाइनमेंट (satisfying assignment) होगा।

Copy
x * x === 1
x + 1 === 0

फाइनाइट फील्ड में, संतुष्ट करने वाला असाइनमेंट $-1$ के congruent तत्व, या $p - 1$ होता है।

Fermat’s Little Theorem के साथ गुणात्मक प्रतिलोम की गणना

Fermat’s Little Theorem यह कहता है कि

दूसरे शब्दों में, यदि आप किसी गैर-शून्य तत्व की घात $p$ तक बढ़ाते हैं, तो आपको वापस वही तत्व मिलता है। कुछ उदाहरण:

• $3⁵ \pmod 5 = 3$
• $4⁷ \pmod 7 = 4$
• $14⁵³ \pmod {53} = 14$

अब विचार करें यदि हम $aᵖ = a \pmod p$ के दोनों पक्षों को $a$ से विभाजित करते हैं (याद रखें, $a ≠ 0$):

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

इसका अर्थ है कि $aᵖ⁻² \pmod p$, $a$ का गुणात्मक प्रतिलोम है, क्योंकि $a$ और $aᵖ⁻²$ का गुणनफल 1 होता है।

कुछ उदाहरण:

• फाइनाइट फील्ड $p = 7$ में $3$ का गुणात्मक प्रतिलोम $5$ है। $3⁷⁻² = 5 \pmod 7$
• फाइनाइट फील्ड $p = 11$ में 8 का गुणात्मक प्रतिलोम $7$ है। $8¹¹⁻² = 7 \pmod {11}$

इस दृष्टिकोण का लाभ यह है कि हम एक स्मार्ट कॉन्ट्रैक्ट में मॉड्यूलर प्रतिलोम की गणना करने के लिए Ethereum में precompile expmod का उपयोग कर सकते हैं।

व्यवहार में, गुणात्मक प्रतिलोम की गणना करने का यह एक आदर्श तरीका नहीं है क्योंकि किसी संख्या को बड़ी घात (power) तक बढ़ाना कम्प्यूटेशनल रूप से महंगा है। जो लाइब्रेरीज़ गुणात्मक प्रतिलोम की गणना करती हैं, वे हुड के नीचे (under the hood) अधिक कुशल एल्गोरिदम का उपयोग करती हैं। हालाँकि, जब ऐसी कोई लाइब्रेरी उपलब्ध न हो, और आप एक त्वरित और सरल समाधान चाहते हों, और एक बड़े घातांक (exponent) की गणना करना अत्यधिक महँगा न हो, तो Fermat’s Little Theorem का उपयोग किया जा सकता है।

Python के साथ गुणात्मक प्रतिलोम की गणना

Python 3.8 या इसके बाद के वर्ज़न का उपयोग करते हुए, हम फाइनाइट फील्ड p में a का गुणात्मक प्रतिलोम निकालने के लिए pow(a, -1, p) कर सकते हैं। pow का पहला तर्क बेस (base) है, दूसरा घातांक (exponent) है, और तीसरा मॉड्यूलर (modulus) है।

उदाहरण:

Copy
p = 17
print(pow(5, -1, p))
# 7
assert (5 * 7) % p == 1

Exercise: 3 मॉड्यूलो 5 का गुणात्मक प्रतिलोम ज्ञात करें। केवल 5 संभावनाएँ हैं, इसलिए उन सभी को आज़माएँ और देखें कि कौन सी काम करती है।

Exercise: फाइनाइट फील्ड $p = 51$ में 50 का गुणात्मक प्रतिलोम क्या है? इसकी गणना करने के लिए आपको Python की आवश्यकता नहीं है, “गुणात्मक प्रतिलोम के सामान्य नियम” में वर्णित सिद्धांतों को देखें।

Exercise: p = 311 के फाइनाइट फील्ड में 288 के गुणात्मक प्रतिलोम की गणना करने के लिए Python का उपयोग करें। आप यह सत्यापित करके अपने काम की जांच कर सकते हैं कि (288 * answer) % 311 == 1।

गुणात्मक प्रतिलोम का जोड़ना भिन्नों के “नियमित” जोड़ने के अनुरूप है

p = 7 के एक फाइनाइट फील्ड में, संख्या 2 और 4 एक दूसरे के गुणात्मक प्रतिलोम हैं क्योंकि $(2 \times 4) \pmod 7 = 1$। इसका मतलब है कि फाइनाइट फील्ड $p = 7$ में, $4$, $1/2$ के congruent है और $2$, $1/4$ के congruent है।

हम कहते हैं कि फाइनाइट फील्ड $p = 7$ में $4$, $1/2$ के congruent है क्योंकि $2 \times \mathsf{mul\_inv}(2) = 1$। इस फाइनाइट फील्ड में $2$ का गुणात्मक प्रतिलोम $4$ है, इसलिए हम $4$ को $1/2$ की तरह मान सकते हैं।

वास्तविक संख्याओं के साथ, यदि हम $1/2 + 1/2$ जोड़ते हैं, तो हम $1$ प्राप्त करने की उम्मीद करते हैं। फाइनाइट फील्ड में भी ऐसा ही होता है। चूँकि $4$, $1/2$ की तरह “व्यवहार” करता है, इसलिए हम उम्मीद करते हैं कि $4 + 4 \pmod 7 = 1$ होगा, और वास्तव में ऐसा होता है।

हम एक फाइनाइट फील्ड में संख्या $5/6$ को एनकोड करने में सक्षम हैं, इसे $5 * (1/6)$, या $5 \times \mathsf{mul\_inv}(6)$ ऑपरेशन के रूप में सोचकर।

विचार करें कि $1/2 + 1/3 = 5/6$। यदि हमारा फाइनाइट फील्ड $p = 7$ है, तो $1/2$, $2$ का गुणात्मक प्रतिलोम है, $1/3$, 3 का गुणात्मक प्रतिलोम है, और $5/6$, 6 के गुणात्मक प्रतिलोम का $5$ गुना है:

Copy
p = 7
one_half = pow(2, -1, p)
one_third = pow(3, -1, p)
five_over_six = (pow(6, -1, p) * 5) % p

assert (one_half + one_third) % p == five_over_six
# True

एक फाइनाइट फील्ड में “भिन्न” (fraction) की गणना करने का सामान्य तरीका अंश (numerator) को हर (denominator) के गुणात्मक प्रतिलोम से गुणा करके, मॉड्यूलो p लेना है:

Copy
def compute_field_element_from_fraction(num, den, p):
	inv_den = pow(den, -1, p)
	return (num * inv_den) % p

ऐसा करना तब संभव नहीं है जब हर p का गुणक (multiple) हो। उदाहरण के लिए, $1/7$ को फाइनाइट फील्ड $p = 7$ में प्रदर्शित नहीं किया जा सकता क्योंकि pow(7, -1, 7) का कोई हल नहीं है। मॉड्यूलो विभाजन के बाद का शेषफल लेता है, और $7/7$ का शेषफल शून्य है, या अधिक सामान्यतः, $7/d$ शून्य होता है जब $d$, $7$ का गुणक होता है। गुणात्मक प्रतिलोम का अर्थ है कि हम किसी संख्या और उसके प्रतिलोम को एक साथ गुणा करके $1$ प्राप्त कर सकते हैं, लेकिन यदि संख्याओं में से एक शून्य है, तो ऐसा कुछ भी नहीं है जिसे हम शून्य से गुणा करके 1 प्राप्त कर सकें।

Exercise: Python में pow(7, -1, 7) चलाएँ। आपको एक अपवाद (exception) दिखाई देगा, ValueError: base is not invertible for the given modulus। $7$ mod $7$ शून्य के बराबर है। ऐसा कुछ भी नहीं है जिसे हम शून्य से गुणा करके $1$ प्राप्त कर सकें।

फाइनाइट फील्ड “डिवीजन” सटीक हानि (precision loss) से ग्रस्त नहीं होता

यदि हम अधिकांश प्रोग्रामिंग भाषाओं में 1 / 3 को विभाजित करते हैं, तो हमें सटीकता (precision) का नुकसान होगा क्योंकि $0.\overline{3}$ को बाइनरी में प्रदर्शित नहीं किया जा सकता है।

हालाँकि, फाइनाइट फील्ड में 1 / 3 केवल 3 का गुणात्मक प्रतिलोम है।

इसका अर्थ है कि एरिथमेटिक सर्किट

Copy
x + y + z === 1;
x === y;
y === z;

का फाइनाइट फील्ड में किए जाने पर एक सटीक समाधान होता है। यदि हम अपने एरिथमेटिक सर्किट के डेटा प्रकारों के लिए फिक्स्ड पॉइंट या फ्लोटिंग पॉइंट नंबरों का उपयोग करते हैं तो यह मज़बूती से करना संभव नहीं होगा (विचार करें कि 0.33333 + 0.33333 + 0.33333 जोड़ने पर 1 के बजाय 0.99999 प्राप्त होगा)।

Python में निम्नलिखित कार्यान्वयन सर्किट को दर्शाता है:

Copy
p = 11

# x, y, z have value 1/3
x = pow(3, -1, 11)
y = pow(3, -1, 11)
z = pow(3, -1, 11)

assert x == y;
assert y == z;
assert (x + y + z) % p == 1

फाइनाइट फील्ड तत्वों में “सम” (even) या “विषम” (odd) की पारंपरिक धारणा नहीं होती

हम किसी संख्या को “सम” कहते हैं यदि इसे बिना किसी शेषफल के दो से विभाजित किया जा सकता है।

एक फाइनाइट फील्ड में, किसी भी तत्व को बिना किसी शेषफल के 2 से विभाजित किया जा सकता है।

अर्थात्, “दो से विभाजित करना” वास्तव में 2 के गुणात्मक प्रतिलोम से गुणा करना है, और इसके परिणामस्वरूप हमेशा बिना “शेषफल” के एक अन्य फील्ड तत्व मिलेगा।

हालाँकि, यदि हमारे पास फील्ड तत्व का बाइनरी प्रतिनिधित्व है, तो हम यह जांच सकते हैं कि तत्व सम है या विषम, यदि इसे पूर्णांक (integer) के रूप में कास्ट किया गया हो। यदि सबसे कम महत्वपूर्ण बिट (least significant bit) 1 है, तो संख्या विषम है (यदि इसे पूर्णांक के रूप में समझा जाए, फाइनाइट फील्ड तत्व के रूप में नहीं)।

Python में फाइनाइट फील्ड लाइब्रेरी

क्योंकि Python में बार-बार pow और % p लिखना थोड़ा थकाऊ हो सकता है, इसलिए पाठक इसके बजाय galois library का उपयोग करना चाह सकते हैं (फाइनाइट फील्ड्स को कभी-कभी गैल्वा फील्ड्स / Galois fields कहा जाता है, जिसका उच्चारण “गैल-वाह” होता है)। इसे python3 -m pip install galois के साथ इंस्टॉल किया जा सकता है।

नीचे, हम galois लाइब्रेरी का उपयोग करने के लिए उपरोक्त अनुभाग $(1/2 + 1/3 = 5/6)$ से भिन्न (fractions) के जोड़ के कोड का अनुवाद करते हैं। लाइब्रेरी गणितीय ऑपरेटरों को फाइनाइट फील्ड में काम करने के लिए ओवरराइट करती है:

Copy
import galois
GF7 = galois.GF(7) # GF7 is a class that wraps 7

one_half = GF7(1) / GF7(2)
one_third = GF7(1) / GF7(3)
five_over_six = GF7(5) / GF7(6)

assert one_half + one_third == five_over_six  

ऑपरेशन 1 / GF(a), a के गुणात्मक प्रतिलोम की गणना करता है।

galois लाइब्रेरी सामने एक ऋणात्मक चिह्न जोड़कर योगात्मक प्रतिलोम की गणना कर सकती है:

Copy
negative_two = -GF7(2)
assert negative_two + GF7(2) == 0

भिन्नों का गुणा भी संगत है

आइए इस उदाहरण के लिए फाइनाइट फील्ड p = 11 का उपयोग करें।

नियमित संख्याओं के साथ हम जानते हैं कि $1/3 * 1/2 = 1/6$।

आइए इसी ऑपरेशन को फाइनाइट फील्ड में करें:

Copy

import galois
GF = galois.GF(11)

one_third = GF(1) / GF(3)
one_half = GF(1) / GF(2)
one_sixth = GF(1) / GF(6)

assert one_third * one_half == one_sixth

Exercise: यह जांचने के लिए galois लाइब्रेरी का उपयोग करें कि फाइनाइट फील्ड $p = 17$ में $3/4 * 1/2 = 3/8$ है।

सभी गैर-शून्य a, b के लिए a × b ≠ 0

किसी फाइनाइट फील्ड में शून्य प्राप्त करने के लिए किन्हीं दो तत्वों को एक साथ गुणा नहीं किया जा सकता जब तक कि उनमें से कोई एक तत्व स्वयं शून्य न हो। नियमित संख्याओं के मामले में भी यह सच है।

इसे समझने के लिए, फाइनाइट फील्ड $p = 7$ पर विचार करें। दो संख्याओं को एक साथ गुणा करने और परिणाम के रूप में $0$ प्राप्त करने के लिए, तो पदों (terms) $a$ में से एक को 7 का गुणक (multiple) होना चाहिए, ताकि $a \pmod 7$ शून्य हो। हालाँकि, $\set{0, 1, 2, 3, 5, 6}$ में से कोई भी 7 का गुणक नहीं है, इसलिए ऐसा नहीं हो सकता।

जब हम एरिथमेटिक सर्किट डिजाइन करेंगे तो हम इस तथ्य का बार-बार उल्लेख करेंगे। उदाहरण के लिए, यदि हम जानते हैं

Copy
x₁ * x₂ * ... * xₙ ≠ 0 

तो हम निश्चित हो सकते हैं कि सभी चर x₁, x₂, xₙ गैर-शून्य हैं — भले ही हम उनके मान न जानते हों।

यहाँ बताया गया है कि हम यथार्थवादी (realistic) एरिथमेटिक सर्किट के लिए इस ट्रिक का उपयोग कैसे कर सकते हैं। मान लीजिए कि हमारे पास सिग्नल्स x₁, x₂, x₃ हैं। हम यह निर्दिष्ट किए बिना कि कौन सा सिग्नल 8 है, इनमें से कम से कम एक सिग्नल के मान को 8 तक सीमित (constrain) करना चाहते हैं। सबसे पहले हम अपने फील्ड के लिए 8 का योगात्मक प्रतिलोम a_inv(8) निकालते हैं। फिर हम करते हैं:

(x₁ + a_inv(8))(x₂ + a_inv(8))(x₃ + a_inv(8)) === 0

इसे इस प्रकार लिखा जा सकता है

(x₁ - 8)(x₂ - 8)(x₃ - 8) === 0

इस समझ के साथ कि -8 हमारे फाइनाइट फील्ड के लिए 8 का योगात्मक प्रतिलोम है।

जब तक किसी एक सिग्नल का मान 8 है, तो वह पद (term) शून्य होगा और पूरे व्यंजक (expression) का गुणनफल शून्य हो जाएगा। यह ट्रिक दो तथ्यों पर निर्भर करती है:

• यदि सभी पद गैर-शून्य हैं, तो व्यंजक के शून्य होने का कोई तरीका नहीं है
• 8 का योगात्मक प्रतिलोम अद्वितीय (unique) है, और 8 का योगात्मक प्रतिलोम 8 का अद्वितीय योगात्मक प्रतिलोम है। दूसरे शब्दों में, 8 के अलावा कोई ऐसा मान नहीं है जिसके परिणामस्वरूप 8 + inv(8) शून्य हो।

इसलिए, एरिथमेटिक सर्किट (x₁ + a_inv(8))(x₂ + a_inv(8))(x₃ + a_inv(8)) === 0 यह बताता है कि x₁, x₂, xₙ में से कम से कम एक का मान 8 है।

फाइनाइट फील्ड संचालन सहचारी (associative), क्रमविनिमेय (commutative) और वितरणात्मक (distributive) होते हैं

नियमित गणित की तरह ही, मॉड्यूलर अंकगणित के साथ, सहचारी, क्रमविनिमेय और वितरणात्मक गुण लागू होते हैं, अर्थात

associative

$(a + b) + c = a + (b + c) \pmod p$

commutative addition

$(a + b) = (b + a) \pmod p$

commutative multiplication

$ab = ba \pmod p$

distributive

$a(b + c) = ab + ac \pmod p$

मॉड्यूलर वर्गमूल (Modular square roots)

“नियमित गणित” में, पूर्ण वर्ग (perfect square) संख्याओं के पूर्णांक वर्गमूल होते हैं। उदाहरण के लिए, 25 का वर्गमूल 5 है, 49 का वर्गमूल 7 है, और इसी तरह।

फाइनाइट फील्ड के तत्वों का वर्गमूल होने के लिए पूर्ण वर्ग होना आवश्यक नहीं है

विचार करें कि $5 \times 5 \pmod {11} = 3$। इसका अर्थ है कि 3 का वर्गमूल 5 है, मॉड्यूलो 11। फाइनाइट फील्ड्स के रैप-अराउंड (wrap around) होने के तरीके के कारण, फाइनाइट फील्ड तत्वों का वर्गमूल होने के लिए उनका पूर्ण वर्ग होना आवश्यक नहीं है।

नियमित वर्गमूलों की तरह, जिनके दो हल होते हैं: एक धनात्मक और एक ऋणात्मक, फाइनाइट फील्ड में मॉड्यूलर वर्गमूलों के भी दो हल होते हैं। अपवाद तत्व 0 है, जिसका वर्गमूल केवल 0 होता है।

फाइनाइट फील्ड मॉड्यूलो 11 में, निम्नलिखित तत्वों के वर्गमूल हैं:

Exercise: सत्यापित करें कि तालिका में बताए गए वर्गमूल फाइनाइट फील्ड मॉड्यूलो 11 में सही हैं।

ध्यान दें कि दूसरा वर्गमूल हमेशा पहले वर्गमूल का योगात्मक प्रतिलोम होता है, ठीक वास्तविक संख्याओं की तरह।

उदाहरण के लिए:

• नियमित गणित में, $9$ के वर्गमूल $3$ और $-3$ हैं, जहां दोनों एक-दूसरे के योगात्मक प्रतिलोम हैं।
• $p = 11$ के फाइनाइट फील्ड में, 9 के वर्गमूल 3 और 8 हैं। 8, 3 का योगात्मक प्रतिलोम है क्योंकि $8 + 3 \pmod {11}$, $0$ है, ठीक वैसे ही जैसे $3$, $-3$ का योगात्मक प्रतिलोम है।

तत्व 2, 6, 7, 8, और 10 के फाइनाइट फील्ड $p = 11$ में मॉड्यूलर वर्गमूल नहीं होते हैं। इसे 0 से 10 तक के प्रत्येक तत्व का वर्ग (square) करके, और यह देखकर कि 2, 6, 7, 8, और 10 कभी उत्पन्न नहीं होते हैं, खोजा जा सकता है।

Copy
numbers_with_roots = set()
p = 11
for i in range(0, p):
    numbers_with_roots.add(i * i % p)

print("numbers_with_roots:", numbers_with_roots)
# numbers_with_roots: {0, 1, 3, 4, 5, 9}

ध्यान दें कि 3 एक पूर्ण वर्ग नहीं है, लेकिन इस फाइनाइट फील्ड में इसका एक वर्गमूल है।

मॉड्यूलर वर्गमूल की गणना करना

मॉड्यूलर वर्गमूल की गणना Python में libnum library के साथ की जा सकती है। नीचे, हम 5 मॉड्यूलो 11 के वर्गमूल की गणना करते हैं। कार्यों has_sqrtmod_prime_power और sqrtmod_prime_power के तीसरे तर्क को हमारे उद्देश्यों के लिए 1 पर सेट किया जा सकता है।

Copy
# install libnum with `python -m pip install libnum`

from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power
has_sqrtmod_prime_power(5, 11, 1) # True
list(sqrtmod_prime_power(5, 11, 1)) # [4, 7]
# square roots generally have two solutions. 4 and 7 are the square roots of 5 (mod 11)

जब p को 4k + 3 के रूप में लिखा जा सकता है जहाँ k एक पूर्णांक है, तो मॉड्यूलर वर्गमूल की गणना निम्नानुसार की जा सकती है:

Copy
def mod_sqrt(x, p):
	assert (p - 3) % 4 == 0, "prime not 4k + 3"
	exponent = (p + 1) // 4
	return pow(x, exponent, p) # x ^ e % p

उपरोक्त फ़ंक्शन x मॉड्यूलो p के वर्गमूलों में से एक देता है। दूसरा वर्गमूल लौटाए गए मान के योगात्मक प्रतिलोम की गणना करके निकाला जा सकता है। यदि अभाज्य संख्या 4k + 3 के रूप की नहीं है तो मॉड्यूलर वर्गमूल की गणना करने के लिए Tonelli-Shanks algorithm का उपयोग किया जाना चाहिए (जिसे ऊपर दी गई libnum लाइब्रेरी लागू करती है)।

इसका निहितार्थ (implication) यह है कि एरिथमेटिक सर्किट x * x === y के दो समाधान हो सकते हैं। उदाहरण के लिए, एक फाइनाइट फील्ड p = 11 में, ऐसा लग सकता है कि एरिथमेटिक सर्किट x * x === 4 केवल मान 2 को स्वीकार करता है क्योंकि -2 एक फाइनाइट फील्ड तत्व नहीं है। हालाँकि, यह धारणा बहुत गलत है! असाइनमेंट x = 9, जो -2 के congruent है, भी सर्किट को संतुष्ट करता है।

Exercise: p = 19 के फाइनाइट फील्ड में 5 के मॉड्यूलर वर्गमूल की गणना करने के लिए ऊपर दिए गए कोड स्निपेट का उपयोग करें। कोड आपको केवल एक ही उत्तर देगा। आप दूसरे की गणना कैसे कर सकते हैं?

फाइनाइट फील्ड्स में रैखिक समीकरणों की प्रणालियाँ (Linear systems of equations)

जैसा कि पिछले अध्याय में उल्लेख किया गया है, एक एरिथमेटिक सर्किट मूल रूप से समीकरणों की एक प्रणाली है। फाइनाइट फील्ड में रैखिक समीकरणों की प्रणालियाँ नियमित संख्याओं पर रैखिक समीकरणों की प्रणाली के साथ बहुत सारे गुण साझा करती हैं। हालाँकि, कुछ अंतर हैं जो शुरुआत में अप्रत्याशित हो सकते हैं। चूँकि एरिथमेटिक सर्किट की गणना फाइनाइट फील्ड्स पर की जाती है, इसलिए हमें यह समझना चाहिए कि ये आश्चर्यजनक विचलन (deviations) कहाँ हो सकते हैं।

रैखिक समीकरण प्रणाली अज्ञात (चर) के एक सेट के साथ सीधी रेखा के समीकरणों का एक संग्रह है जिसे हम एक साथ हल करने का प्रयास करते हैं। रैखिक समीकरणों की प्रणाली का अनूठा (unique) समाधान खोजने के लिए, हमें प्रत्येक चर के लिए एक संख्यात्मक मान खोजना होगा जो सिस्टम में सभी समीकरणों को एक साथ संतुष्ट करेगा।

वास्तविक संख्याओं वाले रैखिक समीकरणों की प्रणालियों में या तो:

1. कोई समाधान नहीं: जिसका अर्थ है कि दो समीकरण उन रेखाओं का प्रतिनिधित्व करते हैं जो दो आयामों (dimensions) में समानांतर हैं, या तीन या अधिक आयामों में कभी पार (cross) नहीं होती हैं

2. एक समाधान: जिसका अर्थ है कि रेखाएं एक बिंदु पर प्रतिच्छेद (intersect) करती हैं

3. अनंत समाधान (Infinite solutions): यदि दोनों समीकरण एक ही रेखा का प्रतिनिधित्व करते हैं, तो प्रतिच्छेदन के अनंत बिंदु होते हैं, और रैखिक समीकरणों की प्रणाली के अनंत समाधान होते हैं।

फाइनाइट फील्ड समीकरणों की प्रणालियों में भी होते हैं

1. कोई समाधान नहीं या

2. एक समाधान या

3. $p$ कई समाधान, अर्थात फील्ड के ऑर्डर के जितने समाधान

हालाँकि, केवल इसलिए कि वास्तविक संख्याओं पर रैखिक समीकरणों की प्रणाली में शून्य, एक, या अनंत समाधान हैं, यह तात्पर्य नहीं है कि फाइनाइट फील्ड पर उसी रैखिक समीकरण प्रणाली में भी शून्य, एक, या p कई समाधान होंगे।

जिस कारण से हम इस पर ज़ोर देते हैं वह यह है कि हम NP में किसी समस्या के अपने समाधान को एनकोड करने के लिए एरिथमेटिक सर्किट और सिग्नल्स के लिए असाइनमेंट का उपयोग करते हैं। हालाँकि, क्योंकि एरिथमेटिक सर्किट्स फाइनाइट फील्ड्स के साथ एनकोड किए जाते हैं, हम अंततः समस्या को इस तरह से एनकोड कर सकते हैं जो उन समीकरणों के व्यवहार को नहीं पकड़ता जिन्हें हम मॉडल करने का प्रयास कर रहे हैं।

निम्नलिखित तीन उदाहरण दिखाते हैं कि फाइनाइट फील्ड पर किए जाने पर समीकरणों की प्रणाली का व्यवहार कैसे बदल सकता है।

Example 1: नियमित संख्याओं पर एक समाधान वाले समीकरणों की प्रणाली में फाइनाइट फील्ड में p कई समाधान हो सकते हैं

उदाहरण के लिए, हम प्लॉट करते हैं:

इसका एक समाधान है: वास्तविक संख्याओं के लिए $(1, 0)$, लेकिन फाइनाइट फील्ड $p = 11$ पर, इसके 11 समाधान हैं: $\set{(0, 6), (1, 0), (2, 5), (3, 10), (4, 4), (5, 9), (6, 3), (7, 8), (8, 2), (9, 7), (10, 1)}$।

यह न मानें कि जिस समीकरण प्रणाली (एरिथमेटिक सर्किट) का वास्तविक संख्याओं में एक समाधान है, उसका फाइनाइट फील्ड में भी एक ही समाधान होगा!

नीचे हम फाइनाइट फील्ड्स पर समीकरणों की प्रणालियों के समाधानों को प्लॉट करते हैं ताकि यह स्पष्ट किया जा सके कि दोनों समीकरण “हर जगह प्रतिच्छेद करते हैं”, अर्थात, दोनों समीकरणों को संतुष्ट करने वाले बिंदुओं का एक ही सेट है:

यह बहुत उल्टा लग सकता है — आइए देखें यह कैसे होता है। यदि हम मूल समीकरणों को हल करते हैं:

$y$ के लिए हमें मिलता है:

$1/2$, $2$ का गुणात्मक प्रतिलोम है। फाइनाइट फील्ड $p = 11$ में, $6$, $2$ का गुणात्मक प्रतिलोम है, अर्थात $2 * 6 \pmod {11} = 1$। इसलिए, फाइनाइट फील्ड $p = 11$ में $x + 2y = 1$ और $6x + y = 6$ वास्तव में एक ही समीकरण हैं। अर्थात्, समीकरण $y = 1/2 - 1/2x$ को फाइनाइट फील्ड में एनकोड किए जाने पर $y = \mathsf{mul\_inv}(2) - \mathsf{mul\_inv}(2)x$ होता है जो $y = 6 - 6x$ है, जो सिस्टम में दूसरे समीकरण के समान है।

Example 2: नियमित संख्याओं पर एक समाधान वाले समीकरणों की प्रणाली का फाइनाइट फील्ड में शून्य समाधान हो सकता है

इसके अलावा, अप्रत्याशित रूप से, वास्तविक संख्याओं पर एक समाधान वाले समीकरणों की प्रणाली का फाइनाइट फील्ड में कोई समाधान नहीं हो सकता है:

स्पष्ट रूप से, इस समीकरण प्रणाली में एक प्रतिच्छेदन बिंदु (intersection point) है, लेकिन फाइनाइट फील्ड पर इसका कोई समाधान नहीं है।

नीचे हम फाइनाइट फील्ड में दो समीकरणों का प्लॉट दिखाते हैं:

Exercise: x = 0..10, y = 0..10 पर (x, y) के प्रत्येक संयोजन (combination) को ब्रूटफोर्स (bruteforce) करने के लिए कोड लिखें ताकि यह सत्यापित किया जा सके कि उपरोक्त प्रणाली का फाइनाइट फील्ड p = 11 पर कोई समाधान नहीं है।

इस समीकरण प्रणाली का फाइनाइट फील्ड $p = 11$ में कोई समाधान क्यों नहीं है?

यदि हम हल करते हैं

वास्तविक संख्याओं के लिए, हमें समाधान मिलते हैं

उपरोक्त भिन्नों (fractions) का फाइनाइट फील्ड p = 11 में कोई congruent तत्व नहीं है।

याद रखें कि किसी संख्या से विभाजित करना उसके गुणात्मक प्रतिलोम से गुणा करने के बराबर है। इसके अलावा, याद रखें कि फील्ड ऑर्डर (इस मामले में 11) का गुणात्मक प्रतिलोम नहीं होगा, क्योंकि फील्ड ऑर्डर 0 के congruent है।

a का गुणात्मक प्रतिलोम वह मान b है जिसके लिए a * b = 1 हो। हालाँकि, यदि a = 0 (या इसके congruent कोई मान) तो b के लिए कोई समाधान नहीं है। इसलिए, हमने वास्तविक संख्याओं में समाधानों के लिए जो व्यंजक लिखे हैं, उन्हें हमारे फाइनाइट फील्ड के तत्वों में अनुवादित नहीं किया जा सकता है।

इसलिए ऊपर दिए गए समाधान (x, y) फाइनाइट फील्ड का हिस्सा नहीं हैं। अतः, फाइनाइट फील्ड p = 11 में, x + 2y = 1 और 7x + 3y = 2 समानांतर रेखाएँ हैं।

इसे दूसरे नज़रिए से देखने के लिए, हम y के लिए समीकरणों को हल कर सकते हैं और प्राप्त कर सकते हैं:

हमने पिछले अनुभाग में देखा कि 6, 2 का गुणात्मक प्रतिलोम है, इसलिए पहले समीकरण का “ढलान” (slope) -1/2 है जो -6 है या फाइनाइट फील्ड में समान रूप से 5 है। दूसरे समीकरण में, हम 3 के गुणात्मक प्रतिलोम को -7 से गुणा करके ढलान की गणना करते हैं: (-7 * pow(3, -1, 11)) % 11 = 5। अब हम दिखाते हैं कि फाइनाइट फील्ड में उनके ढलान समान हैं।

ढलान (slope), y = c + bx के रूप में x का गुणांक (coefficient) है। उपरोक्त दो समीकरणों के लिए, पहला ढलान -1/2 है और दूसरा ढलान -7/3 है। यदि हम इन दोनों भिन्नों को फाइनाइट फील्ड p = 11 के तत्व में परिवर्तित करते हैं, तो हमें 5 का समान मान मिलता है:

Copy
import galois
GF11 = galois.GF(11)

negative_1 = -GF11(1)
negative_7 = -GF11(7)

slope1 = GF11(negative_1) / GF11(2)
slope2 = GF11(negative_7) / GF11(3)

assert slope1 == slope2 # 5 == 5

इस तथ्य का एरिथमेटिक सर्किट के लिए निहितार्थ (implication):

Copy
x + 2 * y === 1
7 * x + 3 * y === 2

यह है कि एरिथमेटिक सर्किट का फाइनाइट फील्ड p = 11 में कोई संतुष्ट करने वाला असाइनमेंट नहीं है।

Example 3: नियमित संख्याओं पर शून्य समाधान वाले समीकरणों की प्रणाली के फाइनाइट फील्ड में p समाधान हो सकते हैं

निम्नलिखित दो सूत्र (formulas) उन रेखाओं को प्लॉट करते हैं जो समानांतर हैं और इसलिए वास्तविक संख्याओं (reals) पर उनका कोई समाधान नहीं है:

हालाँकि, फाइनाइट फील्ड p = 11 पर, इसके 11 समाधान हैं: $\set{(0, 7), (1, 1), (2, 6), (3, 0), (4, 5), (5, 10), (6, 4), (7, 9), (8, 3), (9, 8), (10, 2)}$। वे समाधान नीचे प्लॉट किए गए हैं:

Exercise: दोनों समीकरणों को उनके फाइनाइट फील्ड प्रतिनिधित्व में बदलें और देखें कि वे समान हैं।

मान लीजिए कि हमने इस समीकरण प्रणाली को एरिथमेटिक सर्किट के रूप में एनकोड किया है:

Copy
x + 2 * y === 3
4 * x + 8 * y === 1

जिस फाइनाइट फील्ड का हम उपयोग कर रहे हैं, उसके लिए हमारी बाधाएं (constraints) अनावश्यक (redundant) हैं, भले ही वे “अलग दिखती हों।” अर्थात्, दो अलग-अलग दिखने वाली बाधाएँ वास्तव में $x$ और $y$ को समान मान रखने के लिए बाध्य करती हैं।

फाइनाइट फील्ड्स में बहुपद (Polynomials)

एरिथमेटिक सर्किट वाले अध्याय में, हमने x को केवल 0 या 1 होने के लिए बाध्य करने के लिए बहुपद x(x - 1) === 0 का उपयोग किया था। इसे बहुपद समीकरण के रूप में लिखा जा सकता है। ऐसा करने के लिए, हम अपने व्यंजक का तब तक पूरी तरह से विस्तार करते हैं जब तक कि इसे x की अलग-अलग घातों (powers) के रूप में व्यक्त न कर दिया जाए, जिनमें से प्रत्येक को एक गुणांक से गुणा किया जाता है। इस मामले में: x² - x === 0।

यह धारणा कि बहुपद x² - x === 0 के फाइनाइट फील्ड में (साथ ही वास्तविक संख्याओं के साथ) केवल समाधान 0 या 1 हैं, इस मामले में सही है। हालाँकि, सामान्य तौर पर, किसी को यह नहीं मानना चाहिए कि वास्तविक संख्याओं पर किसी बहुपद के मूल (roots), फाइनाइट फील्ड में समान मूल रखते हैं। हम बाद में कुछ प्रति-उदाहरण (counterexamples) दिखाएंगे।

फिर भी, फाइनाइट फील्ड्स में बहुपद वास्तविक संख्याओं पर बहुपदों के साथ बहुत सारे गुण साझा करते हैं:

• $d$ घात (degree) वाले बहुपद के अधिकतम $d$ मूल होते हैं। बहुपद $p(x)$ के मूल वे मान $r$ हैं जिनके लिए $p(r) = 0$ होता है।
• यदि हम दो बहुपदों $p_1$ और $p_2$ को जोड़ते हैं, तो $p_1 + p_2$ की घात अधिकतम $\max(\deg(p_1), \deg(p_2))$ होगी। यह संभव है कि $p_1 + p_2$ की घात $\max(\deg(p_1), \deg(p_2))$ से कम हो। उदाहरण के लिए, $p_1=x³ + 5x + 7$, और $p_2 = -x³$।
• फाइनाइट फील्ड में बहुपदों को जोड़ना सहचारी (associative), क्रमविनिमेय (commutative) और वितरणात्मक (distributive) नियमों का पालन करता है।
• यदि हम दो बहुपदों $p_1$ और $p_2$ को गुणा करते हैं, तो गुणनफल के मूल, $p_1$ और $p_2$ के मूलों का संघ (union) होंगे।

आइए उदाहरण के रूप में $y = x² \pmod {17}$ को प्लॉट करें।

$x$ का डोमेन फाइनाइट फील्ड के तत्व हैं, और आउटपुट (रेंज) भी फाइनाइट फील्ड का सदस्य होना चाहिए। अर्थात्, ध्यान दें कि कैसे सभी $x$ और $y$ मान $[0,16]$ के अंतराल (interval) में आते हैं। फाइनाइट फील्ड पर एक बहुपद में केवल $p$ से कम $x$ और $y$ मान हो सकते हैं।

फाइनाइट फील्ड $p = 17$ में $y = -x²$ का समतुल्य $y = 16x² \pmod {17}$ है क्योंकि 16 उस फाइनाइट फील्ड में 1 का योगात्मक प्रतिलोम है। बहुपद $y = 16x² \pmod {17}$ नीचे प्लॉट किया गया है:

वे बहुपद जिनके वास्तविक संख्याओं में मूल नहीं होते हैं, उनके फाइनाइट फील्ड में मूल हो सकते हैं

रैखिक समीकरणों की प्रणालियों वाले हमारे उपरोक्त उदाहरणों की तरह, किसी को यह नहीं मानना चाहिए कि वास्तविक संख्याओं में निश्चित मूलों वाले बहुपद के फाइनाइट फील्ड में भी समान मूल होते हैं।

नीचे, हम फाइनाइट फील्ड $p = 17$ में $y = x² + 1$ प्लॉट करते हैं। वास्तविक संख्याओं में, $y = x² + 1$ के कोई वास्तविक मूल नहीं होते हैं। लेकिन फाइनाइट फील्ड में, इसके $4$ और $13$ पर दो मूल हैं, जिन्हें नीचे लाल बिंदुओं में चिह्नित किया गया है:

आइए अब स्पष्ट करते हैं कि $y = x² + 1$ के वास्तविक संख्याओं में मूल क्यों नहीं हैं, लेकिन फाइनाइट फील्ड $p = 17$ में इसके मूल क्यों हैं। फाइनाइट फील्ड $p = 17$ में, 17 शून्य के congruent है। इसलिए यदि हम $x$ में कोई ऐसा मान रखते हैं जिससे $x² + 1$, $17$ हो जाए, तो बहुपद शून्य आउटपुट करेगा, $17$ नहीं। हम $x$ के लिए $x² + 1 = 17$ को हल करके $x² = 17 - 1 = 16$ प्राप्त कर सकते हैं। फाइनाइट फील्ड $p = 17$ में, $x² = 16$ के समाधान $4$ और $13$ हैं। इसलिए, फाइनाइट फील्ड $p = 17$ में $y = x² + 1$ के मूल $4$ और $13$ हैं।

वास्तविक मूलों वाले बहुपदों का फाइनाइट फील्ड में कोई मूल नहीं हो सकता है

बहुपद $y = x² − 5$ पर विचार करें। हम देख सकते हैं कि इसके मूल $\sqrt{5}$ और $-\sqrt{5}$ पर हैं। हालाँकि, यदि हम इसे मॉड्यूलो 17 के फाइनाइट फील्ड पर प्लॉट करते हैं, तो हम देख सकते हैं कि यह कभी x-अक्ष को पार नहीं करता है:

यहाँ कोई मूल नहीं हैं क्योंकि $\sqrt{5}$ को मॉड्यूलो 17 के फाइनाइट फील्ड में प्रदर्शित नहीं किया जा सकता है। हालाँकि, फाइनाइट फील्ड $p = 11$ में, इसके दो मूल होंगे क्योंकि फाइनाइट फील्ड $p = 11$ में 5 के मॉड्यूलर वर्गमूल होते हैं।

ZK Proofs के लिए एरिथमेटिक सर्किट्स में सीमाएँ

यदि हम एक फाइनाइट फील्ड पर एरिथमेटिक सर्किट का उपयोग करके “मुझे बहुपद $y = x² − 5$ का मूल पता है” दिखाने के लिए एक एरिथमेटिक सर्किट लिखना चाहते हैं, तो हम $\sqrt{5}$ को एनकोड करने में सक्षम न होने की समस्या का सामना कर सकते हैं। अर्थात्, वास्तविक संख्याओं पर, $y = x² − 5$ का मूल $\sqrt{5}$ है, लेकिन कुछ फाइनाइट फील्ड्स में इसे व्यक्त नहीं किया जा सकता है। $p$ के आधार पर, एरिथमेटिक सर्किट x² === 5 का कोई संतुष्ट करने वाला विटनेस (witness) नहीं हो सकता है।

Python के साथ फाइनाइट फील्ड्स में बहुपद

एरिथमेटिक सर्किट्स के साथ प्रयोग करते समय, कभी-कभी उन्हें अनुकरण (simulate) करने के लिए Python कोड लिखना सहायक होता है। जब हमारा एरिथमेटिक सर्किट बहुपद रूप में होता है, तो हम इसके व्यवहार का परीक्षण करने के लिए पहले की galois लाइब्रेरी का उपयोग कर सकते हैं। निम्नलिखित कोड उदाहरण बताते हैं कि बहुपदों के साथ काम करने के लिए इस लाइब्रेरी का उपयोग कैसे करें।

फाइनाइट फील्ड में बहुपदों को जोड़ना

नीचे दिए गए कोड में, हम दो बहुपद परिभाषित करते हैं: p1 = x² + 2x + 102 और p2 = x² + x + 1 और फिर उन्हें प्रतीकात्मक रूप से (symbolically) जोड़कर 2x² + 3x बनाते हैं। ध्यान दें कि फाइनाइट फील्ड p = 103 में स्थिर गुणांक (constant coefficient) पद जुड़कर शून्य हो जाते हैं।

Copy
import galois
GF103 = galois.GF(103) # p = 103

# we define a polynomial x^2 + 2x + 102 mod 103
p1 = galois.Poly([1,2,102], GF103)

print(p1)
# x^2 + 2x + 102

# we define a polynomial x^2 + x + 1 mod 103
p2 = galois.Poly([1,1,1], GF103)

print(p1 + p2)
# 2x^2 + 3x

galois लाइब्रेरी ऋणात्मक पूर्णांकों को योगात्मक प्रतिलोम के रूप में समझने के लिए पर्याप्त बुद्धिमान है, जैसा कि नीचे दिया गया कोड प्रदर्शित करता है:

Copy
import galois
GF103 = galois.GF(103) # p = 103

# We can input "-1" as a coefficient, and that will
# automatically be calculated as `p - 1`
# -1 becomes 102 in a field p = 103
p3 = galois.Poly([-1, 1], GF103)
p4 = galois.Poly([-1, 2], GF103)

print(p3)
# 102x + 1
print(p4)
# 102x + 2

फाइनाइट फील्ड में बहुपदों का गुणा करना

हम बहुपदों को एक साथ गुणा कर सकते हैं:

Copy
print(p3 * p4)
# x^2 + 100x + 2

ध्यान दें कि p3 और p4 घात (degree) 1 के बहुपद हैं और उनका गुणनफल घात 2 का बहुपद है।

फाइनाइट फील्ड में बहुपदों के मूल खोजना

फाइनाइट फील्ड्स पर बहुपदों के मूल खोजना एक अलग विषय है (देखें विकिपीडिया पेज: factorizing polynomials over finite fields के लिए एल्गोरिदम)। galois लाइब्रेरी roots फ़ंक्शन के साथ मूलों की गणना निष्पादित कर सकती है। यह सत्यापित करने के लिए उपयोगी हो सकता है कि बहुपद रूप में एरिथमेटिक बाधाएँ (constraints) वास्तव में इच्छित बाधाएँ पैदा करती हैं।

Copy
print((p3 * p4).roots())
# [1, 2]

galois लाइब्रेरी की कमियां (gotchas)

लाइब्रेरी चुपचाप (silently) गुणांक के रूप में पारित फ्लोटिंग पॉइंट नंबरों का फ़्लोर (floor) ले लेती है:

Copy
# The galois library will silently convert
# floats into a integer
galois.Poly([2.5], GF103)
# Poly(2, GF(103))

यदि लाइब्रेरी को p से बड़ी या उसके बराबर संख्या दी जाती है, तो यह रिवर्ट (revert) हो जाएगी:

Copy
# The follow code fails because we cannot
# have coefficients the order of the field or higher
galois.Poly([103], GF103)
# ValueError: GF(103) arrays must have elements in `0 <= x < 103`, not [103].

RareSkills के साथ और जानें

ज़ीरो नॉलेज प्रूफ़्स के बारे में अधिक जानने के लिए हमारी ZK Book देखें।

Practice problems

नीचे दी गई समस्याओं में, 21888242871839275222246405745257275088548364400416034343698204186575808495617 के फाइनाइट फील्ड p का उपयोग करें। ध्यान रखें कि galois लाइब्रेरी को इस आकार के GF ऑब्जेक्ट, galois.GF(p), को इनिशियलाइज़ करने में थोड़ा समय लगता है।

1. एक डेवलपर सभी सिग्नलों को शून्य तक सीमित करने के इरादे से एक एरिथमेटिक सर्किट x * y * z === 0 और x + y + z === 0 बनाता है। इसका एक प्रति-उदाहरण (counter example) खोजें जहां बाधाएं संतुष्ट होती हैं, लेकिन x, y, और z सभी 0 नहीं हैं।
2. एक डेवलपर बहुपद x² + 2x + 3 === 11 के साथ एक सर्किट बनाता है और साबित करता है कि 2 एक समाधान है। दूसरा समाधान क्या है? संकेत: सर्किट को x² + 2x - 8 === 0 के रूप में लिखें फिर मूल (roots) खोजने के लिए बहुपद का हाथ से गुणनखंड (factor) करें। अंत में, दूसरे समाधान को खोजने के लिए फाइनाइट फील्ड में मूलों के congruent तत्व की गणना करें।

मूल रूप से 29 अप्रैल, 2024 को प्रकाशित