आदिम बहुपद (क्षेत्र सिद्धांत)

For बहुपद जैसे कि गुणांक का सबसे बड़ा सामान्य विभाजक 1 है, see आदिम बहुपद (वृत्त सिद्धांत).

परिमित क्षेत्र सिद्धांत में, क्षेत्र सिद्धांत (गणित) में, गणित की एक शाखा, आदिम बहुपद परिमित क्षेत्र GF(p^m) के आदिम तत्व (परिमित क्षेत्र) का न्यूनतम बहुपद (क्षेत्र सिद्धांत) है। इसका मतलब है कि GF(p) = Z/pZ में गुणांक के साथ घात m का बहुपद F(X) एक आदिम बहुपद है यदि यह मोनिक बहुपद है और GF(p^m) में इसका मूल α है ऐसा है कि $\{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-1}\}$ संपूर्ण क्षेत्र GF(p^m) है। इसका अर्थ यह है कि α GF(p^m) में आदिम (p^m − 1)- एकता का आदिम मूल है।

गुण

• क्योंकि सभी न्यूनतम बहुपद अलघुकरणीय बहुपद होते हैं, सभी आदिम बहुपद भी अलघुकरणीय होते हैं।

• एक आदिम बहुपद में गैर-शून्य स्थिरांक होना चाहिए, अन्यथा यह x से विभाज्य होगा। GF(2) से अधिक, x + 1 आदिम बहुपद है और अन्य सभी आदिम बहुपदों में विषम संख्याएँ हैं, क्योंकि किसी भी बहुपद मॉड 2 में समान संख्या में शब्द x + 1 से विभाज्य हैं (इसका मूल के रूप में 1 है)।

• GF(p) पर घात m का एक अलघुकरणीय बहुपद F(x), जहां p अभाज्य है, एक आदिम बहुपद है यदि सबसे छोटा धनात्मक पूर्णांक n ऐसा है कि F(x) xⁿ − 1 को विभाजित करता n = p^m − 1 है।

• GF(p) पर बिल्कुल φ(p^m − 1)/m आदिम बहुपद m घात के होते है, जहां φ यूलर का कुल फलन है।

• घात m के एक आदिम बहुपद के GF(p^m) में m भिन्न मूल हैं, जिसमें सभी का क्रम p^m − 1 (समूह सिद्धांत) है। इसका अर्थ है कि, यदि α एक ऐसा मूल है, तो α^pm−1 = 1 और αⁱ ≠ 1 0 < i < p^m − 1 के लिए है।

• GF(p^m) में आदिम तत्व α की डिग्री m का आदिम बहुपद F(x) का स्पष्ट रूप F(x) = (x − α)(x − α^p)(x − α^p2)⋅⋅⋅(x − α^pm−1) है।

प्रयोग

क्षेत्र तत्व प्रतिनिधित्व

परिमित क्षेत्र के तत्वों का प्रतिनिधित्व करने के लिए आदिम बहुपदों का उपयोग किया जा सकता है। अगर GF(p^m) में α आदिम बहुपद F(x) का मूल है, तो GF(p^m) के शून्येतर तत्वों को α की क्रमिक शक्तियों के रूप में दर्शाया गया है:

$\mathrm {GF} (p^{m})=\{0,1=\alpha ^{0},\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.$

यह परिमित क्षेत्र के गैर-शून्य तत्वों के कंप्यूटर में आर्थिक प्रतिनिधित्व की अनुमति देता है, इसके अनुरूप एक्सपोनेंट द्वारा $\alpha .$ तत्व का प्रतिनिधित्व करके, यह प्रतिनिधित्व गुणन को आसान बनाता है, क्योंकि यह घातांक मॉड्यूलर अंकगणित के योग $p^{m}-1$ से मेल खाता है।

छद्म-यादृच्छिक बिट पीढ़ी

GF(2) पर आदिम बहुपद, दो तत्वों के साथ क्षेत्र, छद्म यादृच्छिक संख्या जनरेटर के लिए उपयोग किया जा सकता है। वास्तव में, प्रत्येक रैखिक-फीडबैक शिफ्ट अधिकतम चक्र लंबाई (जो 2ⁿ − 1 है, जहां n रैखिक फीडबैक शिफ्ट रजिस्टर की लंबाई है) आदिम बहुपद से बनाया जा सकता है।

सामान्य तौर पर, GF(2) पर घात m के आदिम बहुपद के लिए, यह प्रक्रिया 2^m − 1 उसी क्रम को दोहराने से पहले छद्म-यादृच्छिक बिट्स उत्पन्न करेगी।

CRC कोड

चक्रीय अतिरेक जांच (CRC ) त्रुटि-पहचान कोड है जो संदेश बिटस्ट्रिंग को GF(2) पर बहुपद के गुणांक के रूप में व्याख्या करके संचालित करता है और इसे GF(2) पर भी एक निश्चित जनरेटर बहुपद द्वारा विभाजित करता है; CRC का गणित देखें। आदिम बहुपद, या उनके गुणक, कभी-कभी जनरेटर बहुपद के लिए एक अच्छा विकल्प होते हैं क्योंकि वे दो बिट त्रुटियों का विश्वसनीय रूप से पता लगा सकते हैं जो संदेश बिटस्ट्रिंग में दूर तक होती हैं, घात n आदिम बहुपद के लिए 2ⁿ − 1 की दूरी तक होती हैं।

आदिम त्रिपद

आदिम बहुपदों का एक उपयोगी वर्ग आदिम त्रिपद है, जिनके पास केवल तीन गैर-शून्य शब्द हैं: x^r + x^k + 1. उनकी सादगी विशेष रूप से छोटे और तेज रैखिक-फीडबैक शिफ्ट रजिस्टरों के लिए बनाती है। कई परिणाम ट्रिनोमियल्स की प्रधानता का पता लगाने और परीक्षण करने के लिए तकनीक प्रदान करते हैं।

GF(2) पर बहुपदों के लिए, जहाँ 2^r − 1 एक Mersenne अभाज्य है, घात r का एक बहुपद आदिम है अगर और केवल अगर यह अलघुकरणीय है। (एक अलघुकरणीय बहुपद को देखते हुए, यह केवल आदिम नहीं है यदि x की अवधि एक गैर-तुच्छ कारक है 2^r − 1. प्राइम्स का कोई गैर-तुच्छ कारक नहीं है।) हालांकि मेर्सन ट्विस्टर छद्म-यादृच्छिक संख्या जनरेटर ट्रिनोमियल का उपयोग नहीं करता है, यह इसका लाभ उठाता है।

रिचर्ड ब्रेंट (वैज्ञानिक) इस रूप के आदिम ट्रिनोमियल्स को सारणीबद्ध कर रहे हैं, जैसे x^74207281 + x^30684570 + 1. इसका उपयोग विशाल अवधि के छद्म-यादृच्छिक संख्या जनरेटर बनाने के लिए किया जा सकता है 2^74207281 − 1 ≈ 3×10^22338617.

बाहरी संबंध

• Weisstein, Eric W. "Primitive Polynomial". MathWorld.