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

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

असीम रूप से कई अलग-अलग परिमित क्षेत्र हैं। उनकी प्रमुखता अनिवार्य रूप से 'पी' के रूप में हैⁿ जहां p एक अभाज्य संख्या है और n एक धनात्मक पूर्णांक है, और समान आकार के दो परिमित क्षेत्र समरूपता हैं। अभाज्य p को क्षेत्र की विशेषता (बीजगणित) कहा जाता है, और धनात्मक पूर्णांक n को इसकी विशेषता (बीजगणित) # क्षेत्रों के स्थितियों में क्षेत्र का आयाम (सदिश समष्टि) कहा जाता है।

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

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

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

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

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

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

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

Polynomial	x⁶ + x⁴ + x + 1
Binary	{01010011}
Hexadecimal	{53}

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

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

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

निम्नलिखित उदाहरणों में यह सबसे अच्छा है कि बहुपद निरूपण का उपयोग अर्थ के रूप में न किया जाए $x$ उदाहरणों के बीच परिवर्तन। मोनिक इरेड्यूसिबल बहुपद $x 8 + x 4 + x 3 + x + 1$ GF(2) से अधिक प्राथमिक नहीं है। होने देना $λ$ इस बहुपद की जड़ हो (बहुपद प्रतिनिधित्व में यह होगा $x$ ), वह है, $λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . अब $λ 51 = 1$ , इसलिए $λ$ GF का प्राथमिक तत्व नहीं है (2⁸) और क्रम 51 का गुणक उपसमूह उत्पन्न करता है।^[4] फील्ड तत्व पर विचार करें $λ + 1$ (बहुपद प्रतिनिधित्व में यह होगा $x + 1$ ). अब $(λ +1) 8 + (λ +1) 4 + (λ +1) 3 + (λ +1) 2 + 1 = λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . चूंकि इस प्राथमिक बहुपद की सभी जड़ें प्राथमिक तत्व हैं, $λ + 1$ GF का प्राथमिक तत्व है (2⁸) ( $(λ + 1) 255 = 1$ और कोई छोटी घात नहीं है)। जीएफ (2⁸) में 128 जनरेटर हैं (देखें प्राथमिक तत्व (परिमित क्षेत्र)#प्राथमिक तत्वों की संख्या)। रखना $x$ एक परिमित क्षेत्र के लिए एक जनरेटर के रूप में कई कम्प्यूटेशनल गणितीय कार्यों के लिए लाभदायक है।

जोड़ और घटाव

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

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

Polynomial	(x⁶ + x⁴ + x + 1) + (x⁷ + x⁶ + x³ + x) = x⁷ + x⁴ + x³ + 1
Binary	{01010011} + {11001010} = {10011001}
Hexadecimal	{53} + {CA} = {99}

बहुपदों के नियमित जोड़ के तहत योग में 2x शब्द होगा^{6</उप>। यह शब्द 0x बन जाता है⁶ और जब उत्तर घटाया जाता है तो मॉड्यूल 2 को छोड़ दिया जाता है।}

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

p₁	p₂	p₁ + p₂ under...
p₁	p₂	K[x]	GF(2ⁿ)
x³ + x + 1	x³ + x²	2x³ + x² + x + 1	x² + x + 1
x⁴ + x²	x⁶ + x²	x⁶ + x⁴ + 2x²	x⁶ + x⁴
x + 1	x² + 1	x² + x + 2	x² + x
x³ + x	x² + 1	x³ + x² + x + 1	x³ + x² + x + 1
x² + x	x² + x	2x² + 2x	0

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

गुणन

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

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

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

एक्स⁸ + एक्स⁴ + x³ + x + 1।

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

	(x⁶ + x⁴ + x + 1)(x⁷ + x⁶ + x³ + x)
=	(x¹³ + x¹² + x⁹ + x⁷) + (x¹¹ + x¹⁰ + x⁷ + x⁵) + (x⁸ + x⁷ + x⁴ + x²) + (x⁷ + x⁶ + x³ + x)
=	x¹³ + x¹² + x⁹ + x¹¹ + x¹⁰ + x⁵ + x⁸ + x⁴ + x² + x⁶ + x³ + x
=	x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + x² + x

और

	x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + x² + x mod x⁸ + x⁴ + x³ + x¹ + 1
=	(11111101111110 mod 100011011)
=	{3F7E mod 11B} = {01}
=	1 (decimal)

उत्तरार्द्ध को लंबे विभाजन के माध्यम से प्रदर्शित किया जा सकता है (द्विआधारी संकेतन का उपयोग करके दिखाया गया है, क्योंकि यह कार्य के लिए अच्छी तरह से उधार देता है। ध्यान दें कि विशेष या # सत्य तालिका उदाहरण में लागू होती है और अंकगणितीय घटाव नहीं, जैसा कि कोई ग्रेड-स्कूल लंबे विभाजन में उपयोग कर सकता है। .):

         <यू> </यू>
          11111101111110 (आधुनिक) 100011011
         <यू>^100011011 </यू>
          01110000011110
          ^<यू>100011011</यू>
           0110110101110
           <यू>^100011011 </यू>
            010101110110
            <यू>^100011011 </यू>
             00100011010
              <यू>^100011011 </यू>
               000000001

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

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

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

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

निम्नलिखित लूप को आठ बार चलाएं (प्रति बिट एक बार)। पुनरावृत्ति से पहले a या b शून्य होने पर रोकना ठीक है:
1. यदि b का सबसे दाहिना बिट सेट किया गया है, अनन्य या उत्पाद p a के मान से। यह बहुपद जोड़ है।
# एक बिट को दाईं ओर शिफ्ट करें, सबसे दाहिने बिट को हटा दें, और बाईं ओर के बिट को शून्य मान दें। यह x को हटाते हुए बहुपद को x से विभाजित करता है⁰ अवधि।
1. इस बात का ध्यान रखें कि क्या बाईं ओर का बिट एक पर सेट है और इस मान को कैरी करें।
2. एक बिट को बाईं ओर शिफ्ट करें, सबसे बाएं बिट को हटा दें, और नए को सबसे दाएं बिट को शून्य बना दें। यह बहुपद को x से गुणा करता है, लेकिन हमें अभी भी कैरी का हिसाब रखना होगा जो x के गुणांक का प्रतिनिधित्व करता है।^{7</उप>।}
3. यदि कैरी का मान एक, अनन्य या हेक्साडेसिमल संख्या के साथ था 0x1b (00011011 बाइनरी में)। 0x1b अलघुकरणीय बहुपद के संगत उच्च पद को समाप्त कर दिया गया है। संकल्पनात्मक रूप से, अलघुकरणीय बहुपद का उच्च पद और मॉड्यूल 2 से 0 जोड़ते हैं।
p के पास अब गुणनफल है

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

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

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

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

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

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

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

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 की तीव्र संगणना के लिए बैरेट रिडक्शन चरण में किया जाता है।^[6]

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

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

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

यह भी देखें

जेक का लघुगणक

संदर्भ

↑ The roots of such a polynomial must lie in an extension field of GF( $q$ ) since the polynomial is irreducible, and so, has no roots in GF( $q$ ).
↑ Mullen & Panario 2013, p. 17
↑ प्रयोगों का डिजाइन और विश्लेषण. John Wiley & Sons, Ltd. August 8, 2005. pp. 716–720. doi:10.1002/0471709948.app1.
↑ Lidl & Niederreiter 1983, p. 553
↑ Grošek, O.; Fabšič, T. (2018), "Computing multiplicative inverses in finite fields by long division" (PDF), Journal of Electrical Engineering, 69 (5): 400–402, doi:10.2478/jee-2018-0059, S2CID 115440420
↑ "PCLMULQDQ निर्देश का उपयोग करके सामान्य बहुपदों के लिए तेज़ CRC संगणना" (PDF). www.intel.com. 2009. Retrieved 2020-08-08.
↑ "Efficient Software Implementations of Large FiniteFieldsGF(2n) for Secure Storage Applications" (PDF). www.ccs.neu.edu. Retrieved 2020-08-08.
↑ "bpdegnan/aes". GitHub.
↑ [1]^{[dead link]}

स्रोत

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

[1] The roots of such a polynomial must lie in an extension field of GF( $q$ ) since the polynomial is irreducible, and so, has no roots in GF( $q$ ).

[2] Mullen & Panario 2013, p. 17

[3] प्रयोगों का डिजाइन और विश्लेषण. John Wiley & Sons, Ltd. August 8, 2005. pp. 716–720. doi:10.1002/0471709948.app1.

[LN-4] Lidl & Niederreiter 1983, p. 553

[5] Grošek, O.; Fabšič, T. (2018), "Computing multiplicative inverses in finite fields by long division" (PDF), Journal of Electrical Engineering, 69 (5): 400–402, doi:10.2478/jee-2018-0059, S2CID 115440420

[6] "PCLMULQDQ निर्देश का उपयोग करके सामान्य बहुपदों के लिए तेज़ CRC संगणना" (PDF). www.intel.com. 2009. Retrieved 2020-08-08.

[7] "Efficient Software Implementations of Large FiniteFieldsGF(2n) for Secure Storage Applications" (PDF). www.ccs.neu.edu. Retrieved 2020-08-08.

[8] "bpdegnan/aes". GitHub.

[9] [1]^{[dead link]}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

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

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

जोड़ और घटाव

गुणन

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

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

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

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

कैरीलेस गुणा

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

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

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

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

यह भी देखें

संदर्भ

स्रोत

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

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

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

जोड़ और घटाव

गुणन

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

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

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

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

कैरीलेस गुणा

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

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

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

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

यह भी देखें

संदर्भ

स्रोत

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories