परिमित क्षेत्र: Difference between revisions
No edit summary |
No edit summary |
||
Line 219: | Line 219: | ||
जहाँ {{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|''α''}} को दिए गए अलघुकरणीय बहुपद (irreducible polynomials) के मूल के रूप में परिभाषित किया गया है)। जैसा कि {{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 302: | Line 302: | ||
==बहुपद गुणनखंड== | ==बहुपद गुणनखंड== | ||
{{main|Factorization of polynomials over finite fields}} | {{main|Factorization of polynomials over finite fields}} | ||
यदि {{math|''F''}} एक परिमित क्षेत्र है, गुणांक के साथ एक गैर-स्थिर [[ मोनिक बहुपद ]] | यदि {{math|''F''}} एक परिमित क्षेत्र है, तो {{math|''F''}} में गुणांक के साथ एक गैर-स्थिर [[ मोनिक बहुपद ]] {{math|''F''}} पर अलघुकरणीय (irreducible) है, यदि यह {{math|''F''}} में गुणांक वाले दो गैर-स्थिर मोनिक बहुपदों का गुणनफल नहीं है। | ||
चूंकि एक क्षेत्र पर प्रत्येक [[ बहुपद वलय ]] एक अद्वितीय गुणनखंडन | चूंकि एक क्षेत्र पर प्रत्येक [[ बहुपद वलय ]] एक अद्वितीय गुणनखंडन अनुक्षेत्र (unique factorization domain) है, एक परिमित क्षेत्र पर प्रत्येक मोनिक बहुपद को एक अद्वितीय तरीके से (कारकों के क्रम तक) अखंडनीय (irreducible) मोनिक बहुपद के गुणन में विभाजित किया जा सकता है। परिमित क्षेत्र पर बहुपद इरेड्यूसबिलिटी और फैक्टरिंग बहुपदों के परीक्षण के लिए कुशल एल्गोरिदम हैं। वे पूर्णांकों या परिमेय संख्याओं पर बहुपदों का गुणनखण्ड करने के लिए एक महत्वपूर्ण कदम हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर, या कम से कम, परिमित प्रधान क्षेत्रों पर बहुपदों के गुणनखंडन के लिए कार्य होते हैं। | ||
परिमित क्षेत्र में बहुपद | परिमित क्षेत्र में बहुपद अलघुकरणीय (irreducible) और विभाजित बहुपदों के परीक्षण के लिए कुशल प्रणाली (algorithm) हैं। वे पूर्णांकों या [[ परिमेय संख्या ]]ओं पर बहुपदों के गुणनखंड के लिए एक महत्वपूर्ण चरण हैं। कम से कम इस कारण से, प्रत्येक [[ कंप्यूटर बीजगणित प्रणाली ]] में परिमित क्षेत्रों पर, या कम से कम, परिमित प्रमुख क्षेत्रों में ( finite prime fields) बहुपदों के गुणनखंडन के लिए कार्य होते हैं। | ||
=== दी गई डिग्री के अमिट बहुपद === | === दी गई डिग्री के अमिट बहुपद === |
Revision as of 16:17, 19 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) |
Algebraic structures |
---|
गणित में, एक परिमित क्षेत्र (finite field) या गैलोइस क्षेत्र (Évariste Galois के सम्मान में तथाकथित) एक क्षेत्र (गणित) है जिसमें तत्व (गणित) की एक सीमित संख्या होती है। किसी भी क्षेत्र की तरह, एक परिमित क्षेत्र एक सेट (गणित) होता है, जिस पर गुणन, जोड़, घटाव और भाग के संचालन परिभाषित होते हैं और कुछ बुनियादी नियमों को पूरा करते हैं। परिमित क्षेत्रों के सबसे सामान्य उदाहरण पूर्णांक mod p (integers mod p) द्वारा दिए गए हैं जब p एक अभाज्य संख्या है।
एक परिमित क्षेत्र (finite field) का क्रम (order) उसके तत्वों की संख्या है, जो या तो एक अभाज्य संख्या या एक अभाज्य घात है। प्रत्येक अभाज्य संख्या के लिए p और प्रत्येक धनात्मक पूर्णांक k के लिए क्रम के क्षेत्र हैं, जो सभी समरूपी हैं।
गणित और कंप्यूटर विज्ञान के कई क्षेत्रों में परिमित क्षेत्र (finite field) मौलिक हैं, जिनमें संख्या सिद्धांत , बीजगणितीय ज्यामिति , गैलोइस सिद्धांत , परिमित ज्यामिति , क्रिप्टोग्राफी और कोडिंग सिद्धांत शामिल हैं।
गुण
एक परिमित क्षेत्र (finite field) एक परिमित समुच्चय है जो एक क्षेत्र (गणित) है; इसका मतलब है कि गुणा, जोड़, घटाव और भाग (शून्य से भाग को छोड़कर) परिभाषित हैं और क्षेत्र सिद्धांतों के रूप में ज्ञात अंकगणित के नियमों को पूरा करते हैं।
एक परिमित क्षेत्र (finite field) के तत्वों की संख्या को इसका क्रम (order) या, कभी-कभी, इसका आकार कहा जाता है। q क्रम (order) का एक परिमित क्षेत्र (finite field) मौजूद है अगर और केवल अगर q एक प्रमुख संख्या (prime number) है pk (जहां p एक अभाज्य संख्या है और k एक धनात्मक पूर्णांक है)। क्रम (order) pk के क्षेत्र में, किसी भी तत्व की p प्रतियां जोड़ने पर परिणाम हमेशा शून्य होता है ; यानी क्षेत्र की विशेषता (बीजगणित) p है।
यदि q = pk, क्रम (order) के सभी क्षेत्र q समरूपी हैं (देखें § Existence and uniqueness नीचे)।[1]इसके अलावा, एक क्षेत्र (फ़ील्ड) में समान क्रम वाले दो भिन्न परिमित क्षेत्र विस्तार नहीं हो सकते हैं। इसलिए एक ही क्रम के साथ सभी परिमित क्षेत्रों (finite fields) की पहचान की जा सकती है, और उन्हें स्पष्ट रूप से निरूपित किया जाता है , Fq या GF(q), जहां अक्षर GF "गैलॉइस फील्ड" के लिए है।[2] q क्रम (order) के एक परिमित क्षेत्र में, बहुपद Xq − X में परिमित क्षेत्र के सभी q तत्व मूल के रूप में होते हैं। एक परिमित क्षेत्र के गैर-शून्य तत्व एक गुणक समूह बनाते हैं। यह समूह चक्रीय समूह है, इसलिए सभी गैर-शून्य तत्वों को एक ही तत्व की घातों के रूप में व्यक्त किया जा सकता है जिसे क्षेत्र का एक आदिम तत्व (परिमित क्षेत्र) कहा जाता है। (सामान्य तौर पर किसी दिए गए क्षेत्र के लिए कई मौलिक तत्व होंगे।)
परिमित क्षेत्रों के सबसे सरल उदाहरण अभाज्य क्रम के क्षेत्र हैं: प्रत्येक अभाज्य संख्या p के लिए, क्रम (order) p का प्रमुख क्षेत्र , , पूर्णांक मॉड्यूल (integers modulo) p, Z/pZ के रूप में निर्मित किया जा सकता है।
p क्रम (order) के प्रमुख क्षेत्र के तत्वों को 0, ..., p − 1 श्रेणी में पूर्णांकों द्वारा दर्शाया जा सकता है। योग, अंतर और गुणनफल संगत पूर्णांक संक्रिया के परिणाम के p से विभाजन का शेषफल है। यूक्लिडियन डिवीजन द्वारा हैं p संबंधित पूर्णांक ऑपरेशन के परिणाम का। विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके किसी तत्व के गुणनात्मक व्युत्क्रम की गणना की जा सकती है (देखें Extended Euclidean algorithm § Modular integers)
मान लीजिए F एक परिमित क्षेत्र है। F में किसी भी तत्व x और किसी पूर्णांक n के लिए, n ⋅ x द्वारा x की n प्रतियों के योग को निरूपित करें। सबसे छोटा धनात्मक n ऐसा है कि n ⋅ 1 = 0 क्षेत्र की विशेषता p है। यह गुणन को परिभाषित करने की अनुमति देता है , GF(p) के एक तत्व k का F के एक तत्व x द्वारा k लिए एक पूर्णांक प्रतिनिधि (integer representative) चुनकर। यह गुणन F को GF(p)-सदिश स्थल (vector space) बनाता है। यह इस प्रकार है कि किसी पूर्णांक n के लिए F के तत्वों की संख्या pn है।
फ़र्मेट की छोटी प्रमेय के अनुसार, यदि p एक अभाज्य संख्या है और x क्षेत्र (फ़ील्ड) GF(p) में है तो xp = x. इसका तात्पर्य समानता से है
परिमित क्षेत्र (finite field) का कोई भी परिमित क्षेत्र विस्तार (finite field extension) वियोज्य (separable) और सरल (simple) है। यानी अगर E एक परिमित क्षेत्र (finite field) है और F, E का एक उपक्षेत्र (subfield) है , तो E को F से एक एकल तत्व जिसका न्यूनतम बहुपद (क्षेत्र सिद्धांत) वियोज्य (separable) है से जोड़कर प्राप्त किया जाता है। एक शब्दजाल (jargon) का उपयोग करने के लिए, परिमित क्षेत्र (finite fields) सही क्षेत्र (perfect) हैं।
एक अधिक सामान्य बीजगणितीय संरचना जो एक क्षेत्र (field) की अन्य सभी सूक्तियों (axioms) को संतुष्ट करती है, लेकिन जिसके गुणन को क्रमविनिमेय (commutative) होने की आवश्यकता नहीं होती है, उसे विभाजन की अंगूठी (division ring) या कभी-कभी विषम क्षेत्र (skew field) कहा जाता है। वेडरबर्न की छोटी प्रमेय के अनुसार, कोई भी परिमित विभाजन वलय (finite division ring) क्रमविनिमेय (commutative) होता है, और इसलिए एक परिमित क्षेत्र (finite field) होता है।
अस्तित्व और विशिष्टता
मान लीजिए q = pn एक प्रमुख घात (prime power) है, और F बहुपद (polynomial) का विभाजन क्षेत्र (splitting field) हो
बंटवारे वाले क्षेत्रों के समरूपता तक की विशिष्टता का तात्पर्य इस प्रकार है कि क्रम के सभी क्षेत्र q समरूपी हैं। इसके अलावा, यदि कोई क्षेत्र F आदेश का एक क्षेत्र है q = pk एक उपक्षेत्र के रूप में, इसके तत्व हैं q की जड़ें Xq − X, तथा F आदेश का एक और उपक्षेत्र नहीं हो सकता q.
संक्षेप में, हमारे पास निम्नलिखित वर्गीकरण प्रमेय है जिसे पहली बार 1893 में ई. एच. मूर द्वारा सिद्ध किया गया था:[1]
एक परिमित क्षेत्र का क्रम एक प्रमुख शक्ति है। हर प्रधान शक्ति के लिए q आदेश के क्षेत्र हैं q, और वे सभी समरूपी हैं। इन क्षेत्रों में हर तत्व संतुष्ट
और बहुपद Xq − X कारक के रूप में
यह इस प्रकार है कि GF(pn) इसमें एक सबफील्ड आइसोमॉर्फिक शामिल है GF(pm) अगर और केवल अगर m का भाजक है n; उस स्थिति में, यह उपक्षेत्र अद्वितीय है। वास्तव में, बहुपद Xpm − X विभाजित Xpn − X अगर और केवल अगर m का भाजक है n.
स्पष्ट निर्माण
गैर-अभाज्य क्षेत्र
p अभाज्य (prime) और n > 1 के साथ एक प्रमुख घात (prime power) q = pn को देखते हुए, फ़ील्ड GF(q) को स्पष्ट रूप से निम्नलिखित तरीके से स्पष्ट रूप से बनाया जा सकता है। सबसे पहले डिग्री n के GF(p)[X] में एक अलघुकरणीय बहुपद (irreducible polynomial) P चुनते है (इस तरह का एक अलघुकरणीय बहुपद (irreducible polynomial) हमेशा मौजूद रहता है)। फिर भागफल वलय (quotient ring)
अधिक स्पष्ट रूप से, GF(q) के तत्व GF(p) पर बहुपद हैं जिसकी कोटि निश्चित रूप से n से कम है। जोड़ और घटाना GF(p) पर बहुपदों के हैं। दो तत्वों का गुणन GF(p)[X] में P के गुणन द्वारा यूक्लिडियन भाग (Euclidean division) का शेषफल है। एक गैर-शून्य तत्व के गुणात्मक व्युत्क्रम की गणना विस्तारित यूक्लिडियन एल्गोरिथम (extended Euclidean algorithm) के साथ की जा सकती है; देखें विस्तारित यूक्लिडियन एल्गोरिथम (extended Euclidean algorithm) § सरल बीजगणितीय क्षेत्र विस्तार (Simple algebraic field extensions) ।
GF(4) के निर्माण को छोड़कर, P के लिए कई संभावित विकल्प हैं, जो समरूपी (isomorphic) परिणाम उत्पन्न करते हैं। यूक्लिडियन भाग (Euclidean division) को सरल बनाने के लिए, आमतौर पर P के लिए एक बहुपद चुनता है
अगले खंडों में, हम दिखाएंगे कि ऊपर उल्लिखित सामान्य निर्माण विधि छोटे परिमित क्षेत्रों के लिए कैसे काम करती है।
चार तत्वों वाला क्षेत्र
सबसे छोटा गैर-अभाज्य क्षेत्र (non-prime field) चार तत्वों वाला क्षेत्र है, जिसे आमतौर पर GF(4) या के रूप दर्शाया जाता है इसमें चार तत्व होते हैं जैसे कि तथा प्रत्येक के लिए अन्य संक्रिया (operation) के परिणाम वितरण कानून (distributive law) से आसानी से निकाले जा सकते हैं। पूर्ण संक्रिया सारिणी (complete operation tables) के लिए नीचे देखें।
इसे पिछले खंड के परिणामों से निम्नानुसार घटाया जा सकता है।
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) की योगात्मक संरचना क्लेन फोर-ग्रुप के लिए समरूपी (isomorphic) है, जबकि गैर-शून्य गुणात्मक संरचना Z3 के लिए समरूपी (isomorphic) है।
नक्शा
GF(p2) विषम अभाज्य p के लिए
GF(p2) के मामले में परिमित क्षेत्रों के #गैर-अभाज्य क्षेत्रों को लागू करने के लिए, व्यक्ति को 2 कोटि (degree) का एक अलघुकरणीय बहुपद ( irreducible polynomials) ज्ञात करना होता है। p = 2, यह पिछले अनुभाग में किया गया है। यदि p एक विषम अभाज्य संख्या है, तो GF(p) में r के साथ X2 − r के रूप में हमेशा अलघुकरणीय बहुपद ( irreducible polynomials) होते हैं।
अधिक सटीक रूप से, बहुपद X2 − r, GF(p) पर अलघुकरणीय ( irreducible) है यदि और केवल यदि 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) के रूप में चुन सकता है, जो हमें एक बहुत ही सरल अलघुकरणीय बहुपद (irreducible polynomials) X2 + 1 प्राप्त करने की अनुमति देता है।
एक द्विघात गैर-अवशेष (quadratic non-residue) r को चुनने के बाद, α को r का एक प्रतीकात्मक वर्गमूल माने यह एक प्रतीक है, जिसमें गुण (property) α2 = r हैं, ठीक उसी तरह जैसे सम्मिश्र संख्या i का प्रतीकात्मक वर्गमूल −1 है। फिर, GF(p2) के तत्व सभी रैखिक व्यंजक (linear expressions) हैं
जीएफ(8) और जीएफ(27)
बहुपद
जहाँ a, b, c GF(2) या GF(3) (क्रमशः) के तत्व हैं और एक ऐसा प्रतीक है कि
जीएफ(16)
बहुपद
GF(2) पर अलघुकरणीय ( irreducible) है, अर्थात् यह अलघुकरणीय मोडुलो 2 है यह इस प्रकार है कि GF(16) के तत्व अभिव्यक्ति (गणित) द्वारा दर्शाए जा सकते है
गुणक संरचना
गैर-शून्य तत्वों का सेट GF(q) गुणन के तहत एक एबेलियन समूह है, क्रम q – 1 लैग्रेंज के प्रमेय (समूह सिद्धांत) द्वारा | लैग्रेंज की प्रमेय के अनुसार, एक भाजक मौजूद है q – 1 का एक भाजक k ऐसा है कि xk = 1 प्रत्येक गैर-शून्य x के लिए GF(q) में । चूंकि समीकरण xk = 1 का किसी भी क्षेत्र में अधिक से अधिक k हल हैं, q – 1, k के लिए उच्चतम संभव मान है। परिमित एबेलियन समूहों # की संरचना प्रमेय का तात्पर्य है कि यह गुणात्मक समूह चक्रीय समूह है, अर्थात सभी गैर-शून्य तत्व एक ही तत्व की घात हैं। सारांश:
ऐसे तत्व a अभाज्य तत्व (primitive elements) कहलाते हैं। जब तक q = 2, 3, अभाज्य तत्व (primitive elements) अद्वितीय (unique) नहीं है। अभाज्य तत्वों (primitive elements) की संख्या φ(q − 1) है जहां φ यूलर का टोटिएंट फलन है।
उपरोक्त परिणाम का तात्पर्य है कि GF(q) में प्रत्येक x के लिए xq = x । विशेष स्थिति जहां q अभाज्य है, फर्मेट की छोटी प्रमेय है।
असतत लघुगणक
यदि a, GF(q) में एक अभाज्य तत्व (primitive element) है, तो F में किसी भी गैर-शून्य तत्व x के लिए, 0 ≤ n ≤ q − 2 के साथ एक अद्वितीय पूर्णांक n होता है, जैसे कि
इस पूर्णांक n को आधार a पर x का असतत लघुगणक (discrete logarithm) कहा जाता है।
जबकि an की गणना बहुत जल्दी की जा सकती है, उदाहरण के लिए वर्ग द्वारा घातांक का उपयोग करके, व्युत्क्रम संक्रिया, असतत लघुगणक की गणना के लिए कोई ज्ञात कुशल विधि (efficient algorithm) नहीं है। इसका उपयोग विभिन्न क्रिप्टोग्राफिक प्रोटोकॉल में किया गया है, विवरण के लिए असतत लघुगणक देखें।
जब GF(q) गैर-शून्य तत्वों को उनके असतत लघुगणक द्वारा दर्शाया जाता है, तो गुणा और भाग आसान होता है, क्योंकि वे जोड़ और घटाव मॉड्यूल q – 1 तक कम हो जाते हैं। हालांकि, am + an के असतत लघुगणक की गणना करने के लिए अतिरिक्त मात्रा। पहचान .
n = 0, ..., q − 2 के लिए, एक an + 1 के असतत लघुगणक की तालिका बनाकर इस समस्या को हल करने की अनुमति देता है जिसे Zech के लघुगणक कहा जाता है (शून्य के असतत लघुगणक को −∞ के रूप में परिभाषित करना सुविधाजनक है)।
Zech के लघुगणक बड़ी गणनाओं के लिए उपयोगी होते हैं, जैसे कि मध्यम आकार के क्षेत्रों में रैखिक बीजगणित, अर्थात, ऐसे क्षेत्र जो प्राकृतिक विधि (natural algorithm) को अप्रभावी (inefficient) बनाने के लिए पर्याप्त रूप से बड़े हैं, लेकिन बहुत बड़े नहीं हैं, क्योंकि किसी को उसी आकार की तालिका की पूर्व-गणना करनी होती है। क्षेत्र के आदेश के रूप में।
एकता की जड़ ें इकाई के मूल
परिमित क्षेत्र का प्रत्येक अशून्य तत्व इकाई का मूल है, जैसे GF(q) के हर अशून्य तत्वों के लिए xq−1 = 1 के रूप में।
यदि n एक धनात्मक पूर्णांक है, तो इकाई का n--वाँ अभाज्य (primitive) मूल समीकरण xn = 1 का एक हल है जो कि किसी भी धनात्मक पूर्णांक m < n के लिए समीकरण xm = 1 का हल नहीं है। यदि a क्षेत्र F में इकाई का n वां अभाज्य मूल (primitive root) है, तो F में इकाई के सभी n मूल हैं, जो 1, a, a2, ..., an−1 हैं।
फील्ड GF(q) में इकाई का n वां अभाज्य मूल (primitive root) है यदि और केवल यदि n, q − 1 का भाजक है; यदि n, q − 1 का एक भाजक है, तो GF(q) में इकाई के n वें अभाज्य मूलों (primitive roots) की संख्या φ(n) (यूलर का पूर्ण फलन) है। GF(q) में इकाई के n वें मूलोंकी संख्या gcd(n, q − 1) है।
p की विशेषता के क्षेत्र में, प्रत्येक (np) वां मूल इकाई का n वां मूल भी होता है। यह इस प्रकार है कि इकाई की अभाज्य (np) वां मूल कभी भी विशेषता p के क्षेत्र में मौजूद नहीं होता हैं।
दूसरी ओर, यदि n, p का सह अभाज्य है, तो n वें साइक्लोटोमिक बहुपद (cyclotomic polynomial) के मूल p विशेषता के हर क्षेत्र में अलग हैं, क्योंकि यह बहुपद Xn − 1 का एक भाजक है जिसका विभेदक (discriminant) गैर-शून्य मोडुलो p है यह इस प्रकार है कि GF(p) पर nth साइक्लोटॉमिक बहुपद (cyclotomic polynomial) कारक अलग-अलग अलघुकरणीय बहुपदों में होते हैं जिनकी सभी कोटि समान होती है, d कहते हैं, और यह कि GF(pd) विशेषता p का सबसे छोटा क्षेत्र है जिसमें इकाई के nth अभाज्य मूल (primitive roots) होते हैं।
उदाहरण: GF(64)
फील्ड GF(64) में कई दिलचस्प गुण हैं जो छोटे क्षेत्र साझा नहीं करते हैं: इसमें दो उपक्षेत्र हैं जैसे कि कोई भी दूसरे में समाहित नहीं है; सभी जनरेटर (GF(2) पर कोटि 6 के न्यूनतम बहुपद वाले तत्व) अभाज्य तत्व (primitive element) नहीं हैं; और अभाज्य तत्व (primitive element) गैलोइस समूह के अंतर्गत सभी संयुग्मित नहीं हैं।
इस क्षेत्र का क्रम 26, और 6 के विभाजक 1, 2, 3, 6 हैं, GF(2), GF(22) = GF(4), GF(23) = GF(8), तथा GF(64) ही GF(64) के उपक्षेत्र हैं । जैसा कि 2 तथा 3 सहअभाज्य (co-prime) हैं, GF(64) में GF(4) तथा GF(8) का प्रतिच्छेदन प्रमुख क्षेत्र GF(2) है।
इस प्रकार GF(4) तथा GF(8) के समुच्चय (union) में 10 तत्व होते हैं। GF(64) के शेष 54 तत्व इस अर्थ में GF(64) उत्पन्न करते हैं कि किसी अन्य उपक्षेत्र में उनमें से कोई भी शामिल नहीं है। यह इस प्रकार है कि वे GF(2) पर कोटि 6 के अलघुकरणीय बहुपदों के मूल (roots) हैं। इसका तात्पर्य है कि, GF(2) के ऊपर कोटि 6 के बिल्कुल 9 = 54/6 अलघुकरणीय मोनिक बहुपद हैं। इसे X64 − X के ऊपर GF(2) का फैक्टरिंग करके सत्यापित किया जा सकता है।
GF(64) के तत्व कुछ n विभाजक 63 के लिए इकाई के nth अभाज्य मूल हैं। इकाई के तीसरे और सातवें वें मूल क्रमशः GF(4) तथा GF(8) की हैं, {9, 21, 63} में कुछ n के लिए इकाई के 54 जनक (generator) nth अभाज्य मूल हैं। यूलर के टोटिएंट फलन से पता चलता है कि इकाई के 6 आदिम 9 वें मूल , इकाई के 12 अभाज्य 21 वें मूल और इकाई के 36 आदिम 63 वें मूल हैं। इन संख्याओं का योग करने पर फिर से 54 तत्व मिलते हैं।
GF(2) पर साइक्लोटोमिक बहुपदों का गुणनखंडन करके, कोई पाता है कि:
- इकाई के 9 वें छह अभाज्य मूल, मूल हैं और सभी गैलोइस समूह की कार्रवाई के तहत संयुग्मित (conjugate) हैं।
- इकाई के 21 वें बारह अभाज्य मूल, मूल हैं गैलोइस समूह की कार्रवाई के तहत वे दो कक्षाएँ बनाते हैं। चूंकि दो कारक एक दूसरे के पारस्परिक बहुपद हैं, एक मूल और इसका (गुणात्मक) व्युत्क्रम एक ही कक्षा से संबंधित नहीं है।
- GF(64) के 36 अभाज्य तत्व के मूल हैं गैलोइस समूह की कार्रवाई के तहत वे छह तत्वों की छह कक्षाओं में विभाजित हो गए।
इससे पता चलता है कि GF(64) के निर्माण के लिए सबसे अच्छा विकल्प इसे GF(2)[X] / (X6 + X + 1) के रूप में परिभाषित करना है। वास्तव में, यह जनक (generator) एक अभाज्य तत्व है, और यह बहुपद अलघुकरणीय बहुपद है जो सबसे आसान यूक्लिडियन विभाजन (Euclidean division) उत्पन्न करता है।
Frobenius automorphism और Galois सिद्धांत
इस खंड में, p एक अभाज्य संख्या है, और q = pn, p की एक घात है।
GF(q) में सर्वसमिका (x + y)p = xp + yp का तात्पर्य है कि मानचित्र (map)
φ की संरचना को k बार φk द्वारा निरूपित कर , हमारे पास है
GF(p) का कोई अन्य GF(q) -स्वरूपण (automorphism) नहीं हैं। दूसरे शब्दों में, GF(pn) के बिल्कुल n GF(p)-स्वरूपण (automorphism) है, जो हैं
तथ्य यह है कि फ्रोबेनियस मानचित्र विशेषण (surjective) है, इसका तात्पर्य है कि प्रत्येक परिमित क्षेत्र पूर्ण क्षेत्र (perfect field) है।
बहुपद गुणनखंड
यदि F एक परिमित क्षेत्र है, तो F में गुणांक के साथ एक गैर-स्थिर मोनिक बहुपद F पर अलघुकरणीय (irreducible) है, यदि यह F में गुणांक वाले दो गैर-स्थिर मोनिक बहुपदों का गुणनफल नहीं है।
चूंकि एक क्षेत्र पर प्रत्येक बहुपद वलय एक अद्वितीय गुणनखंडन अनुक्षेत्र (unique factorization domain) है, एक परिमित क्षेत्र पर प्रत्येक मोनिक बहुपद को एक अद्वितीय तरीके से (कारकों के क्रम तक) अखंडनीय (irreducible) मोनिक बहुपद के गुणन में विभाजित किया जा सकता है। परिमित क्षेत्र पर बहुपद इरेड्यूसबिलिटी और फैक्टरिंग बहुपदों के परीक्षण के लिए कुशल एल्गोरिदम हैं। वे पूर्णांकों या परिमेय संख्याओं पर बहुपदों का गुणनखण्ड करने के लिए एक महत्वपूर्ण कदम हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर, या कम से कम, परिमित प्रधान क्षेत्रों पर बहुपदों के गुणनखंडन के लिए कार्य होते हैं।
परिमित क्षेत्र में बहुपद अलघुकरणीय (irreducible) और विभाजित बहुपदों के परीक्षण के लिए कुशल प्रणाली (algorithm) हैं। वे पूर्णांकों या परिमेय संख्या ओं पर बहुपदों के गुणनखंड के लिए एक महत्वपूर्ण चरण हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर, या कम से कम, परिमित प्रमुख क्षेत्रों में ( finite prime fields) बहुपदों के गुणनखंडन के लिए कार्य होते हैं।
दी गई डिग्री के अमिट बहुपद
बहुपद
इसका तात्पर्य यह है कि, यदि q = pn फिर Xq − X सभी मोनिक इरेड्यूसिबल बहुपदों का गुणनफल है GF(p), जिसकी डिग्री विभाजित होती है n. वास्तव में, यदि P एक अपरिवर्तनीय कारक है GF(p) का Xq − X, इसकी डिग्री विभाजित होती है n, क्योंकि इसका विभाजन क्षेत्र में समाहित है GF(pn). इसके विपरीत, यदि P एक इरेड्यूसिबल मोनिक बहुपद ओवर है GF(p) डिग्री का d भाग देनेवाला n, यह डिग्री के क्षेत्र विस्तार को परिभाषित करता है 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) में होते हैं यदि इसके चर की संख्या इसकी कोटि (डिग्री) से अधिक है। यह एमिल आर्टिन और लियोनार्ड यूजीन डिक्सन का अनुमान था जिसे क्लाउड शेवेली द्वारा सिद्ध किया गया था (देखें शेवेली-चेतावनी प्रमेय)।
वेडरबर्न की छोटी प्रमेय
एक विभाजन वलय ( डिवीजन रिंग ) क्षेत्र (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.