परिमित क्षेत्र: Difference between revisions
No edit summary |
No edit summary |
||
Line 234: | Line 234: | ||
गैर-शून्य तत्वों का सेट {{math|GF(''q'')}} गुणन के तहत एक [[ एबेलियन समूह ]] है, क्रम {{math|''q'' – 1}} लैग्रेंज के प्रमेय (समूह सिद्धांत) द्वारा | लैग्रेंज की प्रमेय के अनुसार, एक भाजक मौजूद है ''q'' – 1 का एक भाजक {{math|''k''}} ऐसा है कि {{math|1=''x<sup>k</sup>'' = 1}} प्रत्येक गैर-शून्य {{math|''x''}} के लिए {{math|GF(''q'')}} में । चूंकि समीकरण {{math|1=''x<sup>k</sup>'' = 1}} का किसी भी क्षेत्र में अधिक से अधिक {{math|''k''}} हल हैं, {{math|''q'' – 1}}, {{math|''k''}} के लिए उच्चतम संभव मान है। परिमित एबेलियन समूहों # की संरचना प्रमेय का तात्पर्य है कि यह गुणात्मक समूह चक्रीय समूह है, अर्थात सभी गैर-शून्य तत्व एक ही तत्व की घात हैं। सारांश: | गैर-शून्य तत्वों का सेट {{math|GF(''q'')}} गुणन के तहत एक [[ एबेलियन समूह ]] है, क्रम {{math|''q'' – 1}} लैग्रेंज के प्रमेय (समूह सिद्धांत) द्वारा | लैग्रेंज की प्रमेय के अनुसार, एक भाजक मौजूद है ''q'' – 1 का एक भाजक {{math|''k''}} ऐसा है कि {{math|1=''x<sup>k</sup>'' = 1}} प्रत्येक गैर-शून्य {{math|''x''}} के लिए {{math|GF(''q'')}} में । चूंकि समीकरण {{math|1=''x<sup>k</sup>'' = 1}} का किसी भी क्षेत्र में अधिक से अधिक {{math|''k''}} हल हैं, {{math|''q'' – 1}}, {{math|''k''}} के लिए उच्चतम संभव मान है। परिमित एबेलियन समूहों # की संरचना प्रमेय का तात्पर्य है कि यह गुणात्मक समूह चक्रीय समूह है, अर्थात सभी गैर-शून्य तत्व एक ही तत्व की घात हैं। सारांश: | ||
{{block indent | em = 1.5 | text = ''The multiplicative group of the non-zero elements in'' {{math|GF(''q'')}} ''is cyclic, and there exists an element'' {{math|''a''}}, ''such that the'' {{math|''q'' – 1}} ''non-zero elements of'' {{math|GF(''q'')}} ''are'' {{math|1= ''a'', ''a''<sup>2</sup>, ..., ''a''<sup>''q''−2</sup>, ''a''<sup>''q''−1</sup> = 1}}.}} | {{block indent | em = 1.5 | text = ''The multiplicative group of the non-zero elements in'' {{math|GF(''q'')}} ''is cyclic, and there exists an element'' {{math|''a''}}, ''such that the'' {{math|''q'' – 1}} ''non-zero elements of'' {{math|GF(''q'')}} ''are'' {{math|1= ''a'', ''a''<sup>2</sup>, ..., ''a''<sup>''q''−2</sup>, ''a''<sup>''q''−1</sup> = 1}}.}} | ||
ऐसे तत्व {{math|''a''}} अभाज्य तत्व कहलाते हैं। जब तक {{math|1=''q'' = 2, 3}}, अभाज्य तत्व अद्वितीय | ऐसे तत्व {{math|''a''}} अभाज्य तत्व कहलाते हैं। जब तक {{math|1=''q'' = 2, 3}}, अभाज्य तत्व अद्वितीय नहीं है। अभाज्य तत्वों की संख्या {{math|''φ''(''q'' − 1)}} है जहां {{math|''φ''}} '''यूलर का टोटिएंट फलन''' है। | ||
उपरोक्त परिणाम का तात्पर्य है कि {{math|GF(''q'')}} में प्रत्येक {{math|''x''}} के लिए {{math|1=''x<sup>q</sup>'' = ''x''}} । विशेष स्थिति जहां {{math|''q''}} अभाज्य है, फर्मेट की छोटी प्रमेय है। | उपरोक्त परिणाम का तात्पर्य है कि {{math|GF(''q'')}} में प्रत्येक {{math|''x''}} के लिए {{math|1=''x<sup>q</sup>'' = ''x''}} । विशेष स्थिति जहां {{math|''q''}} अभाज्य है, फर्मेट की छोटी प्रमेय है। | ||
Line 330: | Line 330: | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
क्रिप्टोग्राफी में, परिमित क्षेत्रों में या [[ अण्डाकार वक्र ]]ों में [[ असतत लघुगणक समस्या ]] की कठिनाई कई व्यापक रूप से उपयोग किए जाने वाले प्रोटोकॉल का आधार है, जैसे कि डिफी-हेलमैन प्रोटोकॉल। उदाहरण के लिए, 2014 में, विकिपीडिया के लिए एक सुरक्षित इंटरनेट कनेक्शन में एक बड़े परिमित क्षेत्र में अण्डाकार वक्र डिफी-हेलमैन प्रोटोकॉल ([[ ECDHE ]]) शामिल था।<ref>This can be verified by looking at the information on the page provided by the browser.</ref> कोडिंग सिद्धांत में, कई कोड परिमित क्षेत्रों में वेक्टर रिक्त स्थान के [[ रैखिक उप-स्थान ]] के रूप में बनाए जाते हैं। | क्रिप्टोग्राफी में, परिमित क्षेत्रों में या [[ अण्डाकार वक्र ]]ों में [[ असतत लघुगणक समस्या ]] की कठिनाई कई व्यापक रूप से उपयोग किए जाने वाले प्रोटोकॉल का आधार है, जैसे कि डिफी-हेलमैन प्रोटोकॉल। उदाहरण के लिए, 2014 में, विकिपीडिया के लिए एक सुरक्षित इंटरनेट कनेक्शन में एक बड़े परिमित क्षेत्र में अण्डाकार वक्र डिफी-हेलमैन प्रोटोकॉल ([[ ECDHE ]]) शामिल था।<ref>This can be verified by looking at the information on the page provided by the browser.</ref> कोडिंग सिद्धांत में, कई कोड परिमित क्षेत्रों में वेक्टर रिक्त स्थान के [[ रैखिक उप-स्थान ]] के रूप में बनाए जाते हैं। | ||
कई [[ त्रुटि सुधार कोड ]] द्वारा परिमित फ़ील्ड का उपयोग किया जाता है, जैसे रीड-सोलोमन त्रुटि सुधार | रीड-सोलोमन त्रुटि सुधार कोड या [[ बीसीएच कोड ]]। परिमित क्षेत्र में लगभग हमेशा 2 की विशेषता होती है, क्योंकि कंप्यूटर डेटा बाइनरी में संग्रहीत होता है। उदाहरण के लिए, डेटा के एक बाइट की व्याख्या किस तत्व के रूप में की जा सकती है? <math>GF(2^8)</math>. एक अपवाद [[ PDF417 ]] बार कोड है, जो है <math>GF(929)</math>. कुछ सीपीयू में विशेष निर्देश होते हैं जो विशेषता 2 के परिमित क्षेत्रों के लिए उपयोगी हो सकते हैं, आमतौर पर कैरी-लेस उत्पाद की विविधताएं। | कई [[ त्रुटि सुधार कोड ]] द्वारा परिमित फ़ील्ड का उपयोग किया जाता है, जैसे रीड-सोलोमन त्रुटि सुधार | रीड-सोलोमन त्रुटि सुधार कोड या [[ बीसीएच कोड ]]। परिमित क्षेत्र में लगभग हमेशा 2 की विशेषता होती है, क्योंकि कंप्यूटर डेटा बाइनरी में संग्रहीत होता है। उदाहरण के लिए, डेटा के एक बाइट की व्याख्या किस तत्व के रूप में की जा सकती है? <math>GF(2^8)</math>. एक अपवाद [[ PDF417 ]] बार कोड है, जो है <math>GF(929)</math>. कुछ सीपीयू में विशेष निर्देश होते हैं जो विशेषता 2 के परिमित क्षेत्रों के लिए उपयोगी हो सकते हैं, आमतौर पर कैरी-लेस उत्पाद की विविधताएं। | ||
Line 357: | Line 357: | ||
==== अर्ध-बीजगणितीय बंद ==== | ==== अर्ध-बीजगणितीय बंद ==== | ||
हालांकि परिमित क्षेत्र | हालांकि परिमित क्षेत्र बीजगणितीय रूप से बंद नहीं होते हैं, वे [[ अर्ध-बीजगणितीय रूप से बंद क्षेत्र ]] होते हैं| अर्ध-बीजगणितीय रूप से बंद , जिसका अर्थ है कि परिमित क्षेत्र में प्रत्येक [[ सजातीय बहुपद ]] में एक गैर-नगण्य शून्य होता है जिसके घटक क्षेत्र में होते हैं यदि इसके चर की संख्या इसकी कोटि से अधिक है। यह [[ एमिल आर्टिन ]] और [[ लियोनार्ड यूजीन डिक्सन ]] का अनुमान था जिसे [[ क्लाउड शेवेली ]] द्वारा सिद्ध किया गया था (देखें शेवेली-चेतावनी प्रमेय)। | ||
=== वेडरबर्न की छोटी प्रमेय === | === वेडरबर्न की छोटी प्रमेय === | ||
एक विभाजन वलय ( डिवीजन रिंग ) क्षेत्र का सामान्यीकरण है। विभाजन वलय | एक विभाजन वलय ( डिवीजन रिंग ) क्षेत्र का सामान्यीकरण है। विभाजन वलय को क्रमविनिमेय (कम्यूटेटिव) नहीं माना जाता है। कोई गैर-क्रमविनिमेय परिमित विभाजन वलय नहीं हैं: वेडरबर्न की छोटी प्रमेय में कहा गया है कि सभी परिमित विभाजन वलय क्रमविनिमेय हैं, और इसलिए परिमित क्षेत्र हैं। यह परिणाम तब भी कायम रहता है जब हम [[ वैकल्पिकता | वैकल्पिक]][[ संबद्धता |ता]] के लिए [[ संबद्धता ]] की सूक्ति को शिथिल (relax) करते हैं, अर्थात, आर्टिन-ज़ोर्न प्रमेय द्वारा सभी परिमित वैकल्पिक विभाजन वलय परिमित क्षेत्र हैं।<ref>{{cite book | last=Shult | first=Ernest E. | title=अंक और रेखाएँ। शास्त्रीय ज्यामिति की विशेषता| series=Universitext | location=Berlin | publisher=[[Springer-Verlag]] | year=2011 | isbn=978-3-642-15626-7 | zbl=1213.51001 | page=123 }}</ref> | ||
Revision as of 16:05, 20 November 2022
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (February 2015) (Learn how and when to remove this template message) |
गणित में, एक परिमित क्षेत्र या गैलोइस क्षेत्र (इवरिस्ट गैलोइस के सम्मान में तथाकथित) एक क्षेत्र है जिसमें तत्वों की एक सीमित संख्या होती है। किसी भी क्षेत्र की तरह, एक परिमित क्षेत्र एक समुच्चय होता है, जिस पर गुणन, जोड़, घटाव और भाग के संचालन परिभाषित होते हैं और कुछ बुनियादी नियमों को पूरा करते हैं। परिमित क्षेत्रों के सबसे सामान्य उदाहरण पूर्णांक mod p द्वारा दिए गए हैं जब p एक अभाज्य संख्या है।
एक परिमित क्षेत्र का क्रम उसके तत्वों की संख्या है, जो या तो एक अभाज्य संख्या या एक अभाज्य घात है। प्रत्येक अभाज्य संख्या के लिए p और प्रत्येक धनात्मक पूर्णांक k के लिए क्रम के क्षेत्र हैं, जिनमें से सभी समरूपी हैं।
गणित और कंप्यूटर विज्ञान के कई क्षेत्रों में परिमित क्षेत्र मौलिक हैं, जिनमें संख्या सिद्धांत, बीजगणितीय ज्यामिति, गैलोइस सिद्धांत, परिमित ज्यामिति, क्रिप्टोग्राफी और कोडिंग सिद्धांत शामिल हैं।
गुण
एक परिमित क्षेत्र एक परिमित समुच्चय है जो एक ऐसा क्षेत्र है जिसका अर्थ है कि गुणा, जोड़, घटाव और भाग (शून्य से भाग को छोड़कर) परिभाषित हैं और क्षेत्र सिद्धांतों के रूप में ज्ञात अंकगणित के नियमों के नियमों को संतुष्ट करते हैं।
परिमित क्षेत्र के तत्वों की संख्या को उसका क्रम या कभी-कभी उसका आकार कहा जाता है। क्रम q का एक परिमित क्षेत्र उपस्थित होता है यदि q एक अभाज्य संख्या है pk (जहां p एक अभाज्य संख्या है और k एक धनात्मक पूर्णांक है)। क्रम pk के क्षेत्र में, किसी भी तत्व की p प्रतियां जोड़ने पर परिणाम हमेशा शून्य होता है अर्थात क्षेत्र की विशेषता p है।
यदि q = pk, क्रम के सभी क्षेत्र q समरूपी हैं (नीचे § अस्तित्व और अद्वितीयता देखें नीचे)।[1] इसके अतिरिक्त, एक क्षेत्र में एक ही क्रम के दो अलग-अलग परिमित उपक्षेत्र नहीं हो सकते। इसलिए सभी परिमित क्षेत्रों को एक ही क्रम से पहचाना जा सकता है और उन्हें स्पष्ट रूप से , Fq या GF(q) के रूप में निरूपित किया जाता है जहां वर्ण GF का उपयोग "गैलॉइस फील्ड" के लिए होता है।[2] q क्रम के एक परिमित क्षेत्र में, बहुपद Xq − X में परिमित क्षेत्र के सभी q तत्व मूल के रूप में होते हैं। एक परिमित क्षेत्र के गैर-शून्य तत्व एक गुणक समूह बनाते हैं। यह समूह चक्रीय समूह है, इसलिए सभी गैर-शून्य तत्वों को एक ही तत्व की घातों के रूप में व्यक्त किया जा सकता है जिसे क्षेत्र का एक पूर्वग अवयव कहा जाता है। (सामान्य तौर पर किसी दिए गए क्षेत्र के लिए कई मौलिक तत्व होंगे)
परिमित क्षेत्रों के सबसे सरल उदाहरण अभाज्य क्रम के क्षेत्र हैं: प्रत्येक अभाज्य संख्या p के लिए, (क्रम)p का अभाज्य क्षेत्र, , पूर्णांक मॉड्यूल (integers modulo) p, Z/pZ के रूप में निर्मित किया जा सकता है।
p क्रम के अभाज्य क्षेत्र के तत्वों को 0, ..., p − 1 श्रेणी में पूर्णांकों द्वारा दर्शाया जा सकता है। योग, अंतर और गुणनफल संगत पूर्णांक संक्रिया के परिणाम के p से विभाजन का शेषफल है। विस्तारित यूक्लिडीय कलनविधि का उपयोग करके किसी तत्व के गुणात्मक व्युत्क्रम की गणना की जा सकती है। (विस्तारित यूक्लिडियन कलनविधि § मॉड्यूलर पूर्णांक देखें)
मान लीजिए F एक परिमित क्षेत्र है। F में किसी भी तत्व x और किसी पूर्णांक n के लिए, n ⋅ x द्वारा x की n प्रतियों के योग को निरूपित करें। सबसे छोटा धनात्मक n ऐसा है कि n ⋅ 1 = 0 क्षेत्र की विशेषता p है। यह गुणन को परिभाषित करने की अनुमति देता है , GF(p) के एक तत्व k का F के एक तत्व x द्वारा k लिए एक पूर्णांक प्रतिनिधि (integer representative) चुनकर। यह गुणन F को GF(p)-सदिश स्थल बनाता है। यह इस प्रकार है कि किसी पूर्णांक n के लिए F के तत्वों की संख्या pn है।
फ़र्मेट की छोटी प्रमेय के अनुसार, यदि p एक अभाज्य संख्या है और x क्षेत्र GF(p) में है तो xp = x. इसका तात्पर्य समानता से है
परिमित क्षेत्र का कोई भी परिमित क्षेत्र विस्तार वियोज्य (सेपरेबल) और सरल है। अर्थात्, यदि E एक परिमित क्षेत्र है और F, E का एक उपक्षेत्र है , तो E को F से एक एकल तत्व जिसका न्यूनतम बहुपद (क्षेत्र सिद्धांत) वियोज्य है से जोड़कर प्राप्त किया जाता है। एक शब्दावली का उपयोग करने के लिए, परिमित क्षेत्र परिपूर्ण हैं।
एक अधिक सामान्य बीजगणितीय संरचना जो एक क्षेत्र की अन्य सभी सूक्तियों को संतुष्ट करती है, लेकिन जिसके गुणन को क्रमविनिमेय होने की आवश्यकता नहीं होती है, उसे विभाजन वलय या कभी-कभी विषम क्षेत्र कहा जाता है। वेडरबर्न की छोटी प्रमेय के अनुसार, कोई भी परिमित विभाजन वलय, परिवर्तन योग्य होता है और इसलिए एक परिमित क्षेत्र होता है।
अस्तित्व और विशिष्टता
मान लीजिए q = pn एक अभाज्य घात है और F बहुपद का विभाजन क्षेत्र है
विभाजक क्षेत्रों के समरूपता तक की विशिष्टता का तात्पर्य इस प्रकार है कि क्रम के सभी क्षेत्र q समरूपी हैं। इसके अलावा, यदि कोई क्षेत्र F क्रम का एक क्षेत्र है q = pk एक उपक्षेत्र के रूप में, इसके तत्व हैं q की जड़ें Xq − X, तथा F में क्रम q का कोई अन्य उपक्षेत्र नहीं हो सकता।
संक्षेप में, हमारे पास निम्नलिखित वर्गीकरण प्रमेय है जिसे पहली बार 1893 में ई. एच. मूर द्वारा सिद्ध किया गया था:[1]
एक परिमित क्षेत्र का क्रम एक अभाज्य घात है। प्रत्येक अभाज्य घात के लिए q अनुक्रम के क्षेत्र होते हैं और वे सभी समरूपी होते हैं इन क्षेत्रों में प्रत्येक तत्व संतुष्ट करता है।
और बहुपद Xq − X कारक के रूप में
यह अनुसरण करता है कि GF(pn) के लिए एक उपक्षेत्र अनुक्रम शामिल है GF(pm) यदि m, n का भाजक है उस स्थिति में, यह उपक्षेत्र अद्वितीय है। वास्तव में, बहुपद Xpm − X विभाजित Xpn − X यदि और केवल यदि m, n का भाजक है।
स्पष्ट निर्माण
गैर-अभाज्य क्षेत्र
p अभाज्य और n > 1 के साथ एक प्रमुख घात q = pn को देखते हुए, क्षेत्रGF(q) को स्पष्ट रूप से निम्नलिखित तरीके से स्पष्ट रूप से बनाया जा सकता है। सबसे पहले कोटिn के GF(p)[X] में एक अलघुकरणीय बहुपद P चुनते है (इस तरह का एक अलघुकरणीय बहुपद हमेशा मौजूद रहता है)। फिर भागफल वलय
अधिक स्पष्ट रूप से, GF(q) के तत्व GF(p) पर बहुपद हैं जिसकी कोटि निश्चित रूप से n से कम है। जोड़ और घटाना GF(p) पर बहुपदों के हैं। दो तत्वों का गुणन GF(p)[X] में P के गुणन द्वारा यूक्लिडियन विभाजन का शेषफल है। एक गैर-शून्य तत्व के गुणात्मक व्युत्क्रम की गणना विस्तारित यूक्लिडियन कलनविधि के साथ की जा सकती है; देखें विस्तारित यूक्लिडियन कलनविधि § सरल बीजगणितीय क्षेत्र विस्तार।
GF(4) के निर्माण को छोड़कर, P के लिए कई संभावित विकल्प हैं, जो समरूपी परिणाम उत्पन्न करते हैं। यूक्लिडियन विभाजन को सरल बनाने के लिए, आमतौर पर P के लिए एक बहुपद चुनता है
अगले खंडों में, हम दिखाएंगे कि ऊपर उल्लिखित सामान्य निर्माण विधि छोटे परिमित क्षेत्रों के लिए कैसे काम करती है।
चार तत्वों वाला क्षेत्र
सबसे छोटा गैर-अभाज्य क्षेत्र (non-prime field) चार तत्वों वाला क्षेत्र है, जिसे आमतौर पर GF(4) या के रूप दर्शाया जाता है इसमें चार तत्व होते हैं जैसे कि तथा प्रत्येक के लिए अन्य संक्रिया के परिणाम वितरण कानून से आसानी से निकाले जा सकते हैं। पूर्ण संक्रिया सारिणी के लिए नीचे देखें।
इसे पिछले खंड के परिणामों से निम्नानुसार घटाया जा सकता है।
GF(2) के ऊपर, कोटि 2 का केवल एक अलघुकरणीय बहुपद है:
और वह α तथा 1 + α, GF(4) के तत्व हैं जो GF(2) में नहीं हैं। GF(4) में संचालन की तालिकाएँ इसका परिणाम है, और इस प्रकार हैं:
Addition x+y | Multiplication x⋅y | Division x/y | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
घटाव के लिए एक तालिका नहीं दी गई है, क्योंकि घटाव जोड़ के समान है, जैसा कि विशेषता 2 के प्रत्येक क्षेत्र के मामले में है। तीसरी तालिका में, x को y से विभाजित करने के लिए, x के मानों को बाएं स्तंभ में पढ़ा जाना चाहिए और शीर्ष पंक्ति में y के मान। (क्योंकि 0 ⋅ z = 0 प्रत्येक z के लिए प्रत्येक वलय (गणित) में 0 से विभाजन को अपरिभाषित रहना पड़ता है।) तालिकाओं से, यह देखा जा सकता है कि GF(4) की योगात्मक संरचना क्लेन फोर-ग्रुप के लिए समरूपी है, जबकि गैर-शून्य गुणात्मक संरचना Z3 के लिए समरूपी है।
नक्शा
GF(p2) विषम अभाज्य p के लिए
GF(p2) के मामले में परिमित क्षेत्रों के #गैर-अभाज्य क्षेत्रों को लागू करने के लिए, व्यक्ति को 2 कोटि का एक अलघुकरणीय बहुपद ज्ञात करना होता है। p = 2, यह पिछले अनुभाग में किया गया है। यदि p एक विषम अभाज्य संख्या है, तो GF(p) में r के साथ X2 − r के रूप में हमेशा अलघुकरणीय बहुपद होते हैं।
अधिक सटीक रूप से, बहुपद X2 − r, GF(p) पर अलघुकरणीय है यदि और केवल यदि r एक द्विघात गैर-अवशेष मॉड्यूल p है (यह लगभग एक द्विघात गैर-अवशेष (quadratic non-residue) की परिभाषा है)। p − 1/2 द्विघात गैर-अवशेष (quadratic non-residue) मॉड्यूल p हैं। उदाहरण के लिए, p = 3, 5, 11, 13, ..., के लिए 2 एक द्विघात गैर-अवशेष (quadratic non-residue) है तथा 3, p = 5, 7, 17, ....के लिए एक द्विघात गैर-अवशेष (quadratic non-residue) है यदि p ≡ 3 mod 4, यानी p = 3, 7, 11, 19, ..., कोई −1 ≡ p − 1 को एक द्विघात गैर-अवशेष (quadratic non-residue) के रूप में चुन सकता है, जो हमें एक बहुत ही सरल अलघुकरणीय बहुपद X2 + 1 प्राप्त करने की अनुमति देता है।
एक द्विघात गैर-अवशेष (quadratic non-residue) r को चुनने के बाद, α को r का एक प्रतीकात्मक वर्गमूल माने यह एक प्रतीक है, जिसमें गुण α2 = r हैं, ठीक उसी तरह जैसे सम्मिश्र संख्या i का प्रतीकात्मक वर्गमूल −1 है। फिर, GF(p2) के तत्व सभी रैखिक व्यंजक हैं
जीएफ(8) और जीएफ(27)
बहुपद
जहाँ a, b, c GF(2) या GF(3) (क्रमशः) के तत्व हैं और एक ऐसा प्रतीक है कि
जीएफ(16)
बहुपद
GF(2) पर अलघुकरणीय है, अर्थात् यह अलघुकरणीय मोडुलो 2 है यह इस प्रकार है कि GF(16) के तत्व अभिव्यक्ति (गणित) द्वारा दर्शाए जा सकते है
गुणक संरचना
गैर-शून्य तत्वों का सेट GF(q) गुणन के तहत एक एबेलियन समूह है, क्रम q – 1 लैग्रेंज के प्रमेय (समूह सिद्धांत) द्वारा | लैग्रेंज की प्रमेय के अनुसार, एक भाजक मौजूद है q – 1 का एक भाजक k ऐसा है कि xk = 1 प्रत्येक गैर-शून्य x के लिए GF(q) में । चूंकि समीकरण xk = 1 का किसी भी क्षेत्र में अधिक से अधिक k हल हैं, q – 1, k के लिए उच्चतम संभव मान है। परिमित एबेलियन समूहों # की संरचना प्रमेय का तात्पर्य है कि यह गुणात्मक समूह चक्रीय समूह है, अर्थात सभी गैर-शून्य तत्व एक ही तत्व की घात हैं। सारांश:
ऐसे तत्व a अभाज्य तत्व कहलाते हैं। जब तक q = 2, 3, अभाज्य तत्व अद्वितीय नहीं है। अभाज्य तत्वों की संख्या φ(q − 1) है जहां φ यूलर का टोटिएंट फलन है।
उपरोक्त परिणाम का तात्पर्य है कि GF(q) में प्रत्येक x के लिए xq = x । विशेष स्थिति जहां q अभाज्य है, फर्मेट की छोटी प्रमेय है।
असतत लघुगणक
यदि a, GF(q) में एक अभाज्य तत्व है, तो F में किसी भी गैर-शून्य तत्व x के लिए, 0 ≤ n ≤ q − 2 के साथ एक अद्वितीय पूर्णांक n होता है, जैसे कि
इस पूर्णांक n को आधार a पर x का असतत लघुगणक (discrete logarithm) कहा जाता है।
जबकि an की गणना बहुत जल्दी की जा सकती है, उदाहरण के लिए वर्ग द्वारा घातांक का उपयोग करके, व्युत्क्रम संक्रिया, असतत लघुगणक की गणना के लिए कोई ज्ञात कुशल विधि नहीं है। इसका उपयोग विभिन्न क्रिप्टोग्राफिक प्रोटोकॉल में किया गया है, विवरण के लिए असतत लघुगणक देखें।
जब GF(q) गैर-शून्य तत्वों को उनके असतत लघुगणक द्वारा दर्शाया जाता है, तो गुणा और भाग आसान होता है, क्योंकि वे जोड़ और घटाव मॉड्यूल q – 1 तक कम हो जाते हैं। हालांकि, am + an के असतत लघुगणक की गणना करने के लिए अतिरिक्त मात्रा। पहचान .
n = 0, ..., q − 2 के लिए, एक an + 1 के असतत लघुगणक की तालिका बनाकर इस समस्या को हल करने की अनुमति देता है जिसे Zech के लघुगणक कहा जाता है (शून्य के असतत लघुगणक को −∞ के रूप में परिभाषित करना सुविधाजनक है)।
Zech के लघुगणक बड़ी गणनाओं के लिए उपयोगी होते हैं, जैसे कि मध्यम आकार के क्षेत्रों में रैखिक बीजगणित, अर्थात, ऐसे क्षेत्र जो प्राकृतिक विधि को अप्रभावी बनाने के लिए पर्याप्त रूप से बड़े हैं, लेकिन बहुत बड़े नहीं हैं, क्योंकि किसी को उसी आकार की तालिका की पूर्व-गणना करनी होती है। क्षेत्र के आदेश के रूप में।
एकता की जड़ ें इकाई के मूल
परिमित क्षेत्र का प्रत्येक अशून्य तत्व इकाई का मूल है, जैसे GF(q) के हर अशून्य तत्वों के लिए xq−1 = 1 के रूप में।
यदि n एक धनात्मक पूर्णांक है, तो इकाई का n--वाँ अभाज्य मूल समीकरण xn = 1 का एक हल है जो कि किसी भी धनात्मक पूर्णांक m < n के लिए समीकरण xm = 1 का हल नहीं है। यदि a क्षेत्र F में इकाई का n वां अभाज्य मूल है, तो F में इकाई के सभी n मूल हैं, जो 1, a, a2, ..., an−1 हैं।
फील्ड GF(q) में इकाई का n वां अभाज्य मूल है यदि और केवल यदि n, q − 1 का भाजक है; यदि n, q − 1 का एक भाजक है, तो GF(q) में इकाई के n वें अभाज्य मूलों की संख्या φ(n) (यूलर का पूर्ण फलन) है। GF(q) में इकाई के n वें मूलोंकी संख्या gcd(n, q − 1) है।
p की विशेषता के क्षेत्र में, प्रत्येक (np) वां मूल इकाई का n वां मूल भी होता है। यह इस प्रकार है कि इकाई की अभाज्य (np) वां मूल कभी भी विशेषता p के क्षेत्र में मौजूद नहीं होता हैं।
दूसरी ओर, यदि n, p का सह अभाज्य है, तो n वें साइक्लोटोमिक बहुपद के मूल p विशेषता के हर क्षेत्र में अलग हैं, क्योंकि यह बहुपद Xn − 1 का एक भाजक है जिसका विभेदक (discriminant) गैर-शून्य मोडुलो p है यह इस प्रकार है कि GF(p) पर nth साइक्लोटॉमिक बहुपद कारक अलग-अलग अलघुकरणीय बहुपदों में होते हैं जिनकी सभी कोटि समान होती है, d कहते हैं, और यह कि GF(pd) विशेषता p का सबसे छोटा क्षेत्र है जिसमें इकाई के nth अभाज्य मूल होते हैं।
उदाहरण: GF(64)
फील्ड GF(64) में कई दिलचस्प गुण हैं जो छोटे क्षेत्र साझा नहीं करते हैं: इसमें दो उपक्षेत्र हैं जैसे कि कोई भी दूसरे में समाहित नहीं है; सभी जनरेटर (GF(2) पर कोटि 6 के न्यूनतम बहुपद वाले तत्व) अभाज्य तत्व नहीं हैं; और अभाज्य तत्व गैलोइस समूह के अंतर्गत सभी संयुग्मित नहीं हैं।
इस क्षेत्र का क्रम 26, और 6 के विभाजक 1, 2, 3, 6 हैं, GF(2), GF(22) = GF(4), GF(23) = GF(8), तथा GF(64) ही GF(64) के उपक्षेत्र हैं । जैसा कि 2 तथा 3 सहअभाज्य हैं, GF(64) में GF(4) तथा GF(8) का प्रतिच्छेदन अभाज्य क्षेत्र GF(2) है।
इस प्रकार GF(4) तथा GF(8) के समुच्चय (union) में 10 तत्व होते हैं। GF(64) के शेष 54 तत्व इस अर्थ में GF(64) उत्पन्न करते हैं कि किसी अन्य उपक्षेत्र में उनमें से कोई भी शामिल नहीं है। यह इस प्रकार है कि वे GF(2) पर कोटि 6 के अलघुकरणीय बहुपदों के मूल हैं। इसका तात्पर्य है कि, GF(2) के ऊपर कोटि 6 के बिल्कुल 9 = 54/6 अलघुकरणीय मोनिक बहुपद हैं। इसे X64 − X के ऊपर GF(2) का फैक्टरिंग करके सत्यापित किया जा सकता है।
GF(64) के तत्व कुछ n विभाजक 63 के लिए इकाई के nth अभाज्य मूल हैं। इकाई के तीसरे और सातवें वें मूल क्रमशः GF(4) तथा GF(8) की हैं, {9, 21, 63} में कुछ n के लिए इकाई के 54 जनक nth अभाज्य मूल हैं। यूलर के टोटिएंट फलन से पता चलता है कि इकाई के 6 आदिम 9 वें मूल , इकाई के 12 अभाज्य 21 वें मूल और इकाई के 36 आदिम 63 वें मूल हैं। इन संख्याओं का योग करने पर फिर से 54 तत्व मिलते हैं।
GF(2) पर साइक्लोटोमिक बहुपदों का गुणनखंडन करके, कोई पाता है कि:
- इकाई के 9 वें छह अभाज्य मूल, मूल हैं और सभी गैलोइस समूह की कार्रवाई के तहत संयुग्मित हैं।
- इकाई के 21 वें बारह अभाज्य मूल, मूल हैं गैलोइस समूह की कार्रवाई के तहत वे दो कक्षाएँ बनाते हैं। चूंकि दो कारक एक दूसरे के पारस्परिक बहुपद हैं, एक मूल और इसका (गुणात्मक) व्युत्क्रम एक ही कक्षा से संबंधित नहीं है।
- GF(64) के 36 अभाज्य तत्व के मूल हैं गैलोइस समूह की कार्रवाई के तहत वे छह तत्वों की छह कक्षाओं में विभाजित हो गए।
इससे पता चलता है कि GF(64) के निर्माण के लिए सबसे अच्छा विकल्प इसे GF(2)[X] / (X6 + X + 1) के रूप में परिभाषित करना है। वास्तव में, यह जनक एक अभाज्य तत्व है, और यह बहुपद अलघुकरणीय बहुपद है जो सबसे आसान यूक्लिडियन विभाजन उत्पन्न करता है।
Frobenius automorphism और Galois सिद्धांत
इस खंड में, p एक अभाज्य संख्या है, और q = pn, p की एक घात है।
GF(q) में सर्वसमिका (x + y)p = xp + yp का तात्पर्य है कि मानचित्र (map)
φ की संरचना को k बार φk द्वारा निरूपित कर , हमारे पास है
GF(p) का कोई अन्य GF(q) -स्वरूपण नहीं हैं। दूसरे शब्दों में, GF(pn) के बिल्कुल n GF(p)-स्वरूपण (automorphism) है, जो हैं
तथ्य यह है कि फ्रोबेनियस मानचित्र विशेषण (surjective) है, इसका तात्पर्य है कि प्रत्येक परिमित क्षेत्र पूर्ण क्षेत्र है।
बहुपद गुणनखंड
यदि F एक परिमित क्षेत्र है, तो F में गुणांक के साथ एक गैर-स्थिर मोनिक बहुपद F पर अलघुकरणीय है, यदि यह F में गुणांक वाले दो गैर-स्थिर मोनिक बहुपदों का गुणनफल नहीं है।
चूंकि एक क्षेत्र पर प्रत्येक बहुपद वलय एक अद्वितीय गुणनखंडन अनुक्षेत्र (unique factorization domain) है, एक परिमित क्षेत्र पर प्रत्येक मोनिक बहुपद को एक अद्वितीय तरीके से (कारकों के क्रम तक) अखंडनीय (irreducible) मोनिक बहुपद के गुणन में विभाजित किया जा सकता है। परिमित क्षेत्र पर बहुपद इरेड्यूसबिलिटी और फैक्टरिंग बहुपदों के परीक्षण के लिए कुशल एल्गोरिदम हैं। वे पूर्णांकों या परिमेय संख्याओं पर बहुपदों का गुणनखण्ड करने के लिए एक महत्वपूर्ण कदम हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर, या कम से कम, परिमित प्रधान क्षेत्रों पर बहुपदों के गुणनखंडन के लिए कार्य होते हैं।
परिमित क्षेत्र में बहुपद अलघुकरणीय और विभाजित बहुपदों के परीक्षण के लिए कुशल प्रणाली हैं। वे पूर्णांकों या परिमेय संख्या ओं पर बहुपदों के गुणनखंड के लिए एक महत्वपूर्ण चरण हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर, या कम से कम, परिमित अभाज्य क्षेत्रों में बहुपदों के गुणनखंडन के लिए कार्य होते हैं।
दी गई डिग्री के अमिट बहुपद
बहुपद
इसका तात्पर्य यह है कि, यदि q = pn तो Xq − X पर सभी मोनिक अलघुकरणीय बहुपदों का गुणनफल है जिसकी कोटि n को विभाजित करती है। वास्तव में, यदि P, Xq − X के GF(p) पर एक अलघुकरणीय गुणनखंड है, तो इसकी कोटि n को विभाजित करती है, क्योंकि इसका विभाजन क्षेत्र (splitting field) GF(pn) में समाहित है। इसके विपरीत, यदि कोटि d, GF(p) पर एक अलघुकरणीय मोनिक बहुपद है, तो यह कोटि d के क्षेत्र विस्तार को परिभाषित करता है, जो GF(pn) में निहित है , और P के सभी मूल GF(pn) से संबंधित हैं। और Xq − X के मूल हैं; इस प्रकार P, Xq − X को विभाजित करता है। चूंकि Xq − X का कोई विविध गुणन खंड नहीं है, इसलिए यह सभी अलघुकरणीय मोनिक बहुपदों का गुणन है जो इसे विभाजित करते हैं।
इस गुण का उपयोग GF(p) पर बहुपदों की प्रत्येक कोटि के अलघुकरणीय गुणनखंड के गुणन की गणना करने के लिए किया जाता है; भिन्न कोटि गुणनखंड देखें।
एक परिमित क्षेत्र पर दी गई डिग्री के मोनिक इरेड्यूसबल बहुपदों की संख्या
जो नंबर N(q, n) डिग्री के मोनिक इरेड्यूसीबल बहुपद का n ऊपर
GF(q) द्वारा दिया गया है[4]
उपरोक्त सूत्र द्वारा, डिग्री के इरेड्यूसिबल (जरूरी नहीं कि मोनिक) बहुपदों की संख्या n ऊपर GF(q) है (q − 1)N(q, n).
सटीक सूत्र असमानता का तात्पर्य है
अनुप्रयोग
क्रिप्टोग्राफी में, परिमित क्षेत्रों में या अण्डाकार वक्र ों में असतत लघुगणक समस्या की कठिनाई कई व्यापक रूप से उपयोग किए जाने वाले प्रोटोकॉल का आधार है, जैसे कि डिफी-हेलमैन प्रोटोकॉल। उदाहरण के लिए, 2014 में, विकिपीडिया के लिए एक सुरक्षित इंटरनेट कनेक्शन में एक बड़े परिमित क्षेत्र में अण्डाकार वक्र डिफी-हेलमैन प्रोटोकॉल (ECDHE ) शामिल था।[5] कोडिंग सिद्धांत में, कई कोड परिमित क्षेत्रों में वेक्टर रिक्त स्थान के रैखिक उप-स्थान के रूप में बनाए जाते हैं।
कई त्रुटि सुधार कोड द्वारा परिमित फ़ील्ड का उपयोग किया जाता है, जैसे रीड-सोलोमन त्रुटि सुधार | रीड-सोलोमन त्रुटि सुधार कोड या बीसीएच कोड । परिमित क्षेत्र में लगभग हमेशा 2 की विशेषता होती है, क्योंकि कंप्यूटर डेटा बाइनरी में संग्रहीत होता है। उदाहरण के लिए, डेटा के एक बाइट की व्याख्या किस तत्व के रूप में की जा सकती है? . एक अपवाद PDF417 बार कोड है, जो है . कुछ सीपीयू में विशेष निर्देश होते हैं जो विशेषता 2 के परिमित क्षेत्रों के लिए उपयोगी हो सकते हैं, आमतौर पर कैरी-लेस उत्पाद की विविधताएं।
संख्या सिद्धांत में परिमित क्षेत्रों का व्यापक रूप से उपयोग किया जाता है, क्योंकि पूर्णांकों पर कई समस्याओं को मॉड्यूलर अंकगणित एक या कई अभाज्य संख्याओं को कम करके हल किया जा सकता है। उदाहरण के लिए, परिमेय संख्या ओं के क्षेत्र में बहुपद गुणनखंड न और रैखिक बीजगणित के लिए सबसे तेज़ ज्ञात एल्गोरिदम, मॉड्यूलो एक या कई अभाज्य संख्याओं को कम करके आगे बढ़ते हैं, और फिर चीनी शेष प्रमेय , हेंसल लिफ्टिंग या एलएलएल एल्गोरिथम का उपयोग करके समाधान का पुनर्निर्माण करते हैं।
इसी तरह संख्या सिद्धांत में कई सैद्धांतिक समस्याओं को उनके कुछ या सभी अभाज्य संख्याओं में कमी के मॉड्यूल पर विचार करके हल किया जा सकता है। उदाहरण के लिए, हस सिद्धांत देखें। बीजगणितीय ज्यामिति के कई हालिया विकास इन मॉड्यूलर विधियों की शक्ति को बढ़ाने की आवश्यकता से प्रेरित थे। फ़र्मेट के अंतिम प्रमेय का विल्स का प्रमाण एक गहन परिणाम का एक उदाहरण है जिसमें परिमित क्षेत्रों सहित कई गणितीय उपकरण शामिल हैं।
वेइल अनुमान परिमित क्षेत्रों में बीजगणितीय विविधता पर अंकों की संख्या से संबंधित है और सिद्धांत में घातीय योग और वर्ण योग अनुमान सहित कई अनुप्रयोग हैं।
साहचर्य में परिमित क्षेत्रों का व्यापक अनुप्रयोग है, दो प्रसिद्ध उदाहरण पीला ग्राफ की परिभाषा और पाले निर्माण के लिए संबंधित निर्माण हैं। अंकगणितीय संयोजन में परिमित क्षेत्र[6] और परिमित क्षेत्र मॉडल[7][8] व्यापक रूप से उपयोग किया जाता है, जैसे कि अंकगणितीय प्रगति पर ज़ेमेरेडी के प्रमेय में।
एक्सटेंशन
बीजीय बंद
एक परिमित क्षेत्र F बीजगणितीय रूप से बंद नहीं है: बहुपद
बीजीय बंद को ठीक करें का . नक्शा प्रत्येक को भेजना x प्रति xq कहा जाता है qवें शक्ति फ्रोबेनियस ऑटोमोर्फिज्म। का उपक्षेत्र द्वारा तय किया गया nकी पुनरावृति बहुपद के शून्यकों का समुच्चय है xqn − x, जिसके व्युत्पन्न होने के बाद से अलग-अलग जड़ें हैं है −1, जो कभी शून्य नहीं होता। इसलिए उस उपक्षेत्र में है qn तत्वों, तो यह की अनूठी प्रति है में . का हर परिमित विस्तार में क्या यह कुछ के लिए n, इसलिए
निरपेक्ष गैलोइस समूह अनंत समूह है
अर्ध-बीजगणितीय बंद
हालांकि परिमित क्षेत्र बीजगणितीय रूप से बंद नहीं होते हैं, वे अर्ध-बीजगणितीय रूप से बंद क्षेत्र होते हैं| अर्ध-बीजगणितीय रूप से बंद , जिसका अर्थ है कि परिमित क्षेत्र में प्रत्येक सजातीय बहुपद में एक गैर-नगण्य शून्य होता है जिसके घटक क्षेत्र में होते हैं यदि इसके चर की संख्या इसकी कोटि से अधिक है। यह एमिल आर्टिन और लियोनार्ड यूजीन डिक्सन का अनुमान था जिसे क्लाउड शेवेली द्वारा सिद्ध किया गया था (देखें शेवेली-चेतावनी प्रमेय)।
वेडरबर्न की छोटी प्रमेय
एक विभाजन वलय ( डिवीजन रिंग ) क्षेत्र का सामान्यीकरण है। विभाजन वलय को क्रमविनिमेय (कम्यूटेटिव) नहीं माना जाता है। कोई गैर-क्रमविनिमेय परिमित विभाजन वलय नहीं हैं: वेडरबर्न की छोटी प्रमेय में कहा गया है कि सभी परिमित विभाजन वलय क्रमविनिमेय हैं, और इसलिए परिमित क्षेत्र हैं। यह परिणाम तब भी कायम रहता है जब हम वैकल्पिकता के लिए संबद्धता की सूक्ति को शिथिल (relax) करते हैं, अर्थात, आर्टिन-ज़ोर्न प्रमेय द्वारा सभी परिमित वैकल्पिक विभाजन वलय परिमित क्षेत्र हैं।[9]
यह भी देखें
- अर्ध-परिमित क्षेत्र
- एक तत्व के साथ फ़ील्ड
- परिमित क्षेत्र अंकगणित
- परिमित अंगूठी
- परिमित समूह
- प्राथमिक एबेलियन समूह
- हैमिंग स्पेस
टिप्पणियाँ
- ↑ 1.0 1.1 Moore, E. H. (1896), "A doubly-infinite system of simple groups", in E. H. Moore; et al. (eds.), Mathematical Papers Read at the International Mathematics Congress Held in Connection with the World's Columbian Exposition, Macmillan & Co., pp. 208–242
- ↑ This latter notation was introduced by E. H. Moore in an address given in 1893 at the International Mathematical Congress held in Chicago Mullen & Panario 2013, p. 10.
- ↑ Recommended Elliptic Curves for Government Use (PDF), National Institute of Standards and Technology, July 1999, p. 3
- ↑ Jacobson 2009, §4.13
- ↑ This can be verified by looking at the information on the page provided by the browser.
- ↑ Shparlinski, Igor E. (2013), "Additive Combinatorics over Finite Fields: New Results and Applications", Finite Fields and Their Applications, DE GRUYTER, pp. 233–272, doi:10.1515/9783110283600.233, ISBN 9783110283600
- ↑ Green, Ben (2005), "Finite field models in additive combinatorics", Surveys in Combinatorics 2005, Cambridge University Press, pp. 1–28, arXiv:math/0409420, doi:10.1017/cbo9780511734885.002, ISBN 9780511734885, S2CID 28297089
- ↑ Wolf, J. (March 2015). "अंकगणितीय संयोजन में परिमित क्षेत्र मॉडल - दस वर्ष". Finite Fields and Their Applications. 32: 233–274. doi:10.1016/j.ffa.2014.11.003. ISSN 1071-5797.
- ↑ Shult, Ernest E. (2011). अंक और रेखाएँ। शास्त्रीय ज्यामिति की विशेषता. Universitext. Berlin: Springer-Verlag. p. 123. ISBN 978-3-642-15626-7. Zbl 1213.51001.
संदर्भ
- W. H. Bussey (1905) "Galois field tables for pn ≤ 169", Bulletin of the American Mathematical Society 12(1): 22–38, doi:10.1090/S0002-9904-1905-01284-2
- W. H. Bussey (1910) "Tables of Galois fields of order < 1000", Bulletin of the American Mathematical Society 16(4): 188–206, doi:10.1090/S0002-9904-1910-01888-7
- Jacobson, Nathan (2009) [1985], Basic algebra I (Second ed.), Dover Publications, ISBN 978-0-486-47189-1
- Mullen, Gary L.; Mummert, Carl (2007), Finite Fields and Applications I, Student Mathematical Library (AMS), ISBN 978-0-8218-4418-2
- Mullen, Gary L.; Panario, Daniel (2013), Handbook of Finite Fields, CRC Press, ISBN 978-1-4398-7378-6
- Lidl, Rudolf; Niederreiter, Harald (1997), Finite Fields (2nd ed.), Cambridge University Press, ISBN 0-521-39231-4
- Skopin, A. I. (2001) [1994], "Galois field", Encyclopedia of Mathematics, EMS Press
बाहरी संबंध
- Finite Fields at Wolfram research.