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

For polynomials such that the greatest common divisor of the coefficients is 1, see Primitive polynomial (ring theory).

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

गुण

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

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

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

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

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

• GF(p^m) का स्पष्ट रूप है F(x) = (x − α)(x − α^p)(x − α^p2)⋅⋅⋅(x − α^pm−1).

उपयोग

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

परिमित क्षेत्र के तत्वों का प्रतिनिधित्व करने के लिए आदिम बहुपदों का उपयोग किया जा सकता है। अगर α जीएफ में (पी^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.$

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

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

सीआरसी कोड

चक्रीय अतिरेक जांच (सीआरसी) एक त्रुटि-पहचान कोड है जो संदेश बिटस्ट्रिंग को जीएफ (2) पर बहुपद के गुणांक के रूप में व्याख्या करके संचालित करता है और इसे जीएफ (2) पर भी एक निश्चित जनरेटर बहुपद द्वारा विभाजित करता है; सीआरसी का गणित देखें। आदिम बहुपद, या उनके गुणक, कभी-कभी जनरेटर बहुपद के लिए एक अच्छा विकल्प होते हैं क्योंकि वे दो बिट त्रुटियों का विश्वसनीय रूप से पता लगा सकते हैं जो संदेश बिटस्ट्रिंग में दूर तक होती हैं, की दूरी तक 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.