परिमित क्षेत्र

From Vigyanwiki

गणित में, एक परिमित क्षेत्र (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) के एक परिमित क्षेत्र में, बहुपद XqX में परिमित क्षेत्र के सभी 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 के लिए, nx द्वारा 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 + y)p के विस्तार का प्रत्येक द्विपद गुणांक पहले और अंतिम को छोड़कर, p का एक गुणज (multiple) है।

फ़र्मेट की छोटी प्रमेय के अनुसार, यदि p एक अभाज्य संख्या है और x क्षेत्र (फ़ील्ड) GF(p) में है तो xp = x. इसका तात्पर्य समानता से है

GF(p) के बहुपदों के लिए। अधिक सामान्यतः, GF(pn) में प्रत्येक तत्व बहुपद समीकरण xpnx = 0 को संतुष्ट करता है।

परिमित क्षेत्र (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) हो

प्रमुख क्षेत्र (prime field) GF(p) के ऊपर। इसका मतलब यह है कि F निम्नतम क्रम (lowest order) का एक परिमित क्षेत्र (finite field) है, जिसमें P के q अलग-अलग मूल हैं (P का औपचारिक व्युत्पन्न P = −1 है , जिसका अर्थ है कि gcd(P, P) = 1, जिसका सामान्य अर्थ यह है कि विभाजन क्षेत्र (splitting field) मूल (original) का एक वियोज्य विस्तार है)। उपरोक्त पहचान दर्शाता है कि P के दो मूलों (roots) का योग और गुणनफल P के मूल (root) हैं, साथ ही P के मूल का गुणनात्मक व्युत्क्रम (multiplicative inverse)। दूसरे शब्दों में, P के मूल q क्रम (order) का एक क्षेत्र (field) बनाते हैं, जो विभाजन क्षेत्र (splitting field) की न्यूनतमता (minimality) से F के बराबर है।

बंटवारे वाले क्षेत्रों के समरूपता तक की विशिष्टता का तात्पर्य इस प्रकार है कि क्रम के सभी क्षेत्र q समरूपी हैं। इसके अलावा, यदि कोई क्षेत्र F आदेश का एक क्षेत्र है q = pk एक उपक्षेत्र के रूप में, इसके तत्व हैं q की जड़ें XqX, तथा F आदेश का एक और उपक्षेत्र नहीं हो सकता q.

संक्षेप में, हमारे पास निम्नलिखित वर्गीकरण प्रमेय है जिसे पहली बार 1893 में ई. एच. मूर द्वारा सिद्ध किया गया था:[1]

एक परिमित क्षेत्र का क्रम एक प्रमुख शक्ति है। हर प्रधान शक्ति के लिए q आदेश के क्षेत्र हैं q, और वे सभी समरूपी हैं। इन क्षेत्रों में हर तत्व संतुष्ट

और बहुपद XqX कारक के रूप में

यह इस प्रकार है कि GF(pn) इसमें एक सबफील्ड आइसोमॉर्फिक शामिल है GF(pm) अगर और केवल अगर m का भाजक है n; उस स्थिति में, यह उपक्षेत्र अद्वितीय है। वास्तव में, बहुपद XpmX विभाजित XpnX अगर और केवल अगर m का भाजक है n.

स्पष्ट निर्माण

गैर-अभाज्य क्षेत्र

p अभाज्य (prime) और n > 1 के साथ एक प्रमुख घात (prime power) q = pn को देखते हुए, फ़ील्ड GF(q) को स्पष्ट रूप से निम्नलिखित तरीके से स्पष्ट रूप से बनाया जा सकता है। सबसे पहले डिग्री n के GF(p)[X] में एक अलघुकरणीय बहुपद P चुनता है (इस तरह का एक अलघुकरणीय बहुपद हमेशा मौजूद रहता है)। फिर भागफल बजता है सबसे पहले एक इरेड्यूसबल बहुपद का चयन करता है P में GF(p)[X] डिग्री का n (ऐसा एक अघुलनशील बहुपद हमेशा मौजूद होता है)। फिर भागफल वलय

बहुपद वलय का GF(p)[X] द्वारा उत्पन्न आदर्श द्वारा P व्यवस्था का क्षेत्र है q.

अधिक स्पष्ट रूप से, के तत्व GF(q) क्या बहुपद समाप्त हो गए हैं GF(p) जिसकी डिग्री सख्ती से . से कम है n. जोड़ और घटाव उन बहुपदों के ऊपर हैं GF(p). दो तत्वों का गुणनफल बहुपदों के यूक्लिडियन विभाजन का शेषफल है P उत्पाद में GF(p)[X]. एक गैर-शून्य तत्व के गुणक व्युत्क्रम की गणना विस्तारित यूक्लिडियन एल्गोरिथम के साथ की जा सकती है; विस्तारित यूक्लिडियन एल्गोरिथम देखें#सरल बीजीय क्षेत्र एक्सटेंशन|विस्तारित यूक्लिडियन एल्गोरिथम § सरल बीजीय क्षेत्र एक्सटेंशन।

के निर्माण को छोड़कर GF(4), के लिए कई संभावित विकल्प हैं P, जो आइसोमॉर्फिक परिणाम उत्पन्न करते हैं। यूक्लिडियन डिवीजन को सरल बनाने के लिए, आमतौर पर के लिए चुना जाता है P प्रपत्र का एक बहुपद

जो आवश्यक यूक्लिडियन डिवीजनों को बहुत कुशल बनाते हैं। हालांकि, कुछ क्षेत्रों के लिए, आमतौर पर विशेषता में 2, रूप के अपरिवर्तनीय बहुपद Xn + aX + b मौजूद नहीं हो सकता है। विशेषता में 2, यदि बहुपद Xn + X + 1 कम करने योग्य है, इसे चुनने की अनुशंसा की जाती है Xn + Xk + 1 न्यूनतम संभव के साथ k जो बहुपद को अघुलनशील बनाता है। यदि ये सभी त्रिनाम रिड्यूसेबल हैं, तो कोई पेंटानोमियल्स चुनता है Xn + Xa + Xb + Xc + 1, डिग्री से अधिक के बहुपद के रूप में 1, समान संख्या में पदों के साथ, विशेषता में कभी भी अपरिवर्तनीय नहीं होते हैं 2, रखना 1 एक जड़ के रूप में।[3] ऐसे बहुपद के लिए एक संभावित विकल्प कॉनवे बहुपद (परिमित क्षेत्र) द्वारा दिया जाता है। वे एक क्षेत्र के प्रतिनिधित्व और उसके उपक्षेत्रों के प्रतिनिधित्व के बीच एक निश्चित संगतता सुनिश्चित करते हैं।

अगले खंडों में, हम दिखाएंगे कि ऊपर उल्लिखित सामान्य निर्माण विधि छोटे परिमित क्षेत्रों के लिए कैसे काम करती है।

चार तत्वों वाला क्षेत्र

सबसे छोटा गैर-अभाज्य क्षेत्र चार तत्वों वाला क्षेत्र है, जिसे आमतौर पर दर्शाया जाता है GF(4) या इसमें चार तत्व होते हैं ऐसा है कि तथा हरएक के लिए अन्य ऑपरेशन के परिणाम वितरण कानून से आसानी से निकाले जा रहे हैं। संपूर्ण ऑपरेशन टेबल के लिए नीचे देखें।

इसे पिछले खंड के परिणामों से निम्नानुसार घटाया जा सकता है।

ऊपर GF(2), घात का केवल एक अपरिमेय बहुपद है 2:

इसलिए, के लिए GF(4) पूर्ववर्ती खंड के निर्माण में यह बहुपद शामिल होना चाहिए, और
होने देना α इस बहुपद के मूल को निरूपित करें GF(4). यह बताता है कि

α2 = 1 + α,

और कि α तथा 1 + α के तत्व हैं GF(4) जो में नहीं हैं GF(2). संचालन की तालिकाएँ GF(4) इसका परिणाम है, और इस प्रकार हैं:

Addition x+y Multiplication xy Division x/y
y
x
0 1 α 1 + α
0 0 1 α 1 + α
1 1 0 1 + α α
α α 1 + α 0 1
1 + α 1 + α α 1 0
y
x
0 1 α 1 + α
0 0 0 0 0
1 0 1 α 1 + α
α 0 α 1 + α 1
1 + α 0 1 + α 1 α
y
x
1 α 1 + α
0 0 0 0
1 1 1 + α α
α α 1 1 + α
1 + α 1 + α α 1

घटाव के लिए एक तालिका नहीं दी गई है, क्योंकि घटाव जोड़ के समान है, जैसा कि विशेषता 2 के प्रत्येक क्षेत्र के मामले में है। तीसरी तालिका में, के विभाजन के लिए x द्वारा y, के मान x बाएं कॉलम में पढ़ा जाना चाहिए, और के मान y शीर्ष पंक्ति में। (इसलिये 0 ⋅ z = 0 हरएक के लिए z प्रत्येक वलय (गणित) में 0 से भाग को अपरिभाषित रहना पड़ता है।) तालिकाओं से, यह देखा जा सकता है कि की योगात्मक संरचना GF(4) क्लेन_फोर-ग्रुप के लिए आइसोमॉर्फिक है | क्लेन फोर-ग्रुप, जबकि गैर-शून्य गुणक संरचना जेड के लिए आइसोमॉर्फिक है3.

नक्शा

गैर-तुच्छ क्षेत्र ऑटोमोर्फिज्म है, जिसे #फ्रोबेनियस ऑटोमोर्फिज्म और गैलोइस सिद्धांत कहा जाता है, जो भेजता है α दूसरी जड़ में 1 + α उपर्युक्त इरेड्यूसिबल बहुपद का


===जीएफ(पी2) विषम अभाज्य p=== . के लिए के मामले में परिमित क्षेत्रों के #गैर-अभाज्य क्षेत्रों को लागू करने के लिए GF(p2), व्यक्ति को घात 2 का एक अपूरणीय बहुपद ज्ञात करना होता है p = 2, यह पिछले भाग में किया गया है। यदि p एक विषम अभाज्य है, इस रूप के हमेशा अपरिवर्तनीय बहुपद होते हैं X2r, साथ r में GF(p).

अधिक सटीक, बहुपद X2r इरेड्यूसबल ओवर है GF(p) अगर और केवल अगर r एक द्विघात गैर-अवशेष मॉड्यूल है p (यह लगभग एक द्विघात गैर-अवशेष की परिभाषा है)। वहाँ हैं p − 1/2 द्विघात गैर-अवशेष मॉड्यूल p. उदाहरण के लिए, 2 के लिए एक द्विघात गैर-अवशेष है p = 3, 5, 11, 13, ..., तथा 3 के लिए एक द्विघात गैर-अवशेष है p = 5, 7, 17, .... यदि p ≡ 3 mod 4, वह है p = 3, 7, 11, 19, ..., कोई चुन सकता है −1 ≡ p − 1 एक द्विघात गैर-अवशेष के रूप में, जो हमें एक बहुत ही सरल अपरिवर्तनीय बहुपद प्राप्त करने की अनुमति देता है X2 + 1.

एक द्विघात गैर-अवशेष का चयन करना r, होने देना α का प्रतीकात्मक वर्गमूल बनें r, यह एक प्रतीक है जिसमें संपत्ति है α2 = r, उसी तरह जैसे सम्मिश्र संख्या i का प्रतीकात्मक वर्गमूल है −1. फिर, के तत्व GF(p2) सभी रैखिक व्यंजक हैं

साथ a तथा b में GF(p). संचालन GF(p2) निम्नानुसार परिभाषित किया गया है (के तत्वों के बीच संचालन GF(p) लैटिन अक्षरों द्वारा दर्शाए गए ऑपरेशन हैं GF(p)):


जीएफ(8) और जीएफ(27)

बहुपद

इरेड्यूसबल ओवर है GF(2) तथा GF(3), अर्थात्, यह इरेड्यूसेबल मोडुलो है 2 तथा 3 (यह दिखाने के लिए, यह दिखाने के लिए पर्याप्त है कि इसकी कोई जड़ नहीं है GF(2) न ही में GF(3)) यह इस प्रकार है कि . के तत्व GF(8) तथा GF(27) अभिव्यक्ति (गणित) द्वारा दर्शाया जा सकता है
कहाँ पे a, b, c के तत्व हैं GF(2) या GF(3) (क्रमशः), और एक प्रतीक है कि

जोड़, योगात्मक प्रतिलोम और गुणा पर GF(8) तथा GF(27) इस प्रकार परिभाषित किया जा सकता है; निम्नलिखित सूत्रों में, के तत्वों के बीच संचालन GF(2) या GF(3), लैटिन अक्षरों द्वारा निरूपित, संचालन हैं GF(2) या GF(3), क्रमश:


जीएफ(16)

बहुपद

इरेड्यूसबल ओवर है GF(2), अर्थात्, यह इरेड्यूसेबल मोडुलो है 2. यह इस प्रकार है कि . के तत्व GF(16) अभिव्यक्ति (गणित) द्वारा दर्शाया जा सकता है
कहाँ पे a, b, c, d दोनों मे से एक 0 या 1 (के तत्व GF(2)), तथा α एक प्रतीक है कि

(वह है, α को दिए गए इरेड्यूसबल बहुपद के मूल के रूप में परिभाषित किया गया है)। की विशेषता के रूप में GF(2) है 2, प्रत्येक तत्व इसका योज्य प्रतिलोम है GF(16). जोड़ और गुणा GF(16) निम्नानुसार परिभाषित किया जा सकता है; निम्नलिखित सूत्रों में, के तत्वों के बीच संचालन GF(2), लैटिन अक्षरों द्वारा दर्शाए गए ऑपरेशन हैं GF(2).

फील्ड GF(16) आठ आदिम तत्व (परिमित क्षेत्र) हैं (ऐसे तत्व जिनमें . के सभी गैर-शून्य तत्व हैं GF(16) पूर्णांक शक्तियों के रूप में)। ये तत्व . के चार मूल हैं और उनके गुणनात्मक प्रतिलोम। विशेष रूप से, α एक आदिम तत्व है, और आदिम तत्व हैं साथ m 15 से कम और सह अभाज्य (अर्थात 1, 2, 4, 7, 8, 11, 13, 14)।

गुणक संरचना

गैर-शून्य तत्वों का सेट GF(q) गुणन के तहत एक एबेलियन समूह है, क्रम का q – 1. लैग्रेंज के प्रमेय (समूह सिद्धांत) द्वारा | लैग्रेंज की प्रमेय, एक भाजक मौजूद है k का q – 1 ऐसा है कि xk = 1 प्रत्येक गैर-शून्य . के लिए x में GF(q). समीकरण के रूप में xk = 1 ज्यादा से ज्यादा है k किसी भी क्षेत्र में समाधान, q – 1 के लिए उच्चतम संभव मूल्य है k. एबेलियन समूह # वर्गीकरण का तात्पर्य है कि यह गुणन समूह चक्रीय समूह है, अर्थात सभी गैर-शून्य तत्व एक ही तत्व की शक्तियाँ हैं। सारांश:

The multiplicative group of the non-zero elements in GF(q) is cyclic, and there exists an element a, such that the q – 1 non-zero elements of GF(q) are a, a2, ..., aq−2, aq−1 = 1.

ऐसा तत्व a आदिम तत्व (परिमित क्षेत्र) कहलाता है। जब तक q = 2, 3, आदिम तत्व अद्वितीय नहीं है। आदिम तत्वों की संख्या है φ(q − 1) कहाँ पे φ यूलर का टोटिएंट फंक्शन है।

उपरोक्त परिणाम का तात्पर्य है कि xq = x हरएक के लिए x में GF(q). विशेष मामला जहां q प्राइम है फर्मेट का छोटा प्रमेय।

असतत लघुगणक

यदि a में एक आदिम तत्व है GF(q), तो किसी भी गैर-शून्य तत्व के लिए x में F, एक अद्वितीय पूर्णांक है n साथ 0 ≤ nq − 2 ऐसा है कि

x = an.

यह पूर्णांक n असतत लघुगणक कहा जाता है x आधार के लिए a.

जबकि an बहुत तेज़ी से गणना की जा सकती है, उदाहरण के लिए वर्ग द्वारा घातांक का उपयोग करते हुए, व्युत्क्रम संचालन, असतत लघुगणक की गणना के लिए कोई ज्ञात कुशल एल्गोरिथ्म नहीं है। इसका उपयोग विभिन्न क्रिप्टोग्राफिक प्रोटोकॉल में किया गया है, विवरण के लिए असतत लघुगणक देखें।

जब के शून्येतर तत्व GF(q) उनके असतत लघुगणक द्वारा प्रतिनिधित्व किया जाता है, गुणा और भाग आसान होते हैं, क्योंकि वे जोड़ और घटाव को कम करते हैं q – 1. हालांकि, असतत लघुगणक की गणना करने के लिए अतिरिक्त राशि am + an. पहचान

am + an = an(amn + 1)

असतत लघुगणक की तालिका बनाकर इस समस्या को हल करने की अनुमति देता है an + 1, Zech के लघुगणक कहलाते हैं, for n = 0, ..., q − 2 (शून्य के असतत लघुगणक को परिभाषित करना सुविधाजनक है −∞)

Zech के लघुगणक बड़ी गणनाओं के लिए उपयोगी होते हैं, जैसे कि मध्यम आकार के क्षेत्रों में रैखिक बीजगणित, अर्थात, ऐसे क्षेत्र जो प्राकृतिक एल्गोरिदम को अक्षम बनाने के लिए पर्याप्त रूप से बड़े हैं, लेकिन बहुत बड़े नहीं हैं, क्योंकि किसी को उसी आकार की तालिका की पूर्व-गणना करनी होती है। क्षेत्र के आदेश के रूप में।

एकता की जड़ ें

परिमित क्षेत्र का प्रत्येक अशून्य तत्व एकता का मूल है, जैसे xq−1 = 1 के हर शून्येतर तत्व के लिए GF(q).

यदि n एक धनात्मक पूर्णांक है, an n-एकता का आदिम मूल समीकरण का हल है xn = 1 यह समीकरण का हल नहीं है xm = 1 किसी धनात्मक पूर्णांक के लिए m < n. यदि a एक है nएक क्षेत्र में एकता का वां आदिम मूल F, फिर F सभी शामिल हैं n एकता की जड़ें, जो हैं 1, a, a2, ..., an−1.

फील्ड GF(q) इसमें शामिल है a nएकता का वां आदिम मूल यदि और केवल यदि n का भाजक है q − 1; यदि n का भाजक है q − 1, फिर आदिम की संख्या nमें एकता की वें जड़ें GF(q) है φ(n) (यूलर का टोटिएंट फंक्शन)। की संख्या nमें एकता की वें जड़ें GF(q) है gcd(n, q − 1).

विशेषता के क्षेत्र में p, हर एक (np)एकता की जड़ भी है a nएकता की जड़। यह इस प्रकार है कि आदिम (np)विशेषता के क्षेत्र में एकता की जड़ें कभी मौजूद नहीं होती हैं p.

दूसरी ओर, यदि n सह अभाज्य है p, की जड़ें nवें साइक्लोटोमिक बहुपद विशेषता के हर क्षेत्र में अलग हैं p, क्योंकि यह बहुपद . का भाजक है Xn − 1, जिसका विभेदक शून्येतर मोडुलो है p. यह इस प्रकार है कि nth साइक्लोटॉमिक बहुपद कारक खत्म हो गए हैं GF(p) अलग-अलग अपरिवर्तनीय बहुपदों में, जिनकी सभी समान डिग्री हैं, कहते हैं d, और कि GF(pd) विशेषता का सबसे छोटा क्षेत्र है p जिसमें शामिल है nएकता की आदिम जड़ें।

उदाहरण: GF(64)

फील्ड GF(64) इसमें कई दिलचस्प गुण हैं जो छोटे क्षेत्र साझा नहीं करते हैं: इसमें दो उपक्षेत्र हैं जैसे कि न तो दूसरे में निहित है; डिग्री के सभी जनरेटर (न्यूनतम बहुपद (क्षेत्र सिद्धांत) वाले तत्व नहीं) 6 ऊपर GF(2)) आदिम तत्व हैं; और आदिम तत्व गैलोइस समूह के तहत सभी संयुग्मित नहीं हैं।

इस क्षेत्र का क्रम 26, और के भाजक 6 प्राणी 1, 2, 3, 6, के उपक्षेत्र GF(64) हैं GF(2), GF(22) = GF(4), GF(23) = GF(8), तथा GF(64) अपने आप। जैसा 2 तथा 3 सहप्राइम हैं, का प्रतिच्छेदन GF(4) तथा GF(8) में GF(64) प्रमुख क्षेत्र है GF(2).

का संघ GF(4) तथा GF(8) इस प्रकार है 10 तत्व शेष 54 के तत्व GF(64) बनाना GF(64) इस अर्थ में कि किसी अन्य उपक्षेत्र में उनमें से कोई भी शामिल नहीं है। यह इस प्रकार है कि वे डिग्री के अपरिवर्तनीय बहुपद की जड़ें हैं 6 ऊपर GF(2). इसका तात्पर्य है कि, अधिक GF(2), बिल्कुल हैं 9 = 54/6 डिग्री के अपरिवर्तनीय मोनिक बहुपद 6. यह फैक्टरिंग द्वारा सत्यापित किया जा सकता है X64X ऊपर GF(2).

के तत्व GF(64) आदिम हैं nकुछ के लिए एकता की जड़ें n भाग देनेवाला 63. चूंकि एकता की तीसरी और सातवीं जड़ें हैं GF(4) तथा GF(8), क्रमशः, 54 जनरेटर आदिम हैं nकुछ के लिए एकता की जड़ें n में {9, 21, 63}. यूलर के टोटिएंट फंक्शन से पता चलता है कि 6 प्राचीन 9एकता की जड़ें, 12 प्राचीन 21एकता की जड़ें, और 36 प्राचीन 63एकता की rd जड़ें। इन नंबरों का योग करने पर, कोई फिर से पाता है 54 तत्व

साइक्लोटोमिक बहुपदों को गुणा करके GF(2), कोई पाता है कि:

  • छह आदिम 9एकता की जड़ें की जड़ें हैं
    और सभी गैलोइस समूह की कार्रवाई के तहत संयुग्मित हैं।
  • बारह आदिम 21एकता की जड़ें की जड़ें हैं
    गैलोइस समूह की कार्रवाई के तहत वे दो कक्षाएँ बनाते हैं। चूंकि दो कारक एक दूसरे के पारस्परिक बहुपद हैं, एक जड़ और इसका (गुणक) प्रतिलोम एक ही कक्षा से संबंधित नहीं है।
  • 36 }} के आदिम तत्व GF(64) की जड़ें हैं
    गैलोइस समूह की कार्रवाई के तहत वे छह तत्वों की छह कक्षाओं में विभाजित हो गए।

इससे पता चलता है कि निर्माण के लिए सबसे अच्छा विकल्प GF(64) इसे परिभाषित करना है GF(2)[X] / (X6 + X + 1). वास्तव में, यह जनरेटर एक आदिम तत्व है, और यह बहुपद इरेड्यूसबल बहुपद है जो सबसे आसान यूक्लिडियन विभाजन उत्पन्न करता है।

Frobenius automorphism और Galois सिद्धांत

इस खंड में, p एक अभाज्य संख्या है, और q = pn की शक्ति है p.

में GF(q), पहचान (x + y)p = xp + yp तात्पर्य है कि नक्शा

एक है GF(p)-रेखीय मानचित्र और का एक क्षेत्र स्व-रूपता GF(q), जो उपक्षेत्र के प्रत्येक तत्व को ठीक करता है GF(p). फर्डिनेंड जॉर्ज फ्रोबेनियस के बाद इसे फ्रोबेनियस ऑटोमोर्फिज्म कहा जाता है।

द्वारा निरूपित करना φk की कार्य संरचना φ खुद के साथ k बार, हमारे पास है

यह पिछले भाग में दिखाया गया है कि φn पहचान है। के लिये 0 < k < n, ऑटोमोर्फिज्म φk पहचान नहीं है, जैसा कि, अन्यथा, बहुपद

से अधिक होगा pk जड़ें

कोई अन्य नहीं हैं GF(p)-ऑटोमोर्फिज्म ऑफ GF(q). दूसरे शब्दों में, GF(pn) बिल्कुल है n GF(p)-ऑटोमोर्फिज्म, जो हैं

गैलोइस सिद्धांत के संदर्भ में, इसका अर्थ है कि GF(pn) गैलोइस का विस्तार है GF(p), जिसका एक चक्रीय समूह गैलोइस समूह है।

तथ्य यह है कि फ्रोबेनियस मानचित्र विशेषण है, इसका तात्पर्य है कि प्रत्येक परिमित क्षेत्र पूर्ण क्षेत्र है।

बहुपद गुणनखंड

यदि F एक परिमित क्षेत्र है, गुणांक के साथ एक गैर-स्थिर मोनिक बहुपद है F इरेड्यूसिबल बहुपद अधिक है F, यदि यह दो गैर-स्थिर मोनिक बहुपदों का गुणनफल नहीं है, जिसमें गुणांक हैं F.

चूंकि एक क्षेत्र पर प्रत्येक बहुपद वलय एक अद्वितीय गुणनखंडन डोमेन है, एक परिमित क्षेत्र पर प्रत्येक मोनिक बहुपद को एक अनूठे तरीके से (कारकों के क्रम तक) इरेड्यूसिबल मोनिक बहुपद के उत्पाद में विभाजित किया जा सकता है।

परिमित क्षेत्र में बहुपद अप्रासंगिकता और फैक्टरिंग बहुपदों के परीक्षण के लिए कुशल एल्गोरिदम हैं। वे पूर्णांकों या परिमेय संख्या ओं पर बहुपदों के गुणनखंड के लिए एक महत्वपूर्ण चरण हैं। कम से कम इस कारण से, प्रत्येक कंप्यूटर बीजगणित प्रणाली में परिमित क्षेत्रों पर बहुपदों को फ़ैक्टर करने के लिए कार्य होता है, या कम से कम, परिमित प्रमुख क्षेत्रों में।

दी गई डिग्री के अमिट बहुपद

बहुपद

आदेश के क्षेत्र में रैखिक कारकों में कारक q. अधिक सटीक रूप से, यह बहुपद क्रम के क्षेत्र में डिग्री एक के सभी मोनिक बहुपदों का उत्पाद है q.

इसका तात्पर्य यह है कि, यदि q = pn फिर XqX सभी मोनिक इरेड्यूसिबल बहुपदों का गुणनफल है GF(p), जिसकी डिग्री विभाजित होती है n. वास्तव में, यदि P एक अपरिवर्तनीय कारक है GF(p) का XqX, इसकी डिग्री विभाजित होती है n, क्योंकि इसका विभाजन क्षेत्र में समाहित है GF(pn). इसके विपरीत, यदि P एक इरेड्यूसिबल मोनिक बहुपद ओवर है GF(p) डिग्री का d भाग देनेवाला n, यह डिग्री के क्षेत्र विस्तार को परिभाषित करता है d, जो में निहित है GF(pn), और . की सभी जड़ें P के संबंधित GF(pn), और की जड़ें हैं XqX; इस प्रकार P विभाजित XqX. जैसा XqX इसका कोई बहुगुणक नहीं है, इस प्रकार यह उन सभी इरेड्यूसीबल मोनिक बहुपदों का गुणनफल है जो इसे विभाजित करते हैं।

इस संपत्ति का उपयोग बहुपदों की प्रत्येक डिग्री के अघुलनशील कारकों के उत्पाद की गणना करने के लिए किया जाता है GF(p); अलग डिग्री गुणनखंड देखें।

एक परिमित क्षेत्र पर दी गई डिग्री के मोनिक इरेड्यूसबल बहुपदों की संख्या

जो नंबर N(q, n) डिग्री के मोनिक इरेड्यूसीबल बहुपद का n ऊपर

GF(q) द्वारा दिया गया है[4]

कहाँ पे μ मोबियस फ़ंक्शन है। यह सूत्र की संपत्ति का लगभग प्रत्यक्ष परिणाम है XqX के ऊपर।

उपरोक्त सूत्र द्वारा, डिग्री के इरेड्यूसिबल (जरूरी नहीं कि मोनिक) बहुपदों की संख्या n ऊपर GF(q) है (q − 1)N(q, n).

सटीक सूत्र असमानता का तात्पर्य है

यह तेज है अगर और केवल अगर n कुछ प्रधान की शक्ति है। हरएक के लिए q और हर n, दाहिना हाथ धनात्मक है, इसलिए डिग्री का कम से कम एक अपरिवर्तनीय बहुपद है n ऊपर GF(q).

अनुप्रयोग

क्रिप्टोग्राफी में, परिमित क्षेत्रों में या अण्डाकार वक्र ों में असतत लघुगणक समस्या की कठिनाई कई व्यापक रूप से उपयोग किए जाने वाले प्रोटोकॉल का आधार है, जैसे कि डिफी-हेलमैन प्रोटोकॉल। उदाहरण के लिए, 2014 में, विकिपीडिया के लिए एक सुरक्षित इंटरनेट कनेक्शन में एक बड़े परिमित क्षेत्र में अण्डाकार वक्र डिफी-हेलमैन प्रोटोकॉल (ECDHE ) शामिल था।[5] कोडिंग सिद्धांत में, कई कोड परिमित क्षेत्रों में वेक्टर रिक्त स्थान के रैखिक उप-स्थान के रूप में बनाए जाते हैं।

कई त्रुटि सुधार कोड द्वारा परिमित फ़ील्ड का उपयोग किया जाता है, जैसे रीड-सोलोमन त्रुटि सुधार | रीड-सोलोमन त्रुटि सुधार कोड या बीसीएच कोड । परिमित क्षेत्र में लगभग हमेशा 2 की विशेषता होती है, क्योंकि कंप्यूटर डेटा बाइनरी में संग्रहीत होता है। उदाहरण के लिए, डेटा के एक बाइट की व्याख्या किस तत्व के रूप में की जा सकती है? . एक अपवाद PDF417 बार कोड है, जो है . कुछ सीपीयू में विशेष निर्देश होते हैं जो विशेषता 2 के परिमित क्षेत्रों के लिए उपयोगी हो सकते हैं, आमतौर पर कैरी-लेस उत्पाद की विविधताएं।

संख्या सिद्धांत में परिमित क्षेत्रों का व्यापक रूप से उपयोग किया जाता है, क्योंकि पूर्णांकों पर कई समस्याओं को मॉड्यूलर अंकगणित एक या कई अभाज्य संख्याओं को कम करके हल किया जा सकता है। उदाहरण के लिए, परिमेय संख्या ओं के क्षेत्र में बहुपद गुणनखंड न और रैखिक बीजगणित के लिए सबसे तेज़ ज्ञात एल्गोरिदम, मॉड्यूलो एक या कई अभाज्य संख्याओं को कम करके आगे बढ़ते हैं, और फिर चीनी शेष प्रमेय , हेंसल लिफ्टिंग या एलएलएल एल्गोरिथम का उपयोग करके समाधान का पुनर्निर्माण करते हैं।

इसी तरह संख्या सिद्धांत में कई सैद्धांतिक समस्याओं को उनके कुछ या सभी अभाज्य संख्याओं में कमी के मॉड्यूल पर विचार करके हल किया जा सकता है। उदाहरण के लिए, हस सिद्धांत देखें। बीजगणितीय ज्यामिति के कई हालिया विकास इन मॉड्यूलर विधियों की शक्ति को बढ़ाने की आवश्यकता से प्रेरित थे। फ़र्मेट के अंतिम प्रमेय का विल्स का प्रमाण एक गहन परिणाम का एक उदाहरण है जिसमें परिमित क्षेत्रों सहित कई गणितीय उपकरण शामिल हैं।

वेइल अनुमान परिमित क्षेत्रों में बीजगणितीय विविधता पर अंकों की संख्या से संबंधित है और सिद्धांत में घातीय योग और वर्ण योग अनुमान सहित कई अनुप्रयोग हैं।

साहचर्य में परिमित क्षेत्रों का व्यापक अनुप्रयोग है, दो प्रसिद्ध उदाहरण पीला ग्राफ की परिभाषा और पाले निर्माण के लिए संबंधित निर्माण हैं। अंकगणितीय संयोजन में परिमित क्षेत्र[6] और परिमित क्षेत्र मॉडल[7][8] व्यापक रूप से उपयोग किया जाता है, जैसे कि अंकगणितीय प्रगति पर ज़ेमेरेडी के प्रमेय में।

एक्सटेंशन

बीजीय बंद

एक परिमित क्षेत्र F बीजगणितीय रूप से बंद नहीं है: बहुपद

में कोई जड़ नहीं है F, जबसे f (α) = 1 सभी के लिए α में F.

बीजीय बंद को ठीक करें का . नक्शा प्रत्येक को भेजना x प्रति xq कहा जाता है qवें शक्ति फ्रोबेनियस ऑटोमोर्फिज्म। का उपक्षेत्र द्वारा तय किया गया nकी पुनरावृति बहुपद के शून्यकों का समुच्चय है xqn − x, जिसके व्युत्पन्न होने के बाद से अलग-अलग जड़ें हैं है −1, जो कभी शून्य नहीं होता। इसलिए उस उपक्षेत्र में है qn तत्वों, तो यह की अनूठी प्रति है में . का हर परिमित विस्तार में क्या यह कुछ के लिए n, इसलिए

निरपेक्ष गैलोइस समूह अनंत समूह है

किसी भी अनंत गैलोइस समूह की तरह, क्रुल टोपोलॉजी से लैस हो सकता है, और फिर अभी दिए गए आइसोमोर्फिज्म टोपोलॉजिकल समूहों के आइसोमोर्फिज्म हैं। की छवि समूह में जनरेटर है 1, इसलिए से मेल खाती है . यह इस प्रकार है कि अनंत क्रम है और का एक घना उपसमूह उत्पन्न करता है , संपूर्ण समूह नहीं, क्योंकि तत्व अनंत क्रम है और घने उपसमूह उत्पन्न करता है एक कहता है का एक टोपोलॉजिकल जनरेटर है .

अर्ध-बीजगणितीय बंद

हालांकि परिमित क्षेत्र (finite field) बीजगणितीय रूप से बंद (close) नहीं होते हैं, वे अर्ध-बीजगणितीय रूप से बंद क्षेत्र होते हैं| अर्ध-बीजगणितीय रूप से बंद (close), जिसका अर्थ है कि परिमित क्षेत्र में प्रत्येक सजातीय बहुपद (homogeneous polynomial) में एक गैर-नगण्य (non-trivial) शून्य होता है जिसके घटक (components) क्षेत्र (field) में होते हैं यदि इसके चर की संख्या इसकी कोटि (डिग्री) से अधिक है। यह एमिल आर्टिन और लियोनार्ड यूजीन डिक्सन का अनुमान था जिसे क्लाउड शेवेली द्वारा सिद्ध किया गया था (देखें शेवेली-चेतावनी प्रमेय)।

वेडरबर्न की छोटी प्रमेय

एक विभाजन वलय ( डिवीजन रिंग ) क्षेत्र (field) का सामान्यीकरण है। विभाजन वलय ( डिवीजन रिंग ) को क्रमविनिमेय (कम्यूटेटिव) नहीं माना जाता है। कोई गैर-क्रमविनिमेय (नॉन कम्यूटेटिव ) परिमित विभाजन वलय ( डिवीजन रिंग ) नहीं हैं: वेडरबर्न की छोटी प्रमेय में कहा गया है कि सभी परिमित विभाजन वलय (डिवीजन रिंग) क्रमविनिमेय (कम्यूटेटिव)हैं, और इसलिए परिमित क्षेत्र (finite field) हैं। यह परिणाम तब भी कायम रहता है जब हम वैकल्पिकता के लिए संबद्धता की सूक्ति को शिथिल (relax) करते हैं, अर्थात, आर्टिन-ज़ोर्न प्रमेय द्वारा सभी परिमित वैकल्पिक विभाजन वलय ( डिवीजन रिंग ) परिमित क्षेत्र हैं।[9]


यह भी देखें

टिप्पणियाँ

  1. 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
  2. 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.
  3. Recommended Elliptic Curves for Government Use (PDF), National Institute of Standards and Technology, July 1999, p. 3
  4. Jacobson 2009, §4.13
  5. This can be verified by looking at the information on the page provided by the browser.
  6. 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
  7. 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
  8. Wolf, J. (March 2015). "अंकगणितीय संयोजन में परिमित क्षेत्र मॉडल - दस वर्ष". Finite Fields and Their Applications. 32: 233–274. doi:10.1016/j.ffa.2014.11.003. ISSN 1071-5797.
  9. Shult, Ernest E. (2011). अंक और रेखाएँ। शास्त्रीय ज्यामिति की विशेषता. Universitext. Berlin: Springer-Verlag. p. 123. ISBN 978-3-642-15626-7. Zbl 1213.51001.


संदर्भ


बाहरी संबंध