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

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

अपरिमित रूप से अनेक भिन्न परिमित क्षेत्र हैं। उनके तत्वों की संख्या आवश्यक रूप से 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

b को एक बिट को दाईं ओर शिफ्ट करें, सबसे दाहिने बिट को हटा दें, और बाईं ओर के बिट को शून्य मान दें। यह x0 पद को हटाते हुए बहुपद को x से विभाजित करता है।

इस बात पर नज़र रखें कि क्या बाईं ओर का बिट एक पर समायोजित है और इस वैल्यू को कैरी करें।

एक बिट को बाईं ओर शिफ्ट करें, सबसे बाएं बिट को हटा दें, और नए को सबसे दाएं बिट को शून्य बना दें। यह बहुपद को x से गुणा करता है, लेकिन हमें अभी भी कैरी का हिसाब रखना होगा जो x7 के गुणांक का प्रतिनिधित्व करता है।

यदि कैरी का मान एक, विशेष या हेक्साडेसिमल संख्या 0x1b (बाइनरी में 00011011) के साथ होता है। 0x1b अलघुकरणीय बहुपद से मेल खाता है जिसमें उच्च पद का सफाया हो जाता है। संकल्पनात्मक रूप से, अलघुकरणीय बहुपद का उच्च पद और मॉड्यूल 2 से 0 जोड़ते हैं।

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

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

गुणक व्युत्क्रम

See also: Itoh–Tsujii inversion algorithm

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

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

कार्यान्वयन के गुर

जेनरेटर आधारित टेबल

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

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

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

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

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

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

यहाँ, जनरेटर का क्रम (समूह सिद्धांत), |g|, क्षेत्र के गैर-शून्य तत्वों की संख्या है। जीएफ के स्थितियों में (2⁸) यह है 2⁸ − 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 किया जाना चाहिए।

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

कैरीलेस गुणा

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

समग्र क्षेत्र

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

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

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

यहाँ कुछ 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;
}

इस उदाहरण में टाइमिंग अटैक | कैश, टाइमिंग, और ब्रांच प्रेडिक्शन साइड-चैनल लीक है, और क्रिप्टोग्राफी में उपयोग के लिए उपयुक्त नहीं है।

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

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

/**
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