आदिम बहुपद (क्षेत्र सिद्धांत): Difference between revisions
No edit summary |
No edit summary |
||
Line 3: | Line 3: | ||
{{For|बहुपद जैसे कि गुणांक का सबसे बड़ा सामान्य विभाजक 1 है|आदिम बहुपद (वृत्त सिद्धांत)}} | {{For|बहुपद जैसे कि गुणांक का सबसे बड़ा सामान्य विभाजक 1 है|आदिम बहुपद (वृत्त सिद्धांत)}} | ||
[[परिमित क्षेत्र]] [[न्यूनतम बहुपद (क्षेत्र सिद्धांत)|सिद्धांत]] में, [[क्षेत्र सिद्धांत (गणित)]] में, गणित की एक शाखा, आदिम बहुपद [[परिमित क्षेत्र]] {{math|GF(''p''<sup>''m''</sup>)}} के [[आदिम तत्व (परिमित क्षेत्र)]] का [[न्यूनतम बहुपद (क्षेत्र सिद्धांत)]] है। इसका मतलब है कि {{math|1=GF(''p'') = '''Z'''/''p'''''Z'''}} में गुणांक के साथ | [[परिमित क्षेत्र]] [[न्यूनतम बहुपद (क्षेत्र सिद्धांत)|सिद्धांत]] में, [[क्षेत्र सिद्धांत (गणित)]] में, गणित की एक शाखा, आदिम बहुपद [[परिमित क्षेत्र]] {{math|GF(''p''<sup>''m''</sup>)}} के [[आदिम तत्व (परिमित क्षेत्र)]] का [[न्यूनतम बहुपद (क्षेत्र सिद्धांत)]] है। इसका मतलब है कि {{math|1=GF(''p'') = '''Z'''/''p'''''Z'''}} में गुणांक के साथ घात {{mvar|m}} का बहुपद {{math|''F''(''X'')}} एक आदिम बहुपद है यदि यह [[मोनिक बहुपद]] है और {{math|GF(''p''<sup>''m''</sup>)}} में इसका मूल {{math|''α''}} है ऐसा है कि <math>\{0,1,\alpha, \alpha^2,\alpha^3, \ldots \alpha^{p^m-1}\}</math> संपूर्ण क्षेत्र {{math|GF(''p''<sup>''m''</sup>)}} है। इसका अर्थ यह है कि {{math|''α''}} {{math|GF(''p''<sup>''m''</sup>)}} में आदिम ({{math|''p''<sup>''m''</sup> − 1}})- एकता का आदिम मूल है। | ||
== गुण == | == गुण == | ||
* क्योंकि सभी न्यूनतम बहुपद [[अलघुकरणीय बहुपद]] हैं, सभी आदिम बहुपद भी अलघुकरणीय हैं। | * क्योंकि सभी न्यूनतम बहुपद [[अलघुकरणीय बहुपद]] होते हैं, सभी आदिम बहुपद भी अलघुकरणीय होते हैं। | ||
* एक आदिम बहुपद में | * एक आदिम बहुपद में गैर-शून्य स्थिरांक होना चाहिए, अन्यथा यह ''x'' से विभाज्य होगा। GF(2) से अधिक, {{nowrap|''x'' + 1}} आदिम बहुपद है और अन्य सभी आदिम बहुपदों में विषम संख्याएँ हैं, क्योंकि किसी भी बहुपद मॉड 2 में समान संख्या में शब्द {{nowrap|''x'' + 1}} से विभाज्य हैं (इसका मूल के रूप में 1 है)। | ||
* GF(p) पर घात m का एक अलघुकरणीय बहुपद F(x), जहां p अभाज्य है, एक आदिम बहुपद है यदि सबसे छोटा धनात्मक पूर्णांक n ऐसा है कि F(x) | * GF(''p'') पर घात ''m'' का एक अलघुकरणीय बहुपद ''F''(''x''), जहां ''p'' अभाज्य है, एक आदिम बहुपद है यदि सबसे छोटा धनात्मक पूर्णांक ''n'' ऐसा है कि ''F''(''x'') {{nowrap|''x''<sup>''n''</sup> − 1}} को विभाजित करता {{nowrap|1=''n'' = ''p''<sup>''m''</sup> − 1}} है। | ||
* | * GF(''p'') पर बिल्कुल {{nowrap|''φ''(''p''<sup>''m''</sup> − 1)/''m''}} आदिम बहुपद ''m'' घात के होते है, जहां φ यूलर का कुल फलन है। | ||
* | * घात ''m'' के एक आदिम बहुपद के GF(''p<sup>m</sup>'') में ''m'' भिन्न मूल हैं, जिसमें सभी का क्रम {{nowrap|''p''<sup>''m''</sup> − 1}} (समूह सिद्धांत) है। इसका अर्थ है कि, यदि ''α'' एक ऐसा मूल है, तो {{nowrap|1=''α''{{i sup|''p''{{sup|''m''}}−1}} = 1}} और {{nowrap|''α''{{i sup|''i''}} ≠ 1}} {{nowrap|0 < ''i'' < ''p''<sup>''m''</sup> − 1}} के लिए है। | ||
* GF(p<sup>m</sup>) का स्पष्ट रूप | * GF(''p<sup>m</sup>'') में आदिम तत्व ''α की डिग्री m का आदिम बहुपद F(x)'' का स्पष्ट रूप {{nowrap|1=''F''(''x'') = (''x'' − ''α'')(''x'' − ''α''{{i sup|''p''}})(''x'' − ''α''{{i sup|''p''{{sup|2}}}})⋅⋅⋅(''x'' − ''α''{{i sup|''p''{{sup|''m''−1}}}})}} है। | ||
== | == प्रयोग == | ||
=== क्षेत्र तत्व प्रतिनिधित्व === | === क्षेत्र तत्व प्रतिनिधित्व === | ||
परिमित क्षेत्र के तत्वों का प्रतिनिधित्व करने के लिए आदिम बहुपदों का उपयोग किया जा सकता है। अगर | परिमित क्षेत्र के तत्वों का प्रतिनिधित्व करने के लिए आदिम बहुपदों का उपयोग किया जा सकता है। अगर GF(''p<sup>m</sup>'') में ''α'' आदिम बहुपद ''F''(''x'') का मूल है, तो GF(''p<sup>m</sup>'') के शून्येतर तत्वों को ''α'' की क्रमिक शक्तियों के रूप में दर्शाया गया है: | ||
:<math> | :<math> | ||
\mathrm{GF}(p^m) = \{ 0, 1= \alpha^0, \alpha, \alpha^2, \ldots, \alpha^{p^m-2} \} . | \mathrm{GF}(p^m) = \{ 0, 1= \alpha^0, \alpha, \alpha^2, \ldots, \alpha^{p^m-2} \} . | ||
</math> | </math> | ||
यह परिमित क्षेत्र के गैर-शून्य तत्वों के [[कंप्यूटर]] में | यह परिमित क्षेत्र के गैर-शून्य तत्वों के [[कंप्यूटर]] में आर्थिक प्रतिनिधित्व की अनुमति देता है, इसके अनुरूप एक्सपोनेंट द्वारा <math>\alpha.</math> तत्व का प्रतिनिधित्व करके, यह प्रतिनिधित्व गुणन को आसान बनाता है, क्योंकि यह घातांक [[मॉड्यूलर अंकगणित]] के योग <math>p^m-1</math> से मेल खाता है। | ||
=== छद्म-यादृच्छिक बिट पीढ़ी === | === छद्म-यादृच्छिक बिट पीढ़ी === | ||
GF(2) पर आदिम बहुपद, दो तत्वों के साथ क्षेत्र, [[छद्म यादृच्छिक संख्या जनरेटर]] के लिए उपयोग किया जा सकता है। वास्तव में, प्रत्येक रैखिक-फीडबैक शिफ्ट अधिकतम चक्र लंबाई (जो {{nowrap|2<sup>''n''</sup> − 1}} है, जहां ''n'' रैखिक फीडबैक शिफ्ट रजिस्टर की लंबाई है) आदिम बहुपद से बनाया जा सकता है।<ref>C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners</ref> | |||
=== | सामान्य तौर पर, GF(2) पर घात m के आदिम बहुपद के लिए, यह प्रक्रिया {{nowrap|2<sup>''m''</sup> − 1}} उसी क्रम को दोहराने से पहले छद्म-यादृच्छिक बिट्स उत्पन्न करेगी। | ||
चक्रीय अतिरेक जांच ( | |||
=== CRC कोड === | |||
चक्रीय अतिरेक जांच (CRC ) त्रुटि-पहचान कोड है जो संदेश बिटस्ट्रिंग को GF(2) पर बहुपद के गुणांक के रूप में व्याख्या करके संचालित करता है और इसे GF(2) पर भी एक निश्चित जनरेटर बहुपद द्वारा विभाजित करता है; [[सीआरसी का गणित|CRC का गणित]] देखें। आदिम बहुपद, या उनके गुणक, कभी-कभी जनरेटर बहुपद के लिए एक अच्छा विकल्प होते हैं क्योंकि वे दो बिट त्रुटियों का विश्वसनीय रूप से पता लगा सकते हैं जो संदेश बिटस्ट्रिंग में दूर तक होती हैं, घात ''n आदिम बहुपद के लिए'' {{nowrap|2<sup>''n''</sup> − 1}} की दूरी तक होती हैं। | |||
== आदिम त्रिपद == | == आदिम त्रिपद == | ||
आदिम बहुपदों का एक उपयोगी वर्ग आदिम त्रिपद है, जिनके पास केवल तीन गैर-शून्य शब्द हैं: {{nowrap|''x<sup>r</sup>'' + ''x<sup>k</sup>'' + 1}}. उनकी सादगी विशेष रूप से छोटे और तेज रैखिक-फीडबैक शिफ्ट रजिस्टरों के लिए बनाती है।<ref>{{Cite book |last=Gentle |first=James E. |url=https://www.worldcat.org/oclc/51534945 |title=यादृच्छिक संख्या पीढ़ी और मोंटे कार्लो के तरीके|date=2003 |publisher=Springer |isbn=0-387-00178-6 |edition=2 |location=New York |pages=39 |oclc=51534945}}</ref> कई परिणाम ट्रिनोमियल्स की प्रधानता का पता लगाने और परीक्षण करने के लिए तकनीक प्रदान करते हैं।<ref>{{Cite journal |last1=Zierler |first1=Neal |last2=Brillhart |first2=John |date=December 1968 |title=On primitive trinomials (Mod 2) |journal=Information and Control |language=en |volume=13 |issue=6 |pages=541,548,553 |doi=10.1016/S0019-9958(68)90973-X |doi-access=free }}</ref> | आदिम बहुपदों का एक उपयोगी वर्ग आदिम त्रिपद है, जिनके पास केवल तीन गैर-शून्य शब्द हैं: {{nowrap|''x<sup>r</sup>'' + ''x<sup>k</sup>'' + 1}}. उनकी सादगी विशेष रूप से छोटे और तेज रैखिक-फीडबैक शिफ्ट रजिस्टरों के लिए बनाती है।<ref>{{Cite book |last=Gentle |first=James E. |url=https://www.worldcat.org/oclc/51534945 |title=यादृच्छिक संख्या पीढ़ी और मोंटे कार्लो के तरीके|date=2003 |publisher=Springer |isbn=0-387-00178-6 |edition=2 |location=New York |pages=39 |oclc=51534945}}</ref> कई परिणाम ट्रिनोमियल्स की प्रधानता का पता लगाने और परीक्षण करने के लिए तकनीक प्रदान करते हैं।<ref>{{Cite journal |last1=Zierler |first1=Neal |last2=Brillhart |first2=John |date=December 1968 |title=On primitive trinomials (Mod 2) |journal=Information and Control |language=en |volume=13 |issue=6 |pages=541,548,553 |doi=10.1016/S0019-9958(68)90973-X |doi-access=free }}</ref> | ||
GF(2) पर बहुपदों के लिए, जहाँ {{nowrap|2<sup>''r''</sup> − 1}} एक Mersenne अभाज्य है, | |||
GF(2) पर बहुपदों के लिए, जहाँ {{nowrap|2<sup>''r''</sup> − 1}} एक Mersenne अभाज्य है, घात r का एक बहुपद आदिम है अगर और केवल अगर यह अलघुकरणीय है। (एक अलघुकरणीय बहुपद को देखते हुए, यह केवल आदिम नहीं है यदि x की अवधि एक गैर-तुच्छ कारक है {{nowrap|2<sup>''r''</sup> − 1}}. प्राइम्स का कोई गैर-तुच्छ कारक नहीं है।) हालांकि [[मेर्सन ट्विस्टर]] छद्म-यादृच्छिक संख्या जनरेटर ट्रिनोमियल का उपयोग नहीं करता है, यह इसका लाभ उठाता है। | |||
[[रिचर्ड ब्रेंट (वैज्ञानिक)]] इस रूप के आदिम ट्रिनोमियल्स को सारणीबद्ध कर रहे हैं, जैसे {{nowrap|''x''<sup>74207281</sup> + ''x''<sup>30684570</sup> + 1}}.<ref>{{cite web |url=http://maths.anu.edu.au/~brent/trinom.html |title=Search for Primitive Trinomials (mod 2) |first1=Richard P. |last1=Brent |authorlink1=Richard P. Brent |date=4 April 2016 |access-date=4 June 2020}}</ref><ref>{{cite arXiv |title=बारह नए आदिम बाइनरी ट्रिनोमियल्स|first1=Richard P. |last1=Brent |authorlink1=Richard P. Brent |first2=Paul |last2=Zimmermann |authorlink2=Paul Zimmermann (mathematician) |eprint=1605.09213 |class=math.NT |date=24 May 2016 <!-- unsupported parameter |url=https://maths-people.anu.edu.au/~brent/pd/rpb266.pdf -->}}</ref> इसका उपयोग विशाल अवधि के छद्म-यादृच्छिक संख्या जनरेटर बनाने के लिए किया जा सकता है {{nowrap|2<sup>74207281</sup> − 1}} ≈ {{val|3|e=22338617}}. | [[रिचर्ड ब्रेंट (वैज्ञानिक)]] इस रूप के आदिम ट्रिनोमियल्स को सारणीबद्ध कर रहे हैं, जैसे {{nowrap|''x''<sup>74207281</sup> + ''x''<sup>30684570</sup> + 1}}.<ref>{{cite web |url=http://maths.anu.edu.au/~brent/trinom.html |title=Search for Primitive Trinomials (mod 2) |first1=Richard P. |last1=Brent |authorlink1=Richard P. Brent |date=4 April 2016 |access-date=4 June 2020}}</ref><ref>{{cite arXiv |title=बारह नए आदिम बाइनरी ट्रिनोमियल्स|first1=Richard P. |last1=Brent |authorlink1=Richard P. Brent |first2=Paul |last2=Zimmermann |authorlink2=Paul Zimmermann (mathematician) |eprint=1605.09213 |class=math.NT |date=24 May 2016 <!-- unsupported parameter |url=https://maths-people.anu.edu.au/~brent/pd/rpb266.pdf -->}}</ref> इसका उपयोग विशाल अवधि के छद्म-यादृच्छिक संख्या जनरेटर बनाने के लिए किया जा सकता है {{nowrap|2<sup>74207281</sup> − 1}} ≈ {{val|3|e=22338617}}. |
Revision as of 23:53, 15 March 2023
परिमित क्षेत्र सिद्धांत में, क्षेत्र सिद्धांत (गणित) में, गणित की एक शाखा, आदिम बहुपद परिमित क्षेत्र GF(pm) के आदिम तत्व (परिमित क्षेत्र) का न्यूनतम बहुपद (क्षेत्र सिद्धांत) है। इसका मतलब है कि GF(p) = Z/pZ में गुणांक के साथ घात m का बहुपद F(X) एक आदिम बहुपद है यदि यह मोनिक बहुपद है और GF(pm) में इसका मूल α है ऐसा है कि संपूर्ण क्षेत्र GF(pm) है। इसका अर्थ यह है कि α GF(pm) में आदिम (pm − 1)- एकता का आदिम मूल है।
गुण
- क्योंकि सभी न्यूनतम बहुपद अलघुकरणीय बहुपद होते हैं, सभी आदिम बहुपद भी अलघुकरणीय होते हैं।
- एक आदिम बहुपद में गैर-शून्य स्थिरांक होना चाहिए, अन्यथा यह x से विभाज्य होगा। GF(2) से अधिक, x + 1 आदिम बहुपद है और अन्य सभी आदिम बहुपदों में विषम संख्याएँ हैं, क्योंकि किसी भी बहुपद मॉड 2 में समान संख्या में शब्द x + 1 से विभाज्य हैं (इसका मूल के रूप में 1 है)।
- GF(p) पर घात m का एक अलघुकरणीय बहुपद F(x), जहां p अभाज्य है, एक आदिम बहुपद है यदि सबसे छोटा धनात्मक पूर्णांक n ऐसा है कि F(x) xn − 1 को विभाजित करता n = pm − 1 है।
- GF(p) पर बिल्कुल φ(pm − 1)/m आदिम बहुपद m घात के होते है, जहां φ यूलर का कुल फलन है।
- घात m के एक आदिम बहुपद के GF(pm) में m भिन्न मूल हैं, जिसमें सभी का क्रम pm − 1 (समूह सिद्धांत) है। इसका अर्थ है कि, यदि α एक ऐसा मूल है, तो αpm−1 = 1 और αi ≠ 1 0 < i < pm − 1 के लिए है।
- GF(pm) में आदिम तत्व α की डिग्री m का आदिम बहुपद F(x) का स्पष्ट रूप F(x) = (x − α)(x − αp)(x − αp2)⋅⋅⋅(x − αpm−1) है।
प्रयोग
क्षेत्र तत्व प्रतिनिधित्व
परिमित क्षेत्र के तत्वों का प्रतिनिधित्व करने के लिए आदिम बहुपदों का उपयोग किया जा सकता है। अगर GF(pm) में α आदिम बहुपद F(x) का मूल है, तो GF(pm) के शून्येतर तत्वों को α की क्रमिक शक्तियों के रूप में दर्शाया गया है:
यह परिमित क्षेत्र के गैर-शून्य तत्वों के कंप्यूटर में आर्थिक प्रतिनिधित्व की अनुमति देता है, इसके अनुरूप एक्सपोनेंट द्वारा तत्व का प्रतिनिधित्व करके, यह प्रतिनिधित्व गुणन को आसान बनाता है, क्योंकि यह घातांक मॉड्यूलर अंकगणित के योग से मेल खाता है।
छद्म-यादृच्छिक बिट पीढ़ी
GF(2) पर आदिम बहुपद, दो तत्वों के साथ क्षेत्र, छद्म यादृच्छिक संख्या जनरेटर के लिए उपयोग किया जा सकता है। वास्तव में, प्रत्येक रैखिक-फीडबैक शिफ्ट अधिकतम चक्र लंबाई (जो 2n − 1 है, जहां n रैखिक फीडबैक शिफ्ट रजिस्टर की लंबाई है) आदिम बहुपद से बनाया जा सकता है।[1]
सामान्य तौर पर, GF(2) पर घात m के आदिम बहुपद के लिए, यह प्रक्रिया 2m − 1 उसी क्रम को दोहराने से पहले छद्म-यादृच्छिक बिट्स उत्पन्न करेगी।
CRC कोड
चक्रीय अतिरेक जांच (CRC ) त्रुटि-पहचान कोड है जो संदेश बिटस्ट्रिंग को GF(2) पर बहुपद के गुणांक के रूप में व्याख्या करके संचालित करता है और इसे GF(2) पर भी एक निश्चित जनरेटर बहुपद द्वारा विभाजित करता है; CRC का गणित देखें। आदिम बहुपद, या उनके गुणक, कभी-कभी जनरेटर बहुपद के लिए एक अच्छा विकल्प होते हैं क्योंकि वे दो बिट त्रुटियों का विश्वसनीय रूप से पता लगा सकते हैं जो संदेश बिटस्ट्रिंग में दूर तक होती हैं, घात n आदिम बहुपद के लिए 2n − 1 की दूरी तक होती हैं।
आदिम त्रिपद
आदिम बहुपदों का एक उपयोगी वर्ग आदिम त्रिपद है, जिनके पास केवल तीन गैर-शून्य शब्द हैं: xr + xk + 1. उनकी सादगी विशेष रूप से छोटे और तेज रैखिक-फीडबैक शिफ्ट रजिस्टरों के लिए बनाती है।[2] कई परिणाम ट्रिनोमियल्स की प्रधानता का पता लगाने और परीक्षण करने के लिए तकनीक प्रदान करते हैं।[3]
GF(2) पर बहुपदों के लिए, जहाँ 2r − 1 एक Mersenne अभाज्य है, घात r का एक बहुपद आदिम है अगर और केवल अगर यह अलघुकरणीय है। (एक अलघुकरणीय बहुपद को देखते हुए, यह केवल आदिम नहीं है यदि x की अवधि एक गैर-तुच्छ कारक है 2r − 1. प्राइम्स का कोई गैर-तुच्छ कारक नहीं है।) हालांकि मेर्सन ट्विस्टर छद्म-यादृच्छिक संख्या जनरेटर ट्रिनोमियल का उपयोग नहीं करता है, यह इसका लाभ उठाता है।
रिचर्ड ब्रेंट (वैज्ञानिक) इस रूप के आदिम ट्रिनोमियल्स को सारणीबद्ध कर रहे हैं, जैसे x74207281 + x30684570 + 1.[4][5] इसका उपयोग विशाल अवधि के छद्म-यादृच्छिक संख्या जनरेटर बनाने के लिए किया जा सकता है 274207281 − 1 ≈ 3×1022338617.
संदर्भ
- ↑ C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners
- ↑ Gentle, James E. (2003). यादृच्छिक संख्या पीढ़ी और मोंटे कार्लो के तरीके (2 ed.). New York: Springer. p. 39. ISBN 0-387-00178-6. OCLC 51534945.
- ↑ Zierler, Neal; Brillhart, John (December 1968). "On primitive trinomials (Mod 2)". Information and Control (in English). 13 (6): 541, 548, 553. doi:10.1016/S0019-9958(68)90973-X.
- ↑ Brent, Richard P. (4 April 2016). "Search for Primitive Trinomials (mod 2)". Retrieved 4 June 2020.
- ↑ Brent, Richard P.; Zimmermann, Paul (24 May 2016). "बारह नए आदिम बाइनरी ट्रिनोमियल्स". arXiv:1605.09213 [math.NT].