फ़र्मेट प्राइमैलिटी परीक्षण: Difference between revisions
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 9: | Line 9: | ||
यदि कोई यह परीक्षण करना चाहता है कि क्या ''p'' अभाज्य है, तो हम ऐसे यादृच्छिक पूर्णांक चुन सकते हैं जो की ''p'' से विभाज्य नहीं हैं और देख सकते हैं कि समानता धारण करता है या नहीं। यदि समानता ''a'' के मान के लिए मान्य नहीं है, तो ''p'' समग्र है। यदि ''p'' समग्र है तो यह सर्वांगसमता यादृच्छिक ''a'' के लिए रुकने की संभावना नहीं है।<ref name="PSW">{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free }}</ref> इसलिए, यदि समानता ''a'' के या अधिक मानों के लिए मान्य है, तो हम मान सकते हैं कि ''p'' संभावित अभाज्य है। | यदि कोई यह परीक्षण करना चाहता है कि क्या ''p'' अभाज्य है, तो हम ऐसे यादृच्छिक पूर्णांक चुन सकते हैं जो की ''p'' से विभाज्य नहीं हैं और देख सकते हैं कि समानता धारण करता है या नहीं। यदि समानता ''a'' के मान के लिए मान्य नहीं है, तो ''p'' समग्र है। यदि ''p'' समग्र है तो यह सर्वांगसमता यादृच्छिक ''a'' के लिए रुकने की संभावना नहीं है।<ref name="PSW">{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free }}</ref> इसलिए, यदि समानता ''a'' के या अधिक मानों के लिए मान्य है, तो हम मान सकते हैं कि ''p'' संभावित अभाज्य है। | ||
चूंकि, ध्यान दें कि उपरोक्त सर्वांगसमता <math>a \equiv 1 \pmod{p}</math> के लिए नगण्य | चूंकि, ध्यान दें कि उपरोक्त सर्वांगसमता <math>a \equiv 1 \pmod{p}</math> के लिए नगण्य रूप से मान्य है क्योंकि सर्वांगसम संबंध घातांक के साथ संगत है। यदि p विषम है, तो इसी कारण से, यह <math>a \equiv -1 \pmod{p} </math> के लिए भी नगण्य रूप से मान्य है। यही कारण है कि कोई प्रायः अंतराल <math>1 < a < p - 1 </math> में | ||
अतः कोई भी यादृच्छिक a चुनता है | अतः कोई भी यादृच्छिक a चुनता है | ||
:<math>a^{n-1} \equiv 1 \pmod{n}</math> | :<math>a^{n-1} \equiv 1 \pmod{n}</math> | ||
जब n मिश्रित होता है तो उसे फ़र्मेट लियार के रूप में जाना जाता है। इस स्तिथि | जब n मिश्रित होता है तो उसे फ़र्मेट लियार के रूप में जाना जाता है। इस स्तिथि में n को आधार a के लिए [[फ़र्मेट स्यूडोप्राइम]] कहा जाता है। | ||
यदि हम ऐसा कोई चुनते हैं | यदि हम ऐसा कोई चुनते हैं | ||
:<math>a^{n-1} \not\equiv 1 \pmod{n}</math> | :<math>a^{n-1} \not\equiv 1 \pmod{n} </math> | ||
तब a को n की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता के रूप में जाना जाता है। | तब a को n की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता के रूप में जाना जाता है। | ||
| Line 22: | Line 22: | ||
मान लीजिए हम यह निर्धारित करना चाहते हैं कि ''n = 221'' अभाज्य है या नहीं। यादृच्छिक रूप से 1 < ''a'' < 220, मान लीजिए ''a = 38'' चुनें। हम उपरोक्त समानता की जाँच करते हैं और प्राप्त करते हैं किन्तु यह बनाये रखता है: | मान लीजिए हम यह निर्धारित करना चाहते हैं कि ''n = 221'' अभाज्य है या नहीं। यादृच्छिक रूप से 1 < ''a'' < 220, मान लीजिए ''a = 38'' चुनें। हम उपरोक्त समानता की जाँच करते हैं और प्राप्त करते हैं किन्तु यह बनाये रखता है: | ||
:<math>a^{n-1} = 38^{220} \equiv 1 \pmod{221}.</math> | :<math>a^{n-1} = 38^{220} \equiv 1 \pmod{221}.</math> | ||
या तो 221 अभाज्य है, या 38 फ़र्मेट | या तो 221 अभाज्य है, या 38 फ़र्मेट मिथ्याभाषी है, इसलिए हम एक ओर a रखते हैं, मान लीजिए 24: | ||
:<math>a^{n-1} = 24^{220} \equiv 81 \not\equiv 1 \pmod{221}.</math> | :<math>a^{n-1} = 24^{220} \equiv 81 \not\equiv 1 \pmod{221}.</math> | ||
तो 221 समग्र है और 38 वास्तव में फ़र्मेट | तो 221 समग्र है और 38 वास्तव में फ़र्मेट मिथ्याभाषी था। इसके अतिरिक्त , 24 221 की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता है। | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
एल्गोरिथ्म को इस प्रकार लिखा जा सकता है: | एल्गोरिथ्म को इस प्रकार लिखा जा सकता है: | ||
:इनपुट: ''n'': प्रारंभिकता के परीक्षण के लिए मान, ''n''>3; ''k'': | :इनपुट: ''n'': प्रारंभिकता के परीक्षण के लिए मान, ''n''>3; ''k'': पैरामीटर जो प्रारंभिकता के परीक्षण के लिए समय की संख्या निर्धारित करता है | ||
:आउटपुट: ''मिश्रित'' | :आउटपुट: ''मिश्रित'' यदि ''n'' समग्र है, अन्यथा ''संभवतः अभाज्य है तब'' | ||
:''k'' बार दोहराएं: | :''k'' बार दोहराएं: | ||
::[2, एन - 2] की श्रेणी में यादृच्छिक रूप से चुनें | ::[2, एन - 2] की श्रेणी में यादृच्छिक रूप से चुनें | ||
::यदि | ::यदि <math>a^{n-1}\not\equiv1 \pmod n</math>, संभवत: प्रमुख लौटाएं | ||
:यदि कंपोजिट कभी वापस नहीं किया जाता है: संभवतः प्रमुख लौटाएं | :यदि कंपोजिट कभी वापस नहीं किया जाता है: संभवतः प्रमुख लौटाएं | ||
| Line 39: | Line 39: | ||
=== समष्टि === | === समष्टि === | ||
इस प्रकार से [[मॉड्यूलर घातांक]] और बहुपरिशुद्धता गुणन के लिए तीव्र एल्गोरिदम का उपयोग करते हुए, इस एल्गोरिदम का चलने का समय {{math|[[Big O notation|O]](''k'' log<sup>2</sup>''n'' log log ''n'') {{=}} [[Big O notation#Extensions to the Bachmann–Landau notations|Õ]](''k'' log<sup>2</sup>''n'')}} है , जहां k वह संख्या है जितनी बार हम यादृच्छिक a का परीक्षण करते हैं, और n वह मान है जिसे हम प्रारंभिकता के लिए परीक्षण करना चाहते हैं; विवरण के लिए मिलर-राबिन प्राइमलिटी परीक्षण समष्टि | इस प्रकार से [[मॉड्यूलर घातांक]] और बहुपरिशुद्धता गुणन के लिए तीव्र एल्गोरिदम का उपयोग करते हुए, इस एल्गोरिदम का चलने का समय {{math|[[Big O notation|O]](''k'' log<sup>2</sup>''n'' log log ''n'') {{=}} [[Big O notation#Extensions to the Bachmann–Landau notations|Õ]](''k'' log<sup>2</sup>''n'')}} है , जहां k वह संख्या है जितनी बार हम यादृच्छिक a का परीक्षण करते हैं, और n वह मान है जिसे हम प्रारंभिकता के लिए परीक्षण करना चाहते हैं; विवरण के लिए मिलर-राबिन प्राइमलिटी परीक्षण समष्टि मिलर-राबिन प्राइमलिटी परीक्षण देखें। | ||
==दोष== | ==दोष== | ||
किसी भी आधार a>1 के लिए अनंत रूप से अनेक फ़र्मेट स्यूडोप्राइम हैं।{{r|PSW|p=Theorem 1}} | किसी भी आधार a>1 के लिए अनंत रूप से अनेक फ़र्मेट स्यूडोप्राइम हैं।{{r|PSW|p=Theorem 1}} | ||
इससे भी दोष पूर्ण तथ्य यह है कि [[कारमाइकल संख्या|फ़र्मेट स्यूडोप्राइम्स]] अनंत हैं।<ref name="Alford1994">{{cite journal |last1=Alford |first1=W. R. |author-link=W. R. (Red) Alford |last2=Granville |first2=Andrew |author-link2=Andrew Granville |last3=Pomerance |first3=Carl |author-link3=Carl Pomerance |year=1994 |title=कारमाइकल संख्याएँ अनन्त रूप से अनेक हैं|journal=[[Annals of Mathematics]] |doi=10.2307/2118576 |volume=140 |issue=3 |pages=703–722 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf |jstor=2118576 }}</ref> ये संख्याएं <math>n</math> हैं | इससे भी दोष पूर्ण तथ्य यह है कि [[कारमाइकल संख्या|फ़र्मेट स्यूडोप्राइम्स]] अनंत हैं।<ref name="Alford1994">{{cite journal |last1=Alford |first1=W. R. |author-link=W. R. (Red) Alford |last2=Granville |first2=Andrew |author-link2=Andrew Granville |last3=Pomerance |first3=Carl |author-link3=Carl Pomerance |year=1994 |title=कारमाइकल संख्याएँ अनन्त रूप से अनेक हैं|journal=[[Annals of Mathematics]] |doi=10.2307/2118576 |volume=140 |issue=3 |pages=703–722 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf |jstor=2118576 }}</ref> ये संख्याएं <math>n</math> हैं जिसके लिए <u>सभी</u> मान <math>a</math> साथ <math>\operatorname{gcd}(a, n) = 1</math> फ़र्मेट मिथ्याभाषी हैं. इन संख्याओं के लिए, फ़र्मेट प्राइमैलिटी परीक्षण का बार-बार उपयोग कारकों के लिए सरल यादृच्छिक खोज के समान ही कार्य करता है। जबकि [[कारमाइकल संख्या|कारमाइकल संख्याएँ]] अभाज्य संख्याओं की तुलना में अधिक दुर्लभ हैं (कारमाइकल संख्याओं की संख्या के लिए एर्डोज़ की ऊपरी श्रेणी <ref> | ||
{{cite journal |author = Paul Erdős | {{cite journal |author = Paul Erdős | ||
|date=1956 |title=On pseudoprimes and Carmichael numbers | |date=1956 |title=On pseudoprimes and Carmichael numbers | ||
|journal=Publ. Math. Debrecen |volume=4 |pages=201–206|author-link=Paul Erdős }}</ref> अभाज्य संख्या प्रमेय से कम है अभाज्य संख्या फ़ंक्शन n/log(n)) उनमें से पर्याप्त हैं कि फ़र्मेट का प्राइमलिटी परीक्षण प्रायः | |journal=Publ. Math. Debrecen |volume=4 |pages=201–206|author-link=Paul Erdős }}</ref> अभाज्य संख्या प्रमेय से कम है अभाज्य संख्या फ़ंक्शन n/log(n)) उनमें से पर्याप्त हैं कि फ़र्मेट का प्राइमलिटी परीक्षण प्रायः उपरोक्त रूप में उपयोग नहीं किया जाता है। इसके अतिरिक्त ,फ़र्मेट परीक्षण के अन्य अधिक सशक्त एक्सटेंशन, जैसे कि बैली-पीएसडब्ल्यू, मिलर-राबिन और सोलोवे-स्ट्रैसन का अधिक सामान्यतः उपयोग किया जाता है। | ||
सामान्य रूप से, यदि <math>n</math> भाज्य संख्या है जो कारमाइकल संख्या नहीं है, तो सभी का कम से कम आधी संख्या होगी | सामान्य रूप से, यदि <math>n</math> भाज्य संख्या है जो कारमाइकल संख्या नहीं है, तो सभी का कम से कम आधी संख्या होगी | ||
| Line 56: | Line 56: | ||
:<math>(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}</math> | :<math>(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}</math> | ||
और सब कुछ <math>a \cdot a_i</math> के लिए <math>i = 1, 2, ..., s</math> फ़र्मेट | और सब कुछ <math>a \cdot a_i</math> के लिए <math>i = 1, 2, ..., s</math> फ़र्मेट प्रमाणितकर्ता हैं। | ||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
जैसा कि ऊपर दर्शाया गया है, की अधिकांश एप्लिकेशन मिलर-राबिन प्राइमलिटी परीक्षण मिलर-राबिन या बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण का उपयोग प्राइमलिटी के लिए करते हैं। कभी-कभी प्रदर्शन में सुधार के लिए पहले फ़र्मेट परीक्षण (छोटे अभाज्यों द्वारा कुछ परीक्षण विभाजन के साथ) किया जाता है। संस्करण 3.0 के पश्चात से [[जीएनयू मल्टीपल प्रिसिजन अरिथमेटिक लाइब्रेरी]] ट्रायल डिवीजन के पश्चात् और मिलर-राबिन परीक्षण चलाने से प्रथम बेस-210 फ़र्मेट परीक्षण का उपयोग करती है। इस प्रकार से [[लिबगक्रिप्ट]] फ़र्मेट परीक्षण के लिए आधार 2 के साथ समान प्रक्रिया का उपयोग करता है, किन्तु | जैसा कि ऊपर दर्शाया गया है, की अधिकांश एप्लिकेशन मिलर-राबिन प्राइमलिटी परीक्षण मिलर-राबिन या बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण का उपयोग प्राइमलिटी के लिए करते हैं। कभी-कभी प्रदर्शन में सुधार के लिए पहले फ़र्मेट परीक्षण (छोटे अभाज्यों द्वारा कुछ परीक्षण विभाजन के साथ) किया जाता है। संस्करण 3.0 के पश्चात से [[जीएनयू मल्टीपल प्रिसिजन अरिथमेटिक लाइब्रेरी]] ट्रायल डिवीजन के पश्चात् और मिलर-राबिन परीक्षण चलाने से प्रथम बेस-210 फ़र्मेट परीक्षण का उपयोग करती है। इस प्रकार से [[लिबगक्रिप्ट]] फ़र्मेट परीक्षण के लिए आधार 2 के साथ समान प्रक्रिया का उपयोग करता है, किन्तु [[ओपनएसएसएल]] नहीं करता है। | ||
अधिकांश उच्च संख्या में लाइब्रेरी जैसे कि जीएमपी के साथ वास्तविक में, फ़र्मेट परीक्षण मिलर-राबिन परीक्षण की तुलना में अधिक तीव्र | अधिकांश उच्च संख्या में लाइब्रेरी जैसे कि जीएमपी के साथ वास्तविक में, फ़र्मेट परीक्षण मिलर-राबिन परीक्षण की तुलना में अधिक तीव्र नहीं है, और कई इनपुट के लिए धीमा हो सकता है।<ref>{{citation|author=Joe Hurd|date=2003|title=Verification of the Miller–Rabin Probabilistic Primality Test|page=2|citeseerx=10.1.1.105.3196}}</ref> | ||
इस प्रकार से अपवाद के रूप में, ओपनपीएफजीडब्ल्यू संभावित प्राइम परीक्षण के लिए केवल फ़र्मेट परीक्षण का उपयोग करता है। प्रोग्राम का उपयोग सामान्यतः अधिक उच्च इनपुट के साथ अधिकतम गति के लक्ष्य के साथ बहु-हज़ार अंकों वाले इनपुट के साथ किया जाता है। अतः अन्य प्रसिद्ध प्रोग्राम | इस प्रकार से अपवाद के रूप में, ओपनपीएफजीडब्ल्यू संभावित प्राइम परीक्षण के लिए केवल फ़र्मेट परीक्षण का उपयोग करता है। प्रोग्राम का उपयोग सामान्यतः अधिक उच्च इनपुट के साथ अधिकतम गति के लक्ष्य के साथ बहु-हज़ार अंकों वाले इनपुट के साथ किया जाता है। अतः अन्य प्रसिद्ध प्रोग्राम जो केवल फ़र्मेट परीक्षण पर निर्भर करता है वह [[काफ़ी अच्छी गोपनीयता|पीजीपी]] है जहां इसका उपयोग केवल स्व-निर्मित बड़े यादृच्छिक मानों के परीक्षण के लिए किया जाता है (ओपन सोर्स समकक्ष, [[जीएनयू गोपनीयता गार्ड|जीएनयू प्राइवेसी गार्ड]], मिलर-राबिन परीक्षणों के पश्चात फ़र्मेट प्रीपरीक्षण का उपयोग करता है)। | ||
==संदर्भ== | ==संदर्भ== | ||
| Line 71: | Line 71: | ||
{{number theoretic algorithms}} | {{number theoretic algorithms}} | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category:CS1 maint]] | |||
[[Category: | [[Category:Collapse templates]] | ||
[[Category:Created On 18/07/2023]] | [[Category:Created On 18/07/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Translated in Hindi]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:आदिमता परीक्षण]] | |||
[[Category:मॉड्यूलर अंकगणित]] | |||
Latest revision as of 12:22, 31 July 2023
फ़र्मेट प्राइमैलिटी परीक्षण यह निर्धारित करने के लिए यादृच्छिक एल्गोरिदम परीक्षण है कि कोई संख्या संभावित अभाज्य है या नहीं है।
अवधारणा
फ़र्मेट का छोटा प्रमेय यह दर्शाता है कि यदि p अभाज्य है और a, p से विभाज्य नहीं है, तो
यदि कोई यह परीक्षण करना चाहता है कि क्या p अभाज्य है, तो हम ऐसे यादृच्छिक पूर्णांक चुन सकते हैं जो की p से विभाज्य नहीं हैं और देख सकते हैं कि समानता धारण करता है या नहीं। यदि समानता a के मान के लिए मान्य नहीं है, तो p समग्र है। यदि p समग्र है तो यह सर्वांगसमता यादृच्छिक a के लिए रुकने की संभावना नहीं है।[1] इसलिए, यदि समानता a के या अधिक मानों के लिए मान्य है, तो हम मान सकते हैं कि p संभावित अभाज्य है।
चूंकि, ध्यान दें कि उपरोक्त सर्वांगसमता के लिए नगण्य रूप से मान्य है क्योंकि सर्वांगसम संबंध घातांक के साथ संगत है। यदि p विषम है, तो इसी कारण से, यह के लिए भी नगण्य रूप से मान्य है। यही कारण है कि कोई प्रायः अंतराल में
अतः कोई भी यादृच्छिक a चुनता है
जब n मिश्रित होता है तो उसे फ़र्मेट लियार के रूप में जाना जाता है। इस स्तिथि में n को आधार a के लिए फ़र्मेट स्यूडोप्राइम कहा जाता है।
यदि हम ऐसा कोई चुनते हैं
तब a को n की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता के रूप में जाना जाता है।
उदाहरण
मान लीजिए हम यह निर्धारित करना चाहते हैं कि n = 221 अभाज्य है या नहीं। यादृच्छिक रूप से 1 < a < 220, मान लीजिए a = 38 चुनें। हम उपरोक्त समानता की जाँच करते हैं और प्राप्त करते हैं किन्तु यह बनाये रखता है:
या तो 221 अभाज्य है, या 38 फ़र्मेट मिथ्याभाषी है, इसलिए हम एक ओर a रखते हैं, मान लीजिए 24:
तो 221 समग्र है और 38 वास्तव में फ़र्मेट मिथ्याभाषी था। इसके अतिरिक्त , 24 221 की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता है।
एल्गोरिदम
एल्गोरिथ्म को इस प्रकार लिखा जा सकता है:
- इनपुट: n: प्रारंभिकता के परीक्षण के लिए मान, n>3; k: पैरामीटर जो प्रारंभिकता के परीक्षण के लिए समय की संख्या निर्धारित करता है
- आउटपुट: मिश्रित यदि n समग्र है, अन्यथा संभवतः अभाज्य है तब
- k बार दोहराएं:
- [2, एन - 2] की श्रेणी में यादृच्छिक रूप से चुनें
- यदि , संभवत: प्रमुख लौटाएं
- यदि कंपोजिट कभी वापस नहीं किया जाता है: संभवतः प्रमुख लौटाएं
a मान 1 और n-1 का उपयोग नहीं किया जाता है क्योंकि समानता क्रमशः सभी n और सभी विषम n के लिए होती है, इसलिए उनका परीक्षण करने से कोई मान नहीं जुड़ता है।
समष्टि
इस प्रकार से मॉड्यूलर घातांक और बहुपरिशुद्धता गुणन के लिए तीव्र एल्गोरिदम का उपयोग करते हुए, इस एल्गोरिदम का चलने का समय O(k log2n log log n) = Õ(k log2n) है , जहां k वह संख्या है जितनी बार हम यादृच्छिक a का परीक्षण करते हैं, और n वह मान है जिसे हम प्रारंभिकता के लिए परीक्षण करना चाहते हैं; विवरण के लिए मिलर-राबिन प्राइमलिटी परीक्षण समष्टि मिलर-राबिन प्राइमलिटी परीक्षण देखें।
दोष
किसी भी आधार a>1 के लिए अनंत रूप से अनेक फ़र्मेट स्यूडोप्राइम हैं।[1]: Theorem 1
इससे भी दोष पूर्ण तथ्य यह है कि फ़र्मेट स्यूडोप्राइम्स अनंत हैं।[2] ये संख्याएं हैं जिसके लिए सभी मान साथ फ़र्मेट मिथ्याभाषी हैं. इन संख्याओं के लिए, फ़र्मेट प्राइमैलिटी परीक्षण का बार-बार उपयोग कारकों के लिए सरल यादृच्छिक खोज के समान ही कार्य करता है। जबकि कारमाइकल संख्याएँ अभाज्य संख्याओं की तुलना में अधिक दुर्लभ हैं (कारमाइकल संख्याओं की संख्या के लिए एर्डोज़ की ऊपरी श्रेणी [3] अभाज्य संख्या प्रमेय से कम है अभाज्य संख्या फ़ंक्शन n/log(n)) उनमें से पर्याप्त हैं कि फ़र्मेट का प्राइमलिटी परीक्षण प्रायः उपरोक्त रूप में उपयोग नहीं किया जाता है। इसके अतिरिक्त ,फ़र्मेट परीक्षण के अन्य अधिक सशक्त एक्सटेंशन, जैसे कि बैली-पीएसडब्ल्यू, मिलर-राबिन और सोलोवे-स्ट्रैसन का अधिक सामान्यतः उपयोग किया जाता है।
सामान्य रूप से, यदि भाज्य संख्या है जो कारमाइकल संख्या नहीं है, तो सभी का कम से कम आधी संख्या होगी
- (अर्थात। )
फ़र्मेट प्रमाणितकर्ता हैं। इसके प्रमाण के लिए, मान लीजिए कि एक फ़र्मेट प्रमाणितकर्ता है और , , ..., फ़र्मेट मिथ्याभाषी है। तब
और सब कुछ के लिए फ़र्मेट प्रमाणितकर्ता हैं।
अनुप्रयोग
जैसा कि ऊपर दर्शाया गया है, की अधिकांश एप्लिकेशन मिलर-राबिन प्राइमलिटी परीक्षण मिलर-राबिन या बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण का उपयोग प्राइमलिटी के लिए करते हैं। कभी-कभी प्रदर्शन में सुधार के लिए पहले फ़र्मेट परीक्षण (छोटे अभाज्यों द्वारा कुछ परीक्षण विभाजन के साथ) किया जाता है। संस्करण 3.0 के पश्चात से जीएनयू मल्टीपल प्रिसिजन अरिथमेटिक लाइब्रेरी ट्रायल डिवीजन के पश्चात् और मिलर-राबिन परीक्षण चलाने से प्रथम बेस-210 फ़र्मेट परीक्षण का उपयोग करती है। इस प्रकार से लिबगक्रिप्ट फ़र्मेट परीक्षण के लिए आधार 2 के साथ समान प्रक्रिया का उपयोग करता है, किन्तु ओपनएसएसएल नहीं करता है।
अधिकांश उच्च संख्या में लाइब्रेरी जैसे कि जीएमपी के साथ वास्तविक में, फ़र्मेट परीक्षण मिलर-राबिन परीक्षण की तुलना में अधिक तीव्र नहीं है, और कई इनपुट के लिए धीमा हो सकता है।[4]
इस प्रकार से अपवाद के रूप में, ओपनपीएफजीडब्ल्यू संभावित प्राइम परीक्षण के लिए केवल फ़र्मेट परीक्षण का उपयोग करता है। प्रोग्राम का उपयोग सामान्यतः अधिक उच्च इनपुट के साथ अधिकतम गति के लक्ष्य के साथ बहु-हज़ार अंकों वाले इनपुट के साथ किया जाता है। अतः अन्य प्रसिद्ध प्रोग्राम जो केवल फ़र्मेट परीक्षण पर निर्भर करता है वह पीजीपी है जहां इसका उपयोग केवल स्व-निर्मित बड़े यादृच्छिक मानों के परीक्षण के लिए किया जाता है (ओपन सोर्स समकक्ष, जीएनयू प्राइवेसी गार्ड, मिलर-राबिन परीक्षणों के पश्चात फ़र्मेट प्रीपरीक्षण का उपयोग करता है)।
संदर्भ
- ↑ 1.0 1.1 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.
- ↑ Alford, W. R.; Granville, Andrew; Pomerance, Carl (1994). "कारमाइकल संख्याएँ अनन्त रूप से अनेक हैं" (PDF). Annals of Mathematics. 140 (3): 703–722. doi:10.2307/2118576. JSTOR 2118576.
- ↑ Paul Erdős (1956). "On pseudoprimes and Carmichael numbers". Publ. Math. Debrecen. 4: 201–206.
- ↑ Joe Hurd (2003), Verification of the Miller–Rabin Probabilistic Primality Test, p. 2, CiteSeerX 10.1.1.105.3196
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 31.8: Primality testing". Introduction to Algorithms (Second ed.). MIT Press; McGraw-Hill. p. 889–890. ISBN 0-262-03293-7.
{{cite book}}: CS1 maint: multiple names: authors list (link)
