परिमित क्षेत्र अंकगणित

गणित में, परिमित क्षेत्र अंकगणित एक परिमित क्षेत्र में अंकगणित है एक क्षेत्र (गणित) जिसमें तत्वों की एक परिमित संख्या (गणित) होती है एक क्षेत्र में अंकगणित के विपरीत होता है, जिसमें अनंत संख्या में तत्व होते हैं, जैसे परिमेय संख्याओं का क्षेत्र होता है।

अपरिमित रूप से अनेक भिन्न परिमित क्षेत्र हैं। उनके तत्वों की संख्या आवश्यक रूप से pⁿ के रूप में होती है जहाँ p एक अभाज्य संख्या है और n एक धनात्मक पूर्णांक है, और समान आकार के दो परिमित क्षेत्र समरूपी होते हैं। अभाज्य p को क्षेत्र की विशेषता कहा जाता है, और धनात्मक पूर्णांक n को इसके अभाज्य क्षेत्र पर क्षेत्र का आयाम कहा जाता है।

परिमित क्षेत्रों का उपयोग विभिन्न प्रकार के अनुप्रयोगों में किया जाता है, जिसमें बीसीएच कोड जैसे रैखिक ब्लॉक कोड में उत्कृष्ट कोडिंग सिद्धांत और क्रिप्टोग्राफी एल्गोरिदम में रीड-सोलोमन त्रुटि संशोधन जैसे प्रतियोगिता नियोजन और प्रयोगों के डिजाइन में रिजेंडेल (एईएस) एन्क्रिप्शन एल्गोरिदम सम्मिलित हैं।

प्रभावी बहुपद प्रतिनिधित्व

pⁿ तत्वों के साथ परिमित क्षेत्र को GF(pⁿ) कहा जाता है और इसे परिमित क्षेत्र सिद्धांत के संस्थापक इवरिस्ट गैलोइस के सम्मान में क्रम pⁿ का गैलोइस क्षेत्र भी कहा जाता है। GF (p), जहाँ p एक अभाज्य संख्या है, वह केवल पूर्णांक मापांक p का वलय है। अर्थात्, कोई पूर्णांक पर सामान्य संक्रिया का उपयोग करके संचालन (जोड़, व्यवकलन, गुणा) कर सकता है, जिसके बाद संशोधन मापांक p हो सकता है। उदाहरण के लिए, GF(5) में, 4 + 3 = 7 को घटाकर 2 मापांक 5 कर दिया गया है। विभाजन व्युत्क्रम मापांक p द्वारा गुणन है, जिसकी गणना विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके की जा सकती है।

एक विशेष स्थिति GF(2) है, जहां योग विशेष OR (XOR) है और गुणन AND है। चूंकि केवल प्रतिवर्त तत्व 1 होता है, विभाजन समरूपता फलन है।

GF(pⁿ) के तत्वों को GF(p) पर n से दृढ़ता से कम घात के बहुपदों के रूप में प्रदर्शित किया जा सकता है। संक्रियक तब मापांक R किया जाता है जहां R, GF(p) पर घात n का एक अखंडनीय बहुपद है, उदाहरण के लिए बहुपद विस्तृत विभाजन का उपयोग करना। दो बहुपदों P और Q का योग सदैव की तरह किया जाता है; गुणन निम्नानुसार किया जा सकता है: सदैव की तरह W = P · Q की गणना करें, फिर शेष मापांक R की गणना करें। बहुपद गुणांक के संदर्भ में इस प्रतिनिधित्व को एक एकपदीय आधार (उर्फ 'बहुपद आधार') कहा जाता है।

GF(pⁿ) के तत्वों के अन्य निरूपण हैं; कुछ उपरोक्त बहुपद प्रतिनिधित्व के लिए समरूप हैं और (उदाहरण के लिए, आव्यूह का उपयोग करके) अन्य अपेक्षाकृत अधिक भिन्न दिखते हैं। सामान्य आधार का उपयोग करने से कुछ संदर्भों में लाभ हो सकता है।

जब अभाज्य संख्या 2 होती है, तो पारंपरिक रूप से GF(pⁿ) द्विआधारी अंक प्रणाली के रूप में, बहुपद में प्रत्येक शब्द के गुणांक के साथ संबंधित तत्व की बाइनरी अभिव्यक्ति में एक बिट द्वारा दर्शाया गया है। ब्रेसेस ( { and } ) या इसी तरह के सीमांकक सामान्य रूप से बाइनरी संख्याओ या उनके हेक्साडेसिमल ( षोडश आधारी) समकक्षों में जोड़े जाते हैं, यह इंगित करने के लिए कि मान क्षेत्र के आधार के गुणांक देता है, इस प्रकार क्षेत्र के एक तत्व का प्रतिनिधित्व करता है। उदाहरण के लिए, निम्नलिखित विशेषता 2 परिमित क्षेत्र में समान मान के समतुल्य प्रतिनिधित्व हैं:

बहुपदीय	x6 + x4 + x + 1
बाइनरी	{01010011}
हेक्साडेसिमल	{53}

प्राथमिक बहुपद

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

परिमित क्षेत्र GF(q) में गुणांक वाले डिग्री n का एक एकगुणांकी अखंडनीय बहुपद, जहां q = pt कुछ अभाज्य p और धनात्मक पूर्णांक t के लिए, एक पूर्वग बहुपद कहलाता है, यदि इसकी सभी जड़ें GF(pⁿ) के पूर्वग बहुपद हैं। परिमित क्षेत्र के बहुपद प्रतिनिधित्व में, इसका तात्पर्य है कि x प्राथमिक तत्व है। जिसके लिए कम से कम एक अलघुकरणीय बहुपद है x प्राथमिक तत्व है। दूसरे शब्दों में, एक प्रारम्भिक बहुपद के लिए, x की घातें क्षेत्र में प्रत्येक शून्येतर मान उत्पन्न करती हैं।

निम्नलिखित उदाहरणों में बहुपद प्रतिनिधित्व का उपयोग नहीं करना सबसे अच्छा है, क्योंकि उदाहरणों के बीच x का अर्थ बदल जाता है। GF(2) पर एकगुणांकी अखंडनीय बहुपद x⁸ + x⁴ + x³ + x + 1 पूर्वग नहीं है। मान लीजिए λ इस बहुपद का (बहुपद प्रतिनिधित्व में यह x होगा) वर्गमूल है, जो कि λ⁸ + λ⁴ + λ³ + λ + 1 = 0 है। अब λ⁵¹ = 1, इसलिए λ, GF(2⁸) का प्रारम्भिक तत्व नहीं है और क्रम 51 का गुणक उपसमूह उत्पन्न करता है। क्षेत्र तत्व λ + 1 पर विचार करें, बहुपद प्रतिनिधित्व में यह x + 1 होगा। अब (λ+1)⁸ + (λ+1)⁴ + (λ+1)³ + (λ+1)² + 1 = λ⁸ + λ⁴ + λ³ + λ + 1 = 0 है। जैसा कि इस प्रारम्भिक बहुपद के सभी वर्गमूल प्रारम्भिक तत्व हैं, GF(2⁸) ((λ + 1)²⁵⁵ = 1 और कोई छोटी घात नहीं है। GF(2⁸) में 128 जनित्र हैं प्रारम्भिक तत्वों की संख्या देखें। एक परिमित क्षेत्र के लिए एक जनित्र के रूप में x का होना कई संगणनात्मक गणितीय फलनों के लिए लाभदायक है।

जोड़ना और घटाना

इन बहुपदों में से दो को एक साथ जोड़कर या घटाकर जोड़ और घटाना किया जाता है, और परिणाम मापांक को कम करके विशेषता को कम किया जाता है।

विशेषता 2 के साथ परिमित क्षेत्र में, अतिरिक्त मापांक 2, व्यवकलन मापांक 2, और एक्सओआर समान हैं। इस प्रकार,

बहुपदीय	(x6 + x4 + x + 1) + (x7 + x6 + x3 + x) = x7 + x4 + x3 + 1
बाइनरी	{01010011} + {11001010} = {10011001}
हेक्साडेसिमल	{53} + {CA} = {99}

बहुपदों के नियमित संकलन के अंतर्गत, योग में 2x⁶ पद होगा। यह पद 0x⁶ हो जाता है और उत्तर कम होने पर मापांक 2 को हटा दिया जाता है।

यहां सामान्य बीजगणितीय योग और कुछ बहुपदों की विशेषता 2 परिमित क्षेत्र योग दोनों के साथ एक सारणी है

p1	p2	p1 + p2 के अंतर्गत
		K[x]	GF(2n)
x3 + x + 1	x3 + x2	2x3 + x2 + x + 1	x2 + x + 1
x4 + x2	x6 + x2	x6 + x4 + 2x2	x6 + x4
x + 1	x2 + 1	x2 + x + 2	x2 + x
x3 + x	x2 + 1	x3 + x2 + x + 1	x3 + x2 + x + 1
x2 + x	x2 + x	2x2 + 2x	0

कंप्यूटर विज्ञान अनुप्रयोगों में, विशेषता 2 के परिमित क्षेत्रों के लिए संचालन को सरल किया जाता है, जिसे GF(2ⁿ) गैलोज़ क्षेत्र भी कहा जाता है, जिससे ये क्षेत्र अनुप्रयोगों के लिए विशेष रूप से लोकप्रिय विकल्प बन जाते हैं।

गुणन

परिमित क्षेत्र में गुणन गुणन तुल्यता संबंध परिमित क्षेत्र को परिभाषित करने के लिए उपयोग किया जाने वाला एक अलघुकरणीय बहुपद अपचायक बहुपद है। अर्थात्, यह गुणन है जिसके बाद भाजक के रूप में घटते हुए बहुपद का उपयोग करते हुए विभाजन होता है—शेष गुणनफल होता है। प्रतीक • का उपयोग परिमित क्षेत्र में गुणन को निरूपित करने के लिए किया जा सकता है।

रिजंडैल (एईएस) परिमित क्षेत्र

रिजेंडेल (एईएस के रूप में मानकीकृत) 256 तत्वों के साथ विशेषता 2 परिमित क्षेत्र का उपयोग करता है, जिसे गैलोइस क्षेत्र GF(2⁸) भी कहा जा सकता है। यह गुणन के लिए निम्न बहुपद को कम करने का प्रयोग करता है:

x⁸ + x⁴ + x³ + x + 1.

उदाहरण के लिए, रिजेंडेल के क्षेत्र में {53} • {CA} = {01} क्योंकि

	(x6 + x4 + x + 1)(x7 + x6 + x3 + x)
=	(x13 + x12 + x9 + x7) + (x11 + x10 + x7 + x5) + (x8 + x7 + x4 + x2) + (x7 + x6 + x3 + x)
=	x13 + x12 + x9 + x11 + x10 + x5 + x8 + x4 + x2 + x6 + x3 + x
=	x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x

और

	x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x mod x8 + x4 + x3 + x1 + 1
=	(11111101111110 mod 100011011)
=	{3F7E mod 11B} = {01}
=	1 (decimal)

उत्तरार्द्ध को विस्तृत विभाजन के माध्यम से प्रदर्शित किया जा सकता है बाइनरी संकेतन का उपयोग करके दिखाया गया है, क्योंकि यह फलन को अच्छी तरह से प्रदान करता है। ध्यान दें कि विशेष OR को उदाहरण में प्रयुक्त किया गया है और अंकगणितीय व्यवकलन नहीं है, जैसा कि कोई प्राथमिक-स्कूल विस्तृत विभाजन में उपयोग कर सकता है।:

 11111101111110 (mod) 100011011
 ^100011011 
 01110000011110
 ^100011011 
 0110110101110
 ^100011011 
 010101110110
 ^100011011 
 00100011010
 ^100011011 
 000000001

तत्व {53} और {CA} एक दूसरे के गुणात्मक व्युत्क्रम हैं क्योंकि उनका गुणनफल 1 है।

इस विशेष परिमित क्षेत्र में गुणा "कृषक एल्गोरिथ्म" के एक संशोधित संस्करण का उपयोग करके भी किया जा सकता है। प्रत्येक बहुपद को उपरोक्त के समान बाइनरी संकेत का उपयोग करके दर्शाया गया है। आठ बिट पर्याप्त हैं क्योंकि प्रत्येक (कम) बहुपद के संदर्भ में केवल घात 0 से 7 संभव हैं।

यह एल्गोरिदम तीन चर (कंप्यूटर प्रोग्रामिंग अर्थ में) का उपयोग करता है, प्रत्येक में आठ-बिट प्रतिनिधित्व होता है। a और b को गुना के साथ आरंभ किया जाता है; p गुणनफल को संग्रहीत करता है और इसे 0 से प्रारंभ किया जाना चाहिए।

एल्गोरिदम के प्रारंभ और अंत में, और प्रत्येक पुनरावृत्ति के प्रारंभ और अंत में, यह अपरिवर्तनीय (कंप्यूटर विज्ञान) सत्य है: a b + p गुणनफल है। एल्गोरिदम प्रारंभ होने पर यह स्पष्ट रूप से सत्य है। जब एल्गोरिदम समाप्त हो जाता है, तो a या b शून्य होगा इसलिए p में गुणनफल होगा।

• निम्नलिखित लूप को आठ बार (प्रति बिट एक बार) सक्रिय करे। पुनरावृत्ति से पहले a या b शून्य होने पर रोकना सही है:

1. यदि b का सबसे दाहिना बिट विशेष या गुणन p को a के मान से निर्धारित किया गया है। यह बहुपद जोड़ है। edit
2. b को एक बिट को दाईं ओर विस्थापित करें, सबसे दाहिने बिट को हटा दें, और बाईं ओर के बिट को शून्य मान दें। यह x⁰ पद को हटाते हुए बहुपद को x से विभाजित करता है।
3. इस बात पर ध्यान रखें कि क्या बाईं ओर का बिट a पर समायोजित है और इस मान को घात कहते हैं।
4. a बिट को बाईं ओर विस्थापित करें, सबसे बाएं बिट को हटा दें, और नए को सबसे दाएं बिट को शून्य बना दें। यह बहुपद को x से गुणा करता है, लेकिन हमें अभी भी घात की गणना करनी होगी जो x7 के गुणांक का प्रतिनिधित्व करता है।
5. यदि घात का मान एक, विशेष या हेक्साडेसिमल संख्या 0x1b (बाइनरी में 00011011) के साथ होता है। 0x1b अलघुकरणीय बहुपद से समान है जिसमें उच्च पद का हटाया जाता है। संकल्पनात्मक रूप से, अलघुकरणीय बहुपद का उच्च पद और मॉड्यूल 2 से 0 जोड़ते हैं।

• p के पास गुणन है

यह एल्गोरिथ्म विशेषता 2 के अन्य क्षेत्रों में गुणा करने के लिए आसानी से सामान्यीकृत करता है, a, b, और p की लंबाई और मान 0x1b को उपयुक्त रूप से बदलता है।

गुणात्मक प्रतिलोम

See also: इटोह-त्सुजी प्रतिलोम एल्गोरिथ्म

एक परिमित क्षेत्र के तत्व a के गुणक व्युत्क्रम की गणना कई अलग-अलग तरीकों से की जा सकती है:

• क्षेत्र में प्रत्येक संख्या से गुणा करके जब तक गुणन एक न हो जाए। यह एक पशु बल खोज है।
• चूंकि GF(pⁿ) के शून्येतर तत्व गुणा के संबंध में एक परिमित समूह बनाते हैं, a^pn−1 = 1 ( a ≠ 0 के लिए), इस प्रकार a का व्युत्क्रम a^pn−2 है।
• विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके प्राप्त करता है।
• परिमित क्षेत्र के लिए लघुगणक और घातांक सारणी बनाकर, pn − 1 से लघुगणक घटाकर और परिणाम को घातांक बनाता है।
• परिमित क्षेत्र के लिए एक मॉड्यूलर गुणक व्युत्क्रम सारणी बनाकर और जांच कर रहा है।
• एक समग्र क्षेत्र में मानचित्रण करके जहां प्रतिलोम सरल होता है, और वापस मानचित्रण करता है।
• अभाज्य कोटि के परिमित क्षेत्र की स्थितियों में एक विशेष पूर्णांक का निर्माण करके या गैर-अभाज्य क्रम के परिमित क्षेत्र की स्थितियों में एक विशेष बहुपद का निर्माण करके और इसे a से विभाजित करके प्राप्त किया जाता है।

कार्यान्वयन युक्ति

जनित्र आधारित सारणी

छोटे गैलोइस क्षेत्रों पर गैलोइस क्षेत्र गणना के लिए एल्गोरिदम विकसित करते समय, एक सामान्य प्रदर्शन अनुकूलन दृष्टिकोण जनित्र g को जाँचना और पहचान का उपयोग करना है:

$ab=g^{\log _{g}(ab)}=g^{\log _{g}(a)+\log _{g}(b)}$

log_g(a) और g^y फलनों और एक पूर्णांक जोड़ संक्रिया के लिए सारणी जांच के अनुक्रम के रूप में गुणन को कार्यान्वित करने के लिए है। यह उस गुण का उपयोग करता है जिसमें प्रत्येक परिमित क्षेत्र में जनित्र होते हैं। रिजेंडेल क्षेत्र के उदाहरण में, बहुपद x + 1 (या {03}) एक ऐसा जनित्र है। एक बहुपद के जनित्र होने के लिए एक आवश्यक लेकिन पर्याप्त शर्त नहीं है कि वह अलघुकरणीय हो।

a या b के शून्य होने के विशेष स्थितियों के लिए एक कार्यान्वयन का परीक्षण होना चाहिए, क्योंकि गुणनफल भी शून्य होगा।

पहचान के साथ गुणात्मक व्युत्क्रम निर्धारित करने के लिए इसी योजना का उपयोग किया जा सकता है:

$a^{-1}=g^{\log _{g}\left(a^{-1}\right)}=g^{-\log _{g}(a)}=g^{|g|-\log _{g}(a)}$

यहाँ, जनित्र का क्रम (समूह सिद्धांत), |g|, क्षेत्र के गैर-शून्य तत्वों की संख्या है। GF(2⁸) की स्थितियों में यह 28 − 1 = 255 है। अर्थात, रिजेंडेल उदाहरण के लिए: (x + 1)²⁵⁵ = 1 है। तो यह दो अवलोकन सारणी और एक पूर्णांक व्यवकलन के साथ किया जा सकता है। घातांक के लिए इस विचार का उपयोग करने से भी लाभ मिलता है:

$a^{n}=g^{\log _{g}\left(a^{n}\right)}=g^{n\log _{g}(a)}=g^{n\log _{g}(a){\pmod {|g|}}}$

इसके लिए दो सारणी अवलोकन, एक पूर्णांक गुणन और एक पूर्णांक मापांक संक्रिया की आवश्यकता होती है। विशेष स्थितियों के लिए पुनः एक परीक्षण a = 0 किया जाना चाहिए।

हालाँकि, क्रिप्टोग्राफ़िक कार्यान्वयन में, ऐसे कार्यान्वयन से सावधान रहना होगा क्योंकि कई माइक्रोप्रोसेसरों के सीपीयू कैश मेमोरी अभिगम्य के लिए परिवर्तनशील समय की ओर ले जाते हैं। इससे ऐसे कार्यान्वयन हो सकते हैं जो समय आक्षेप के प्रति संवेदनशील हैं।

घात-रहित गुणा

बाइनरी क्षेत्र्स GF(2n) के लिए, क्षेत्र गुणन को घात-रहित गुणन जैसे सीएलएमयूएल निर्देश समुच्चय का उपयोग करके कार्यान्वित किया जा सकता है, जो n ≤ 64 के लिए अच्छा है। एक गुणन एक उत्पाद का उत्पादन करने के लिए एक घात-रहित गुणा (2n - 1 बिट तक) का उपयोग करता है, भागफल = ⌊उत्पाद / (क्षेत्र बहुपद)⌋, क्षेत्र बहुपद द्वारा भागफल का गुणा, फिर एक xor: परिणाम = उत्पाद ⊕ ((क्षेत्र बहुपद) ⌊उत्पाद / (क्षेत्र बहुपद)⌋) उत्पन्न करने के लिए क्षेत्र बहुपद के पूर्व-गणना किए गए व्युत्क्रम का एक अन्य घात-रहित गुणा है। पिछले 3 चरणों (पीसीएलएमयूएलक्यूडीक्यू, पीसीएलएमयूएलक्यूडीक्यू,, xor) का उपयोग x86 पीसीएलएमयूएलक्यूडीक्यू निर्देश का उपयोग करके सीआरसी की तेजी से गणना के लिए बैरेट न्यून चरण में किया जाता है।

संयुक्त क्षेत्र

जब k एक सम्मिश्र संख्या है, तो बाइनरी क्षेत्र GF(2^k) से इसके एक उपक्षेत्र के विस्तार क्षेत्र, अर्थात GF((2^m)ⁿ) में समरूपता सम्मिलित होगी, जहाँ k = m n है। इन समरूपताओं में से एक का उपयोग गणितीय विचारों को सरल बना सकता है क्योंकि विस्तार की घात समंजन के साथ छोटी होती है कि तत्वों को अब एक बड़े उपक्षेत्र में दर्शाया जाता है। हार्डवेयर कार्यान्वयन के लिए गेट गणना को कम करने के लिए, प्रक्रिया में कई नेस्टिंग सम्मिलित हो सकते हैं, जैसे GF(2⁸) to GF(((2²)²)²) में मानचित्रित होती है। एक कार्यान्वयन बाधा है, दो अभ्यावेदन में संचालन संगत होना चाहिए, इसलिए समरूपता के स्पष्ट उपयोग की आवश्यकता है। अधिक सटीक रूप से, समरूपता को मानचित्र () द्वारा निरूपित किया जाएगा, यह एक आक्षेप है जो GF(2^k) के एक तत्व को GF((2^m)ⁿ) में मानचित्रित करता है, परिणामस्वरूप: map(a + b) = map(a) + map(b) और map(a b) = map(a) map(b) जहां मानचित्रण से पहले GF(2^k) में बाईं ओर के संचालन होते हैं और मानचित्रण के बाद दाईं ओर के संचालन GF((2^m)ⁿ) में होते हैं। समाकृतिकता को सामान्य रूप से k बिट आव्यूह द्वारा k रो के साथ प्रयुक्त किया जाता है, जिसका उपयोग GF(2^k) के एक तत्व के GF (2) से गुणा करने के लिए किया जाता है, जिसे 1 बिट आव्यूह द्वारा k रो के रूप में माना जाता है। α को GF(2^k) के प्रारम्भिक तत्व के रूप में परिभाषित करें, और β को GF((2^m)ⁿ) के प्रारम्भिक तत्व तब β^j = map(α^j) और map⁻¹(β^j) के रूप में परिभाषित करें। Α और β के मान मानचित्रण आव्यूह और इसके व्युत्क्रम को निर्धारित करते हैं। चूंकि वास्तविक गणित GF((2^m)ⁿ) में किया जाता है, GF((2^m)ⁿ) के लिए कम करने वाला बहुपद सामान्य रूप से प्रारम्भिक होता है और GF((2^m)ⁿ) में β = x होता है। जोड़ और गुणा के लिए अनुकूलता बाधा को पूरा करने के लिए, GF(2^k) के किसी भी प्रारम्भिक तत्व α को चयन करने के लिए खोज की जाती है जो बाधा को पूरा करेगा। ऐसी स्थितियों में जहां GF(2^k) के लिए बहुपद को कम करना प्रारम्भिक है, एक वैकल्पिक मानचित्रण विधि संभव है: GF(2^k) के लिए कम करने वाले बहुपद के 1 बिट गुणांक की व्याख्या GF(2m) के m बिट तत्वों 0 या 1 के रूप में की जाती है, और घात n के m प्रारम्भिक कारक होंगे, जिनमें से कोई भी GF((2^m)ⁿ) के लिए कम करने वाले बहुपद के रूप में उपयोग किया जा सकता है। एक समग्र क्षेत्र में मानचित्रण को GF(p^k) को किसी भी अभाज्य के लिए GF((p^m)ⁿ) जैसे समग्र क्षेत्र में मानचित्रण करने के लिए सामान्यीकृत किया जा सकता है।

प्रोग्राम उदाहरण

C (प्रोग्रामिंग भाषा)

यहाँ कुछ C (प्रोग्रामिंग भाषा) कोड दिया गया है जो क्रम 2 की विशेषता 2 परिमित क्षेत्र में संख्याओं को जोड़ और गुणा करेगा⁸, उदाहरण के लिए रिजेंडेल एल्गोरिथम या रीड-सोलोमन द्वारा उपयोग किया जाता है, रूसी कृषक गुणन एल्गोरिथ्म का उपयोग करते हुए:

/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the modulo polynomial relation x^8 + x^4 + x^3 + x + 1 = 0
 * (the other way being to do carryless multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* accumulator for the product of the multiplication */
	while (a != 0 && b != 0) {
        if (b & 1) /* if the polynomial for b has a constant term, add the corresponding a to p */
            p ^= a; /* addition in GF(2^m) is an XOR of the polynomial coefficients */

        if (a & 0x80) /* GF modulo: if a has a nonzero term x^7, then must be reduced when it becomes x^8 */
            a = (a << 1) ^ 0x11b; /* subtract (XOR) the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
        else
            a <<= 1; /* equivalent to a*x */
        b >>= 1;
	}
	return p;
}

इस उदाहरण में कैशे, समय, और शाखा भविष्यवाणी पार्श्व-प्रणाली प्रदर्शित है, और क्रिप्टोग्राफी में उपयोग के लिए उपयुक्त नहीं है।

D प्रोग्रामिंग उदाहरण

यह D (प्रोग्रामिंग भाषा) प्रोग्राम रिजेंडेल के परिमित क्षेत्र में संख्याओं को गुणा करेगा और पीजीएम छवि उत्पन्न करेगा:

/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}

पार्श्व-प्रणाली से संरक्षण के लिए यह उदाहरण किसी भी शाखा या सारणी अवलोकन का उपयोग नहीं करता है और इसलिए क्रिप्टोग्राफी में उपयोग के लिए उपयुक्त है।

यह भी देखें

• ज़ेच का लघुगणक

स्रोत

• Lidl, Rudolf; Niederreiter, Harald (1983), Finite Fields, Addison-Wesley, ISBN 0-201-13519-1 (कैम्ब्रिज यूनिवर्सिटी प्रेस द्वारा 1984 में पुनः जारी ISBN 0-521-30240-4).
• Mullen, Gary L.; Panario, Daniel (2013), Handbook of Finite Fields, CRC Press, ISBN 978-1-4398-7378-6

बाहरी संबंध

• Gordon, G. (1976). "Very simple method to find the minimum polynomial of an arbitrary nonzero element of a finite field". Electronics Letters. 12 (25): 663–664. doi:10.1049/el:19760508.
• da Rocha, V. C.; Markarian, G. (2006). "Simple method to find trace of arbitrary element of a finite field". Electronics Letters. 42 (7): 423–325. doi:10.1049/el:20060473.
• Trenholme, Sam. "AE's Galois field".
• Planck, James S. (2007). "Fast Galois Field Arithmetic Library in C/C++".
• Wikiversity: Reed–Solomon for Coders – Finite Field Arithmetic