परिमित क्षेत्र: Difference between revisions
No edit summary |
No edit summary |
||
Line 53: | Line 53: | ||
=== गैर-अभाज्य क्षेत्र === | === गैर-अभाज्य क्षेत्र === | ||
{{math|''p''}} अभाज्य और {{math|''n'' > 1}} के साथ एक प्रमुख घात {{math|1=''q'' = ''p''<sup>''n''</sup>}} को देखते हुए, क्षेत्र{{math|GF(''q'')}} को स्पष्ट रूप से निम्नलिखित तरीके से स्पष्ट रूप से बनाया जा सकता है। सबसे पहले कोटि{{math|''n''}} के {{math|GF(''p'')[''X'']}} में एक '''अलघुकरणीय''' बहुपद {{math|''P''}} चुनते है (इस तरह का एक अलघुकरणीय बहुपद हमेशा मौजूद रहता है)। फिर [[ भागफल वलय ]]<math display="block">\mathrm{GF}(q) = \mathrm{GF}(p)[X]/(P)</math> | {{math|''p''}} अभाज्य और {{math|''n'' > 1}} के साथ एक प्रमुख घात {{math|1=''q'' = ''p''<sup>''n''</sup>}} को देखते हुए, क्षेत्र{{math|GF(''q'')}} को स्पष्ट रूप से निम्नलिखित तरीके से स्पष्ट रूप से बनाया जा सकता है। सबसे पहले कोटि{{math|''n''}} के {{math|GF(''p'')[''X'']}} में एक '''अलघुकरणीय''' बहुपद {{math|''P''}} चुनते है (इस तरह का एक अलघुकरणीय बहुपद हमेशा मौजूद रहता है)। फिर [[ भागफल वलय ]]<math display="block">\mathrm{GF}(q) = \mathrm{GF}(p)[X]/(P)</math> | ||
{{math|''P''}} द्वारा उत्पन्न आदर्श द्वारा बहुपद वलय | {{math|''P''}} द्वारा उत्पन्न आदर्श द्वारा बहुपद वलय {{math|GF(''p'')[''X'']}} का क्रम {{math|''q''}} का एक क्षेत्र है। | ||
अधिक स्पष्ट रूप से, {{math|GF(''q'')}} के तत्व {{math|GF(''p'')}} पर बहुपद हैं जिसकी कोटि निश्चित रूप से {{math|''n''}} से कम है। जोड़ और घटाना {{math|GF(''p'')}} पर बहुपदों के हैं। दो तत्वों का गुणन {{math|GF(''p'')[''X'']}} में {{math|''P''}} के गुणन द्वारा यूक्लिडियन | अधिक स्पष्ट रूप से, {{math|GF(''q'')}} के तत्व {{math|GF(''p'')}} पर बहुपद हैं जिसकी कोटि निश्चित रूप से {{math|''n''}} से कम है। जोड़ और घटाना {{math|GF(''p'')}} पर बहुपदों के हैं। दो तत्वों का गुणन {{math|GF(''p'')[''X'']}} में {{math|''P''}} के गुणन द्वारा यूक्लिडियन विभाजन का शेषफल है। एक गैर-शून्य तत्व के गुणात्मक व्युत्क्रम की गणना विस्तारित यूक्लिडियन कलनविधि के साथ की जा सकती है; देखें विस्तारित यूक्लिडियन कलनविधि § सरल बीजगणितीय क्षेत्र विस्तार। | ||
{{math|GF(4)}} के निर्माण को छोड़कर, {{math|''P''}} के लिए कई संभावित विकल्प हैं, जो समरूपी | {{math|GF(4)}} के निर्माण को छोड़कर, {{math|''P''}} के लिए कई संभावित विकल्प हैं, जो समरूपी परिणाम उत्पन्न करते हैं। यूक्लिडियन विभाजन को सरल बनाने के लिए, आमतौर पर {{math|''P''}} के लिए एक बहुपद चुनता है | ||
<math display="block">X^n + aX + b,</math> | <math display="block">X^n + aX + b,</math> | ||
जो यूक्लिडियन | जो यूक्लिडियन विभाजन को बहुत कुशल बनाते हैं। हालाँकि, कुछ क्षेत्रों के लिए, विशेष रूप से विशेषता 2 में, {{math|''X<sup>n</sup>'' + ''aX'' + ''b''}} के रूप में अलघुकरणीय बहुपद मौजूद नहीं हो सकते हैं। विशेषता {{math|2}} में, यदि बहुपद {{math|''X''<sup>''n''</sup> + ''X'' + 1}} कम करने योग्य है, तो {{math|''X''<sup>''n''</sup> + ''X''<sup>''k''</sup> + 1}} को सबसे कम संभव {{math|''k''}} के साथ चुनने की अनुशंसा की जाती है जो बहुपद को अलघुकरणीय बनाता है। यदि ये सभी [[ त्रिनाम ]] लघुकरणीय हैं, तो कोई पेंटानोमियल्स {{math|''X''<sup>''n''</sup> + ''X''<sup>''a''</sup> + ''X''<sup>''b''</sup> + ''X''<sup>''c''</sup> + 1}} चुनता है , क्योंकि {{math|1}} से अधिक कोटि वाले बहुपद, सम संख्या वाले शब्दों के साथ, विशेषता {{math|2}} में कभी भी अलघुकरणीय नहीं होते हैं जिसमें 1 मूल होता है।<ref>{{citation|publisher=[[National Institute of Standards and Technology]]|url=http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf|title=Recommended Elliptic Curves for Government Use|pages=3|date=July 1999}}</ref> ऐसे बहुपद के लिए एक संभावित विकल्प [[ कॉनवे बहुपद (परिमित क्षेत्र) ]] द्वारा दिया जाता है। वे एक क्षेत्र के निरूपण और उसके उपक्षेत्रों के निरूपण के बीच एक निश्चित अनुकूलता सुनिश्चित करते हैं। | ||
अगले खंडों में, हम दिखाएंगे कि ऊपर उल्लिखित सामान्य निर्माण विधि छोटे परिमित क्षेत्रों के लिए कैसे काम करती है। | अगले खंडों में, हम दिखाएंगे कि ऊपर उल्लिखित सामान्य निर्माण विधि छोटे परिमित क्षेत्रों के लिए कैसे काम करती है। | ||
=== चार तत्वों वाला क्षेत्र === | === चार तत्वों वाला क्षेत्र === | ||
सबसे छोटा गैर-अभाज्य क्षेत्र (non-prime field) चार तत्वों वाला क्षेत्र है, जिसे आमतौर पर {{math|GF(4)}} या <math>\mathbb F_4.</math> के रूप दर्शाया जाता है इसमें चार तत्व <math>0, 1, \alpha, 1+\alpha</math> होते हैं जैसे कि <math>\alpha^2=1+\alpha,</math> <math>1\cdot\alpha = \alpha \cdot 1 = \alpha,</math> <math>x+x=0,</math> तथा <math>x\cdot 0=0\cdot x=0,</math> प्रत्येक <math>x\in \operatorname{GF}(4),</math> के लिए अन्य संक्रिया | सबसे छोटा गैर-अभाज्य क्षेत्र (non-prime field) चार तत्वों वाला क्षेत्र है, जिसे आमतौर पर {{math|GF(4)}} या <math>\mathbb F_4.</math> के रूप दर्शाया जाता है इसमें चार तत्व <math>0, 1, \alpha, 1+\alpha</math> होते हैं जैसे कि <math>\alpha^2=1+\alpha,</math> <math>1\cdot\alpha = \alpha \cdot 1 = \alpha,</math> <math>x+x=0,</math> तथा <math>x\cdot 0=0\cdot x=0,</math> प्रत्येक <math>x\in \operatorname{GF}(4),</math> के लिए अन्य संक्रिया के परिणाम [[ वितरण कानून ]]से आसानी से निकाले जा सकते हैं। पूर्ण संक्रिया सारिणी के लिए नीचे देखें। | ||
इसे पिछले खंड के परिणामों से निम्नानुसार घटाया जा सकता है। | इसे पिछले खंड के परिणामों से निम्नानुसार घटाया जा सकता है। | ||
Line 166: | Line 166: | ||
|} | |} | ||
घटाव के लिए एक तालिका नहीं दी गई है, क्योंकि घटाव जोड़ के समान है, जैसा कि विशेषता 2 के प्रत्येक क्षेत्र के मामले में है। | घटाव के लिए एक तालिका नहीं दी गई है, क्योंकि घटाव जोड़ के समान है, जैसा कि विशेषता 2 के प्रत्येक क्षेत्र के मामले में है। | ||
तीसरी तालिका में, {{math|''x''}} को {{math|''y''}} से विभाजित करने के लिए, {{math|''x''}} के मानों को बाएं स्तंभ में पढ़ा जाना चाहिए और शीर्ष पंक्ति में y के मान। (क्योंकि {{math|1=0 ⋅ ''z'' = 0}} प्रत्येक {{mvar|z}} के लिए प्रत्येक वलय (गणित) में 0 से विभाजन को अपरिभाषित रहना पड़ता है।) तालिकाओं से, यह देखा जा सकता है कि {{math|GF(4)}} की योगात्मक संरचना क्लेन फोर-ग्रुप के लिए समरूपी | तीसरी तालिका में, {{math|''x''}} को {{math|''y''}} से विभाजित करने के लिए, {{math|''x''}} के मानों को बाएं स्तंभ में पढ़ा जाना चाहिए और शीर्ष पंक्ति में y के मान। (क्योंकि {{math|1=0 ⋅ ''z'' = 0}} प्रत्येक {{mvar|z}} के लिए प्रत्येक वलय (गणित) में 0 से विभाजन को अपरिभाषित रहना पड़ता है।) तालिकाओं से, यह देखा जा सकता है कि {{math|GF(4)}} की योगात्मक संरचना क्लेन फोर-ग्रुप के लिए समरूपी है, जबकि गैर-शून्य गुणात्मक संरचना Z<sub>3</sub> के लिए समरूपी है। | ||
नक्शा | नक्शा | ||
<math display="block"> \varphi:x \mapsto x^2</math> | <math display="block"> \varphi:x \mapsto x^2</math> | ||
गैर-नगण्य क्षेत्र | गैर-नगण्य क्षेत्र स्वसमाकृतिकता है, जिसे फ्रोबेनियस स्वसमाकृतिकता और गैलोइस सिद्धांत कहा जाता है, जो {{math|''α''}} को ऊपर बताए गए अलघुकरणीय बहुपद <math>X^2+X+1.</math> के दूसरे मूल {{math|1 + ''α''}} में भेजता है | ||
Line 176: | Line 176: | ||
'''<big>{{math|GF(''p''<sup>2</sup>)}} विषम अभाज्य {{math|''p''}} के लिए</big>''' | '''<big>{{math|GF(''p''<sup>2</sup>)}} विषम अभाज्य {{math|''p''}} के लिए</big>''' | ||
{{math|GF(''p''<sup>2</sup>)}} के मामले में परिमित क्षेत्रों के #गैर-अभाज्य क्षेत्रों को लागू करने के लिए, व्यक्ति को 2 कोटि | {{math|GF(''p''<sup>2</sup>)}} के मामले में परिमित क्षेत्रों के #गैर-अभाज्य क्षेत्रों को लागू करने के लिए, व्यक्ति को 2 कोटि का एक अलघुकरणीय बहुपद ज्ञात करना होता है। {{math|1=''p'' = 2}}, यह पिछले अनुभाग में किया गया है। यदि {{math|''p''}} एक विषम अभाज्य संख्या है, तो {{math|GF(''p'')}} में {{math|''r''}} के साथ {{math|1=''X''<sup>2</sup> − ''r''}} के रूप में हमेशा अलघुकरणीय बहुपद होते हैं। | ||
अधिक सटीक रूप से, बहुपद {{math|1=''X''<sup>2</sup> − ''r''}}, {{math|GF(''p'')}} पर अलघुकरणीय | अधिक सटीक रूप से, बहुपद {{math|1=''X''<sup>2</sup> − ''r''}}, {{math|GF(''p'')}} पर अलघुकरणीय है यदि और केवल यदि {{math|''r''}} एक [[ द्विघात गैर-अवशेष | द्विघात गैर-अवशेष]] मॉड्यूल {{math|''p''}} है (यह लगभग एक द्विघात गैर-अवशेष (quadratic non-residue) की परिभाषा है)। {{math|{{sfrac|''p'' − 1|2}}}} द्विघात गैर-अवशेष (quadratic non-residue) मॉड्यूल {{math|''p''}} हैं। उदाहरण के लिए, {{math|1= ''p'' = 3, 5, 11, 13, ...}}, के लिए {{math|2}} एक द्विघात गैर-अवशेष (quadratic non-residue) है तथा {{math|3}}, {{math|1= ''p'' = 5, 7, 17, ...}}.के लिए एक द्विघात गैर-अवशेष (quadratic non-residue) है यदि {{math|1=''p'' ≡ 3 mod 4}}, यानी {{math|1=''p'' = 3, 7, 11, 19, ...}}, कोई {{math|1= −1 ≡ ''p'' − 1}} को एक द्विघात गैर-अवशेष (quadratic non-residue) के रूप में चुन सकता है, जो हमें एक बहुत ही सरल अलघुकरणीय बहुपद {{math|''X''<sup>2</sup> + 1}} प्राप्त करने की अनुमति देता है। | ||
एक | एक द्विघात गैर-अवशेष (quadratic non-residue) {{math|''r''}} को चुनने के बाद, {{math|''α''}} को {{math|''r''}} का एक प्रतीकात्मक वर्गमूल माने यह एक प्रतीक है, जिसमें गुण {{math|1=''α''<sup>2</sup> = ''r''}} हैं, ठीक उसी तरह जैसे सम्मिश्र संख्या {{math|''i''}} का प्रतीकात्मक वर्गमूल {{math|−1}} है। फिर, {{math|GF(''p''<sup>2</sup>)}} के तत्व सभी रैखिक व्यंजक हैं <math display="block">a+b\alpha,</math> | ||
{{math|GF(''p'')}} में {{math|''a''}} तथा {{math|''b''}} के साथ। {{math|GF(''p''<sup>2</sup>)}} पर संक्रिया | {{math|GF(''p'')}} में {{math|''a''}} तथा {{math|''b''}} के साथ। {{math|GF(''p''<sup>2</sup>)}} पर संक्रिया निम्नानुसार परिभाषित किए गए हैं (लैटिन अक्षरों द्वारा दर्शाए गए {{math|GF(''p'')}} के तत्वों के बीच संक्रिया {{math|GF(''p'')}} संक्रिया हैं): | ||
<math display="block">\begin{align} | <math display="block">\begin{align} | ||
-(a+b\alpha)&=-a+(-b)\alpha\\ | -(a+b\alpha)&=-a+(-b)\alpha\\ | ||
Line 194: | Line 194: | ||
बहुपद | बहुपद | ||
<math display="block">X^3-X-1</math> | <math display="block">X^3-X-1</math> | ||
{{math|GF(2)}} तथा {{math|GF(3)}} पर अलघुकरणीय | {{math|GF(2)}} तथा {{math|GF(3)}} पर अलघुकरणीय है अर्थात्, यह अलघुकरणीय '''मोडुलो''' {{math|2}} तथा {{math|3}} है (यह दिखाने के लिए पर्याप्त है कि इसकी {{math|GF(2)}} में कोई मूल नहीं है न ही {{math|GF(3)}} में)। यह इस प्रकार है कि {{math|GF(8)}} तथा {{math|GF(27)}} के तत्वों को [[ अभिव्यक्ति (गणित) ]] द्वारा दर्शाया जा सकता है | ||
<math display="block">a+b\alpha+c\alpha^2,</math> | <math display="block">a+b\alpha+c\alpha^2,</math> | ||
Line 214: | Line 214: | ||
{{math|GF(2)}} पर अलघुकरणीय | {{math|GF(2)}} पर अलघुकरणीय है, अर्थात् यह अलघुकरणीय मोडुलो {{math|2}} है यह इस प्रकार है कि {{math|GF(16)}} के तत्व '''अभिव्यक्ति (गणित)''' द्वारा दर्शाए जा सकते है | ||
<math display="block">a+b\alpha+c\alpha^2+d\alpha^3,</math> | <math display="block">a+b\alpha+c\alpha^2+d\alpha^3,</math> | ||
जहाँ {{math|''a'', ''b'', ''c'', ''d''}} दोनों मे से एक {{math|0}} या {{math|1}} (के तत्व {{math|GF(2)}}), तथा {{math|''α''}} एक प्रतीक है कि | जहाँ {{math|''a'', ''b'', ''c'', ''d''}} दोनों मे से एक {{math|0}} या {{math|1}} (के तत्व {{math|GF(2)}}), तथा {{math|''α''}} एक प्रतीक है कि | ||
<math display="block">\alpha^4=\alpha+1</math> | <math display="block">\alpha^4=\alpha+1</math> | ||
(अर्थात {{math|''α''}} को दिए गए अलघुकरणीय बहुपद | (अर्थात {{math|''α''}} को दिए गए अलघुकरणीय बहुपद के मूल के रूप में परिभाषित किया गया है)। जैसा कि {{math|GF(2)}} की विशेषता {{math|2}} है, {{math|GF(16)}} में प्रत्येक तत्व इसका योगात्मक व्युत्क्रम है। {{math|GF(16)}} पर जोड़ और गुणा को निम्नानुसार परिभाषित किया जा सकता है; निम्नलिखित सूत्रों में, लैटिन अक्षरों द्वारा दर्शाए गए {{math|GF(2)}} के तत्वों के बीच संक्रियाएँ {{math|GF(2)}} में संक्रियाएँ हैं। | ||
<math display="block"> | <math display="block"> | ||
\begin{align} | \begin{align} | ||
Line 228: | Line 228: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
फील्ड {{math|GF(16)}} में आठ अभाज्य तत्व | फील्ड {{math|GF(16)}} में आठ अभाज्य तत्व हैं (ऐसे तत्व जिनमें. पूर्णांक घातों के रूप में {{math|GF(16)}} के सभी गैर-शून्य तत्व हैं )। ये तत्व <math>X^4+X+1</math> के चार मूल हैं और उनके गुणनात्मक व्युत्क्रम हैं। विशेष रूप से, {{math|''α''}} एक अभाज्य तत्व है, और अभाज्य तत्व हैं <math>\alpha^m</math> जिसमें {{mvar|m}} से कम और 15 के साथ सह अभाज्य (अर्थात 1, 2, 4, 7, 8, 11, 13, 14)। | ||
== गुणक संरचना == | == गुणक संरचना == | ||
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|''a''}} अभाज्य तत्व कहलाते हैं। जब तक {{math|1=''q'' = 2, 3}}, अभाज्य तत्व अद्वितीय (unique) नहीं है। अभाज्य तत्वों की संख्या {{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 240: | Line 240: | ||
=== असतत लघुगणक === | === असतत लघुगणक === | ||
यदि {{math|''a''}}, {{math|GF(''q'')}} में एक अभाज्य तत्व | यदि {{math|''a''}}, {{math|GF(''q'')}} में एक अभाज्य तत्व है, तो {{math|''F''}} में किसी भी गैर-शून्य तत्व {{math|''x''}} के लिए, {{math|0 ≤ ''n'' ≤ ''q'' − 2}} के साथ एक अद्वितीय पूर्णांक {{math|''n''}} होता है, जैसे कि | ||
{{block indent | em = 1.5 | text = {{math|1=''x'' = ''a<sup>n</sup>''}}.}} | {{block indent | em = 1.5 | text = {{math|1=''x'' = ''a<sup>n</sup>''}}.}} | ||
इस पूर्णांक {{math|''n''}} को आधार {{math|''a''}} पर {{math|''x''}} का [[ असतत लघुगणक ]] (discrete logarithm) कहा जाता है। | इस पूर्णांक {{math|''n''}} को आधार {{math|''a''}} पर {{math|''x''}} का [[ असतत लघुगणक ]] (discrete logarithm) कहा जाता है। | ||
जबकि {{math|''a<sup>n</sup>''}} की गणना बहुत जल्दी की जा सकती है, उदाहरण के लिए [[ वर्ग द्वारा घातांक ]] का उपयोग करके, व्युत्क्रम संक्रिया, असतत लघुगणक की गणना के लिए कोई ज्ञात कुशल विधि | जबकि {{math|''a<sup>n</sup>''}} की गणना बहुत जल्दी की जा सकती है, उदाहरण के लिए [[ वर्ग द्वारा घातांक ]] का उपयोग करके, व्युत्क्रम संक्रिया, असतत लघुगणक की गणना के लिए कोई ज्ञात कुशल विधि नहीं है। इसका उपयोग विभिन्न [[ क्रिप्टोग्राफिक प्रोटोकॉल ]] में किया गया है, विवरण के लिए असतत लघुगणक देखें। | ||
जब {{math|GF(''q'')}} गैर-शून्य तत्वों को उनके असतत लघुगणक द्वारा दर्शाया जाता है, तो गुणा और भाग आसान होता है, क्योंकि वे जोड़ और घटाव मॉड्यूल {{math|''q'' – 1}} तक कम हो जाते हैं। हालांकि, {{math|''a''<sup>''m''</sup> + ''a''<sup>''n''</sup>}} के असतत लघुगणक की गणना करने के लिए अतिरिक्त मात्रा। पहचान . | जब {{math|GF(''q'')}} गैर-शून्य तत्वों को उनके असतत लघुगणक द्वारा दर्शाया जाता है, तो गुणा और भाग आसान होता है, क्योंकि वे जोड़ और घटाव मॉड्यूल {{math|''q'' – 1}} तक कम हो जाते हैं। हालांकि, {{math|''a''<sup>''m''</sup> + ''a''<sup>''n''</sup>}} के असतत लघुगणक की गणना करने के लिए अतिरिक्त मात्रा। पहचान . | ||
Line 250: | Line 250: | ||
{{math|1 =''n'' = 0, ..., ''q'' − 2}} के लिए, एक {{math|''a''<sup>''n''</sup> + 1}} के असतत लघुगणक की तालिका बनाकर इस समस्या को हल करने की अनुमति देता है जिसे Zech के लघुगणक कहा जाता है (शून्य के असतत लघुगणक को {{math|−∞}} के रूप में परिभाषित करना सुविधाजनक है)। | {{math|1 =''n'' = 0, ..., ''q'' − 2}} के लिए, एक {{math|''a''<sup>''n''</sup> + 1}} के असतत लघुगणक की तालिका बनाकर इस समस्या को हल करने की अनुमति देता है जिसे Zech के लघुगणक कहा जाता है (शून्य के असतत लघुगणक को {{math|−∞}} के रूप में परिभाषित करना सुविधाजनक है)। | ||
Zech के लघुगणक बड़ी गणनाओं के लिए उपयोगी होते हैं, जैसे कि मध्यम आकार के क्षेत्रों में रैखिक बीजगणित, अर्थात, ऐसे क्षेत्र जो प्राकृतिक विधि | Zech के लघुगणक बड़ी गणनाओं के लिए उपयोगी होते हैं, जैसे कि मध्यम आकार के क्षेत्रों में रैखिक बीजगणित, अर्थात, ऐसे क्षेत्र जो प्राकृतिक विधि को अप्रभावी बनाने के लिए पर्याप्त रूप से बड़े हैं, लेकिन बहुत बड़े नहीं हैं, क्योंकि किसी को उसी आकार की तालिका की पूर्व-गणना करनी होती है। क्षेत्र के आदेश के रूप में। | ||
=== [[ एकता की जड़ ]]ें इकाई के मूल === | === [[ एकता की जड़ ]]ें इकाई के मूल === | ||
Line 256: | Line 256: | ||
परिमित क्षेत्र का प्रत्येक अशून्य तत्व इकाई का मूल है, जैसे {{math|GF(''q'')}} के हर अशून्य तत्वों के लिए {{math|1=''x''<sup>''q''−1</sup> = 1}} के रूप में। | परिमित क्षेत्र का प्रत्येक अशून्य तत्व इकाई का मूल है, जैसे {{math|GF(''q'')}} के हर अशून्य तत्वों के लिए {{math|1=''x''<sup>''q''−1</sup> = 1}} के रूप में। | ||
यदि {{math|''n''}} एक धनात्मक पूर्णांक है, तो इकाई का {{math|''n''}}--वाँ अभाज्य | यदि {{math|''n''}} एक धनात्मक पूर्णांक है, तो इकाई का {{math|''n''}}--वाँ अभाज्य मूल समीकरण {{math|1=''x<sup>n</sup>'' = 1}} का एक हल है जो कि किसी भी धनात्मक पूर्णांक {{math|''m'' < ''n''}} के लिए समीकरण {{math|1=''x<sup>m</sup>'' = 1}} का हल नहीं है। यदि {{math|''a''}} क्षेत्र {{math|''F''}} में इकाई का {{math|''n''}} वां अभाज्य मूल है, तो {{math|''F''}} में इकाई के सभी {{math|''n''}} मूल हैं, जो {{math|1, ''a'', ''a''<sup>2</sup>, ..., ''a''<sup>''n''−1</sup>}} हैं। | ||
फील्ड {{math|GF(''q'')}} में इकाई का {{math|''n''}} वां अभाज्य मूल | फील्ड {{math|GF(''q'')}} में इकाई का {{math|''n''}} वां अभाज्य मूल है यदि और केवल यदि {{math|''n''}}, {{math|''q'' − 1}} का भाजक है; यदि {{math|''n''}}, q − 1 का एक भाजक है, तो {{math|GF(''q'')}} में इकाई के {{math|''n''}} वें अभाज्य मूलों की संख्या {{math|''φ''(''n'')}} (यूलर का पूर्ण फलन) है। {{math|GF(''q'')}} में इकाई के {{math|''n''}} वें मूलोंकी संख्या {{math|gcd(''n'', ''q'' − 1)}} है। | ||
{{math|''p''}} की विशेषता के क्षेत्र में, प्रत्येक {{math|(''np'')}} वां मूल इकाई का {{math|''n''}} वां मूल भी होता है। यह इस प्रकार है कि इकाई की अभाज्य {{math|(''np'')}} वां मूल कभी भी विशेषता p के क्षेत्र में मौजूद नहीं होता हैं। | {{math|''p''}} की विशेषता के क्षेत्र में, प्रत्येक {{math|(''np'')}} वां मूल इकाई का {{math|''n''}} वां मूल भी होता है। यह इस प्रकार है कि इकाई की अभाज्य {{math|(''np'')}} वां मूल कभी भी विशेषता p के क्षेत्र में मौजूद नहीं होता हैं। | ||
दूसरी ओर, यदि {{math|''n''}}, {{math|''p''}} का [[ सह अभाज्य ]] है, तो {{math|''n''}} वें साइक्लोटोमिक बहुपद | दूसरी ओर, यदि {{math|''n''}}, {{math|''p''}} का [[ सह अभाज्य ]] है, तो {{math|''n''}} वें साइक्लोटोमिक बहुपद के मूल {{math|''p''}} विशेषता के हर क्षेत्र में अलग हैं, क्योंकि यह बहुपद {{math|''X<sup>n</sup>'' − 1}} का एक भाजक है जिसका [[ विभेदक | विभेदक]] (discriminant) {{tmath|n^n}} गैर-शून्य मोडुलो {{mvar|p}} है यह इस प्रकार है कि {{math|GF(''p'')}} पर {{math|''n''}}th साइक्लोटॉमिक बहुपद कारक अलग-अलग अलघुकरणीय बहुपदों में होते हैं जिनकी सभी कोटि समान होती है, {{math|''d''}} कहते हैं, और यह कि {{math|GF(''p<sup>d</sup>'')}} विशेषता {{math|''p''}} का सबसे छोटा क्षेत्र है जिसमें इकाई के {{math|''n''}}th अभाज्य मूल होते हैं। | ||
=== उदाहरण: GF(64)=== | === उदाहरण: GF(64)=== | ||
फील्ड {{math|GF(64)}} में कई दिलचस्प गुण हैं जो छोटे क्षेत्र साझा नहीं करते हैं: इसमें दो उपक्षेत्र हैं जैसे कि कोई भी दूसरे में समाहित नहीं है; सभी जनरेटर ({{math|GF(2)}} पर कोटि {{math|6}} के न्यूनतम बहुपद वाले तत्व) अभाज्य तत्व | फील्ड {{math|GF(64)}} में कई दिलचस्प गुण हैं जो छोटे क्षेत्र साझा नहीं करते हैं: इसमें दो उपक्षेत्र हैं जैसे कि कोई भी दूसरे में समाहित नहीं है; सभी जनरेटर ({{math|GF(2)}} पर कोटि {{math|6}} के न्यूनतम बहुपद वाले तत्व) अभाज्य तत्व नहीं हैं; और अभाज्य तत्व गैलोइस समूह के अंतर्गत सभी संयुग्मित नहीं हैं। | ||
इस क्षेत्र का क्रम {{math|2<sup>6</sup>}}, और {{math|6}} के विभाजक {{math|1, 2, 3, 6}} हैं, {{math|GF(2)}}, {{math|1=GF(2<sup>2</sup>) = GF(4)}}, {{math|1=GF(2<sup>3</sup>) = GF(8)}}, तथा {{math|GF(64)}} ही {{math|GF(64)}} के उपक्षेत्र हैं । जैसा कि {{math|2}} तथा {{math|3}} सहअभाज्य | इस क्षेत्र का क्रम {{math|2<sup>6</sup>}}, और {{math|6}} के विभाजक {{math|1, 2, 3, 6}} हैं, {{math|GF(2)}}, {{math|1=GF(2<sup>2</sup>) = GF(4)}}, {{math|1=GF(2<sup>3</sup>) = GF(8)}}, तथा {{math|GF(64)}} ही {{math|GF(64)}} के उपक्षेत्र हैं । जैसा कि {{math|2}} तथा {{math|3}} सहअभाज्य हैं, {{math|GF(64)}} में {{math|GF(4)}} तथा {{math|GF(8)}} का प्रतिच्छेदन अभाज्य क्षेत्र {{math|GF(2)}} है। | ||
इस प्रकार {{math|GF(4)}} तथा {{math|GF(8)}} के समुच्चय (union) में {{math|10}} तत्व होते हैं। {{math|GF(64)}} के शेष {{math|54}} तत्व इस अर्थ में {{math|GF(64)}} उत्पन्न करते हैं कि किसी अन्य उपक्षेत्र में उनमें से कोई भी शामिल नहीं है। यह इस प्रकार है कि वे {{math|GF(2)}} पर कोटि {{math|6}} के अलघुकरणीय बहुपदों के मूल | इस प्रकार {{math|GF(4)}} तथा {{math|GF(8)}} के समुच्चय (union) में {{math|10}} तत्व होते हैं। {{math|GF(64)}} के शेष {{math|54}} तत्व इस अर्थ में {{math|GF(64)}} उत्पन्न करते हैं कि किसी अन्य उपक्षेत्र में उनमें से कोई भी शामिल नहीं है। यह इस प्रकार है कि वे {{math|GF(2)}} पर कोटि {{math|6}} के अलघुकरणीय बहुपदों के मूल हैं। इसका तात्पर्य है कि, {{math|GF(2)}} के ऊपर कोटि {{math|6}} के बिल्कुल {{math|1=9 = {{sfrac|54|6}}}} अलघुकरणीय मोनिक बहुपद हैं। इसे {{math|''X''<sup>64</sup> − ''X''}} के ऊपर {{math|GF(2)}} का फैक्टरिंग करके सत्यापित किया जा सकता है। | ||
{{math|GF(64)}} के तत्व कुछ {{math|''n''}} विभाजक {{math|63}} के लिए इकाई के {{math|''n''}}th अभाज्य मूल हैं। इकाई के तीसरे और सातवें वें मूल क्रमशः {{math|GF(4)}} तथा {{math|GF(8)}} की हैं, {{math|{9, 21, 63}<nowiki/>}} में कुछ {{math|''n''}} के लिए इकाई के {{math|54}} जनक | {{math|GF(64)}} के तत्व कुछ {{math|''n''}} विभाजक {{math|63}} के लिए इकाई के {{math|''n''}}th अभाज्य मूल हैं। इकाई के तीसरे और सातवें वें मूल क्रमशः {{math|GF(4)}} तथा {{math|GF(8)}} की हैं, {{math|{9, 21, 63}<nowiki/>}} में कुछ {{math|''n''}} के लिए इकाई के {{math|54}} जनक {{math|''n''}}th अभाज्य मूल हैं। यूलर के टोटिएंट फलन से पता चलता है कि इकाई के {{math|6}} आदिम {{math|9}} वें मूल , इकाई के {{math|12}} अभाज्य {{math|21}} वें मूल और इकाई के {{math|36}} आदिम {{math|63}} वें मूल हैं। इन संख्याओं का योग करने पर फिर से {{math|54}} तत्व मिलते हैं। | ||
{{math|GF(2)}} पर साइक्लोटोमिक बहुपदों का गुणनखंडन करके, कोई पाता है कि: | {{math|GF(2)}} पर साइक्लोटोमिक बहुपदों का गुणनखंडन करके, कोई पाता है कि: | ||
*इकाई के {{math|9}} वें छह अभाज्य मूल, मूल हैं <math display="block">X^6+X^3+1,</math> और सभी गैलोइस समूह की कार्रवाई के तहत संयुग्मित | *इकाई के {{math|9}} वें छह अभाज्य मूल, मूल हैं <math display="block">X^6+X^3+1,</math> और सभी गैलोइस समूह की कार्रवाई के तहत संयुग्मित हैं। | ||
* इकाई के {{math|21}} वें बारह अभाज्य मूल, मूल हैं <math display="block">(X^6+X^4+X^2+X+1)(X^6+X^5+X^4+X^2+1).</math> गैलोइस समूह की कार्रवाई के तहत वे दो कक्षाएँ बनाते हैं। चूंकि दो कारक एक दूसरे के [[ पारस्परिक बहुपद ]] हैं, एक मूल और इसका (गुणात्मक) व्युत्क्रम एक ही कक्षा से संबंधित नहीं है। | * इकाई के {{math|21}} वें बारह अभाज्य मूल, मूल हैं <math display="block">(X^6+X^4+X^2+X+1)(X^6+X^5+X^4+X^2+1).</math> गैलोइस समूह की कार्रवाई के तहत वे दो कक्षाएँ बनाते हैं। चूंकि दो कारक एक दूसरे के [[ पारस्परिक बहुपद ]] हैं, एक मूल और इसका (गुणात्मक) व्युत्क्रम एक ही कक्षा से संबंधित नहीं है। | ||
* {{math|1=GF(64)}} के {{math|36}} अभाज्य तत्व के मूल हैं <math display="block">(X^6+X^4+X^3+X+1)(X^6+X+1)(X^6+X^5+1)(X^6+X^5+X^3+X^2+1)(X^6+X^5+X^2+X+1)(X^6+X^5+X^4+X+1).</math> गैलोइस समूह की कार्रवाई के तहत वे छह तत्वों की छह कक्षाओं में विभाजित हो गए। | * {{math|1=GF(64)}} के {{math|36}} अभाज्य तत्व के मूल हैं <math display="block">(X^6+X^4+X^3+X+1)(X^6+X+1)(X^6+X^5+1)(X^6+X^5+X^3+X^2+1)(X^6+X^5+X^2+X+1)(X^6+X^5+X^4+X+1).</math> गैलोइस समूह की कार्रवाई के तहत वे छह तत्वों की छह कक्षाओं में विभाजित हो गए। | ||
इससे पता चलता है कि {{math|GF(64)}} के निर्माण के लिए सबसे अच्छा विकल्प इसे {{math|GF(2)[''X''] / (''X''<sup>6</sup> + ''X'' + 1)}} के रूप में परिभाषित करना है। वास्तव में, यह जनक | इससे पता चलता है कि {{math|GF(64)}} के निर्माण के लिए सबसे अच्छा विकल्प इसे {{math|GF(2)[''X''] / (''X''<sup>6</sup> + ''X'' + 1)}} के रूप में परिभाषित करना है। वास्तव में, यह जनक एक अभाज्य तत्व है, और यह बहुपद अलघुकरणीय बहुपद है जो सबसे आसान यूक्लिडियन विभाजन उत्पन्न करता है। | ||
==Frobenius automorphism और Galois सिद्धांत == | ==Frobenius automorphism और Galois सिद्धांत == | ||
Line 293: | Line 293: | ||
<math display="block">X^{p^k}-X</math>{{math|''p<sup>k</sup>''}} मूलों से अधिक होगा। | <math display="block">X^{p^k}-X</math>{{math|''p<sup>k</sup>''}} मूलों से अधिक होगा। | ||
{{math|GF(''p'')}} का कोई अन्य {{math|GF(''q'')}} -स्वरूपण | {{math|GF(''p'')}} का कोई अन्य {{math|GF(''q'')}} -स्वरूपण नहीं हैं। दूसरे शब्दों में, {{math|GF(''p<sup>n</sup>'')}} के बिल्कुल {{math|''n''}} {{math|GF(''p'')}}-स्वरूपण (automorphism) है, जो हैं | ||
<math display="block">\mathrm{Id}=\varphi^0, \varphi, \varphi^2, \ldots, \varphi^{n-1}.</math> | <math display="block">\mathrm{Id}=\varphi^0, \varphi, \varphi^2, \ldots, \varphi^{n-1}.</math> | ||
गैलोइस सिद्धांत के संदर्भ में, इसका अर्थ है कि {{math|GF(''p<sup>n</sup>'')}}, {{math|GF(''p'')}} का गैलोइस विस्तार है, जिसमें चक्रीय गैलोज समूह है। | गैलोइस सिद्धांत के संदर्भ में, इसका अर्थ है कि {{math|GF(''p<sup>n</sup>'')}}, {{math|GF(''p'')}} का गैलोइस विस्तार है, जिसमें चक्रीय गैलोज समूह है। | ||
तथ्य यह है कि फ्रोबेनियस मानचित्र विशेषण (surjective) है, इसका तात्पर्य है कि प्रत्येक परिमित क्षेत्र पूर्ण क्षेत्र | तथ्य यह है कि फ्रोबेनियस मानचित्र विशेषण (surjective) है, इसका तात्पर्य है कि प्रत्येक परिमित क्षेत्र पूर्ण क्षेत्र है। | ||
==बहुपद गुणनखंड== | ==बहुपद गुणनखंड== | ||
{{main|Factorization of polynomials over finite fields}} | {{main|Factorization of polynomials over finite fields}} | ||
यदि {{math|''F''}} एक परिमित क्षेत्र है, तो {{math|''F''}} में गुणांक के साथ एक गैर-स्थिर [[ मोनिक बहुपद ]] {{math|''F''}} पर अलघुकरणीय | यदि {{math|''F''}} एक परिमित क्षेत्र है, तो {{math|''F''}} में गुणांक के साथ एक गैर-स्थिर [[ मोनिक बहुपद ]] {{math|''F''}} पर अलघुकरणीय है, यदि यह {{math|''F''}} में गुणांक वाले दो गैर-स्थिर मोनिक बहुपदों का गुणनफल नहीं है। | ||
चूंकि एक क्षेत्र पर प्रत्येक [[ बहुपद वलय ]] एक अद्वितीय गुणनखंडन अनुक्षेत्र (unique factorization domain) है, एक परिमित क्षेत्र पर प्रत्येक मोनिक बहुपद को एक अद्वितीय तरीके से (कारकों के क्रम तक) अखंडनीय (irreducible) मोनिक बहुपद के गुणन में विभाजित किया जा सकता है। परिमित क्षेत्र पर बहुपद इरेड्यूसबिलिटी और फैक्टरिंग बहुपदों के परीक्षण के लिए कुशल एल्गोरिदम हैं। वे पूर्णांकों या परिमेय संख्याओं पर बहुपदों का गुणनखण्ड करने के लिए एक महत्वपूर्ण कदम हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर, या कम से कम, परिमित प्रधान क्षेत्रों पर बहुपदों के गुणनखंडन के लिए कार्य होते हैं। | चूंकि एक क्षेत्र पर प्रत्येक [[ बहुपद वलय ]] एक अद्वितीय गुणनखंडन अनुक्षेत्र (unique factorization domain) है, एक परिमित क्षेत्र पर प्रत्येक मोनिक बहुपद को एक अद्वितीय तरीके से (कारकों के क्रम तक) अखंडनीय (irreducible) मोनिक बहुपद के गुणन में विभाजित किया जा सकता है। परिमित क्षेत्र पर बहुपद इरेड्यूसबिलिटी और फैक्टरिंग बहुपदों के परीक्षण के लिए कुशल एल्गोरिदम हैं। वे पूर्णांकों या परिमेय संख्याओं पर बहुपदों का गुणनखण्ड करने के लिए एक महत्वपूर्ण कदम हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर, या कम से कम, परिमित प्रधान क्षेत्रों पर बहुपदों के गुणनखंडन के लिए कार्य होते हैं। | ||
परिमित क्षेत्र में बहुपद अलघुकरणीय | परिमित क्षेत्र में बहुपद अलघुकरणीय और विभाजित बहुपदों के परीक्षण के लिए कुशल प्रणाली हैं। वे पूर्णांकों या [[ परिमेय संख्या ]]ओं पर बहुपदों के गुणनखंड के लिए एक महत्वपूर्ण चरण हैं। कम से कम इस कारण से, प्रत्येक [[ कंप्यूटर बीजगणित प्रणाली ]] में परिमित क्षेत्रों पर, या कम से कम, परिमित अभाज्य क्षेत्रों में बहुपदों के गुणनखंडन के लिए कार्य होते हैं। | ||
=== दी गई डिग्री के अमिट बहुपद === | === दी गई डिग्री के अमिट बहुपद === | ||
Line 311: | Line 311: | ||
<math display="block">X^q-X</math>एक क्षेत्र पर रैखिक गुणन खंड में क्रम {{math|''q''}} के गुणन खंड। अधिक सटीक रूप से, यह बहुपद क्रम {{math|''q''}} के क्षेत्र में एक कोटि के सभी मोनिक बहुपदों का गुणन है। | <math display="block">X^q-X</math>एक क्षेत्र पर रैखिक गुणन खंड में क्रम {{math|''q''}} के गुणन खंड। अधिक सटीक रूप से, यह बहुपद क्रम {{math|''q''}} के क्षेत्र में एक कोटि के सभी मोनिक बहुपदों का गुणन है। | ||
इसका तात्पर्य यह है कि, यदि {{math|1=''q'' = ''p<sup>n</sup>''}} तो {{math|''X<sup>q</sup>'' − ''X''}} पर सभी मोनिक अलघुकरणीय | इसका तात्पर्य यह है कि, यदि {{math|1=''q'' = ''p<sup>n</sup>''}} तो {{math|''X<sup>q</sup>'' − ''X''}} पर सभी मोनिक अलघुकरणीय बहुपदों का गुणनफल है जिसकी कोटि {{math|''n''}} को विभाजित करती है। वास्तव में, यदि {{math|''P''}}, {{math|''X<sup>q</sup>'' − ''X''}} के {{math|GF(''p'')}} पर एक अलघुकरणीय गुणनखंड है, तो इसकी कोटि {{math|''n''}} को विभाजित करती है, क्योंकि इसका विभाजन क्षेत्र (splitting field) {{math|GF(''p''<sup>''n''</sup>)}} में समाहित है। इसके विपरीत, यदि कोटि {{math|''d''}}, {{math|GF(''p'')}} पर एक अलघुकरणीय मोनिक बहुपद है, तो यह कोटि {{math|''d''}} के क्षेत्र विस्तार को परिभाषित करता है, जो {{math|GF(''p''<sup>''n''</sup>)}} में निहित है , और {{math|''P''}} के सभी मूल {{math|GF(''p''<sup>''n''</sup>)}} से संबंधित हैं। और {{math|''X<sup>q</sup>'' − ''X''}} के मूल हैं; इस प्रकार {{math|''P''}}, {{math|''X<sup>q</sup>'' − ''X''}} को विभाजित करता है। चूंकि {{math|''X<sup>q</sup>'' − ''X''}} का कोई विविध गुणन खंड नहीं है, इसलिए यह सभी अलघुकरणीय मोनिक बहुपदों का गुणन है जो इसे विभाजित करते हैं। | ||
इस गुण का उपयोग {{math|GF(''p'')}} पर बहुपदों की प्रत्येक कोटि के अलघुकरणीय गुणनखंड के गुणन की गणना करने के लिए किया जाता है; भिन्न कोटि गुणनखंड | इस गुण का उपयोग {{math|GF(''p'')}} पर बहुपदों की प्रत्येक कोटि के अलघुकरणीय गुणनखंड के गुणन की गणना करने के लिए किया जाता है; भिन्न कोटि गुणनखंड देखें। | ||
=== एक परिमित क्षेत्र पर दी गई डिग्री के मोनिक इरेड्यूसबल बहुपदों की संख्या === | === एक परिमित क्षेत्र पर दी गई डिग्री के मोनिक इरेड्यूसबल बहुपदों की संख्या === |
Revision as of 15:58, 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, अभाज्य तत्व अद्वितीय (unique) नहीं है। अभाज्य तत्वों की संख्या φ(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, इसलिए
निरपेक्ष गैलोइस समूह अनंत समूह है
अर्ध-बीजगणितीय बंद
हालांकि परिमित क्षेत्र (finite field) बीजगणितीय रूप से बंद (close) नहीं होते हैं, वे अर्ध-बीजगणितीय रूप से बंद क्षेत्र होते हैं| अर्ध-बीजगणितीय रूप से बंद (close), जिसका अर्थ है कि परिमित क्षेत्र में प्रत्येक सजातीय बहुपद (homogeneous polynomial) में एक गैर-नगण्य (non-trivial) शून्य होता है जिसके घटक (components) क्षेत्र (field) में होते हैं यदि इसके चर की संख्या इसकी कोटि (डिग्री) से अधिक है। यह एमिल आर्टिन और लियोनार्ड यूजीन डिक्सन का अनुमान था जिसे क्लाउड शेवेली द्वारा सिद्ध किया गया था (देखें शेवेली-चेतावनी प्रमेय)।
वेडरबर्न की छोटी प्रमेय
एक विभाजन वलय ( डिवीजन रिंग ) क्षेत्र का सामान्यीकरण है। विभाजन वलय ( डिवीजन रिंग ) को क्रमविनिमेय (कम्यूटेटिव) नहीं माना जाता है। कोई गैर-क्रमविनिमेय (नॉन कम्यूटेटिव ) परिमित विभाजन वलय ( डिवीजन रिंग ) नहीं हैं: वेडरबर्न की छोटी प्रमेय में कहा गया है कि सभी परिमित विभाजन वलय (डिवीजन रिंग) क्रमविनिमेय (कम्यूटेटिव) हैं, और इसलिए परिमित क्षेत्र (finite field) हैं। यह परिणाम तब भी कायम रहता है जब हम वैकल्पिकता के लिए संबद्धता की सूक्ति को शिथिल (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.