फ़र्मेट प्राइमैलिटी परीक्षण: Difference between revisions

Revision as of 09:48, 22 July 2023

फ़र्मेट प्राइमैलिटी परीक्षण यह निर्धारित करने के लिए यादृच्छिक एल्गोरिदम परीक्षण है कि कोई संख्या संभावित अभाज्य है या नहीं है।

अवधारणा

फ़र्मेट का छोटा प्रमेय यह दर्शाता है कि यदि p अभाज्य है और a, p से विभाज्य नहीं है, तो

a^{p-1}\equiv 1{\pmod {p}}.

यदि कोई यह परीक्षण करना चाहता है कि क्या p अभाज्य है, तो हम ऐसे यादृच्छिक पूर्णांक चुन सकते हैं जो की p से विभाज्य नहीं हैं और देख सकते हैं कि समानता धारण करता है या नहीं। यदि समानता a के मान के लिए मान्य नहीं है, तो p समग्र है। यदि p समग्र है तो यह सर्वांगसमता यादृच्छिक a के लिए रुकने की संभावना नहीं है।^[1] इसलिए, यदि समानता a के या अधिक मानों के लिए मान्य है, तो हम मान सकते हैं कि p संभावित अभाज्य है।

चूंकि, ध्यान दें कि उपरोक्त सर्वांगसमता $a\equiv 1{\pmod {p}}$ के लिए नगण्य रूप से मान्य है क्योंकि सर्वांगसम संबंध घातांक के साथ संगत है। यदि p विषम है, तो इसी कारण से, यह $a\equiv -1{\pmod {p}}$ के लिए भी नगण्य रूप से मान्य है। यही कारण है कि कोई प्रायः अंतराल $1<a<p-1$ में

अतः कोई भी यादृच्छिक a चुनता है

a^{n-1}\equiv 1{\pmod {n}}

जब n मिश्रित होता है तो उसे फ़र्मेट लियार के रूप में जाना जाता है। इस स्तिथि में n को आधार a के लिए फ़र्मेट स्यूडोप्राइम कहा जाता है।

यदि हम ऐसा कोई चुनते हैं

a^{n-1}\not \equiv 1{\pmod {n}}

तब a को n की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता के रूप में जाना जाता है।

उदाहरण

मान लीजिए हम यह निर्धारित करना चाहते हैं कि n = 221 अभाज्य है या नहीं। यादृच्छिक रूप से 1 < a < 220, मान लीजिए a = 38 चुनें। हम उपरोक्त समानता की जाँच करते हैं और प्राप्त करते हैं किन्तु यह बनाये रखता है:

a^{n-1}=38^{220}\equiv 1{\pmod {221}}.

या तो 221 अभाज्य है, या 38 फ़र्मेट मिथ्याभाषी है, इसलिए हम एक ओर a रखते हैं, मान लीजिए 24:

a^{n-1}=24^{220}\equiv 81\not \equiv 1{\pmod {221}}.

तो 221 समग्र है और 38 वास्तव में फ़र्मेट मिथ्याभाषी था। इसके अतिरिक्त , 24 221 की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता है।

एल्गोरिदम

एल्गोरिथ्म को इस प्रकार लिखा जा सकता है:

इनपुट: n: प्रारंभिकता के परीक्षण के लिए मान, n>3; k: पैरामीटर जो प्रारंभिकता के परीक्षण के लिए समय की संख्या निर्धारित करता है

आउटपुट: मिश्रित यदि n समग्र है, अन्यथा संभवतः अभाज्य है तब

k बार दोहराएं:

[2, एन - 2] की श्रेणी में यादृच्छिक रूप से चुनें

यदि

a^{n-1}\not \equiv 1{\pmod {n}}

, संभवत: प्रमुख लौटाएं

यदि कंपोजिट कभी वापस नहीं किया जाता है: संभवतः प्रमुख लौटाएं

a मान 1 और n-1 का उपयोग नहीं किया जाता है क्योंकि समानता क्रमशः सभी n और सभी विषम n के लिए होती है, इसलिए उनका परीक्षण करने से कोई मान नहीं जुड़ता है।

समष्टि

इस प्रकार से मॉड्यूलर घातांक और बहुपरिशुद्धता गुणन के लिए तीव्र एल्गोरिदम का उपयोग करते हुए, इस एल्गोरिदम का चलने का समय $O (k log 2 n log log n) = Õ (k log 2 n)$ है , जहां k वह संख्या है जितनी बार हम यादृच्छिक a का परीक्षण करते हैं, और n वह मान है जिसे हम प्रारंभिकता के लिए परीक्षण करना चाहते हैं; विवरण के लिए मिलर-राबिन प्राइमलिटी परीक्षण समष्टि मिलर-राबिन प्राइमलिटी परीक्षण देखें।

दोष

किसी भी आधार a>1 के लिए अनंत रूप से अनेक फ़र्मेट स्यूडोप्राइम हैं।^[1]^{: Theorem 1}

इससे भी दोष पूर्ण तथ्य यह है कि फ़र्मेट स्यूडोप्राइम्स अनंत हैं।^[2] ये संख्याएं $n$ हैं जिसके लिए सभी मान $a$ साथ $\operatorname {gcd} (a,n)=1$ फ़र्मेट मिथ्याभाषी हैं. इन संख्याओं के लिए, फ़र्मेट प्राइमैलिटी परीक्षण का बार-बार उपयोग कारकों के लिए सरल यादृच्छिक खोज के समान ही कार्य करता है। जबकि कारमाइकल संख्याएँ अभाज्य संख्याओं की तुलना में अधिक दुर्लभ हैं (कारमाइकल संख्याओं की संख्या के लिए एर्डोज़ की ऊपरी श्रेणी ^[3] अभाज्य संख्या प्रमेय से कम है अभाज्य संख्या फ़ंक्शन n/log(n)) उनमें से पर्याप्त हैं कि फ़र्मेट का प्राइमलिटी परीक्षण प्रायः उपरोक्त रूप में उपयोग नहीं किया जाता है। इसके अतिरिक्त ,फ़र्मेट परीक्षण के अन्य अधिक सशक्त एक्सटेंशन, जैसे कि बैली-पीएसडब्ल्यू, मिलर-राबिन और सोलोवे-स्ट्रैसन का अधिक सामान्यतः उपयोग किया जाता है।

सामान्य रूप से, यदि $n$ भाज्य संख्या है जो कारमाइकल संख्या नहीं है, तो सभी का कम से कम आधी संख्या होगी

a\in (\mathbb {Z} /n\mathbb {Z} )^{*}

(अर्थात।

\operatorname {gcd} (a,n)=1

)

फ़र्मेट प्रमाणितकर्ता हैं। इसके प्रमाण के लिए, मान लीजिए कि $a$ एक फ़र्मेट प्रमाणितकर्ता है और $a_{1}$ , $a_{2}$ , ..., $a_{s}$ फ़र्मेट मिथ्याभाषी है। तब

(a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}

और सब कुछ $a\cdot a_{i}$ के लिए $i=1,2,...,s$ फ़र्मेट प्रमाणितकर्ता हैं।

अनुप्रयोग

जैसा कि ऊपर दर्शाया गया है, की अधिकांश एप्लिकेशन मिलर-राबिन प्राइमलिटी परीक्षण मिलर-राबिन या बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण का उपयोग प्राइमलिटी के लिए करते हैं। कभी-कभी प्रदर्शन में सुधार के लिए पहले फ़र्मेट परीक्षण (छोटे अभाज्यों द्वारा कुछ परीक्षण विभाजन के साथ) किया जाता है। संस्करण 3.0 के पश्चात से जीएनयू मल्टीपल प्रिसिजन अरिथमेटिक लाइब्रेरी ट्रायल डिवीजन के पश्चात् और मिलर-राबिन परीक्षण चलाने से प्रथम बेस-210 फ़र्मेट परीक्षण का उपयोग करती है। इस प्रकार से लिबगक्रिप्ट फ़र्मेट परीक्षण के लिए आधार 2 के साथ समान प्रक्रिया का उपयोग करता है, किन्तु ओपनएसएसएल नहीं करता है।

अधिकांश उच्च संख्या में लाइब्रेरी जैसे कि जीएमपी के साथ वास्तविक में, फ़र्मेट परीक्षण मिलर-राबिन परीक्षण की तुलना में अधिक तीव्र नहीं है, और कई इनपुट के लिए धीमा हो सकता है।^[4]

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

संदर्भ

↑ ^1.0 ^1.1 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (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)

[PSW-1] 1.0 ^1.1 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.

[Alford1994-2] Alford, W. R.; Granville, Andrew; Pomerance, Carl (1994). "कारमाइकल संख्याएँ अनन्त रूप से अनेक हैं" (PDF). Annals of Mathematics. 140 (3): 703–722. doi:10.2307/2118576. JSTOR 2118576.

[3] Paul Erdős (1956). "On pseudoprimes and Carmichael numbers". Publ. Math. Debrecen. 4: 201–206.

[4] Joe Hurd (2003), Verification of the Miller–Rabin Probabilistic Primality Test, p. 2, CiteSeerX 10.1.1.105.3196

[1]

[2]

[3]

[4]

@@ 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'' संभावित अभाज्य है।
-चूंकि, ध्यान दें कि उपरोक्त सर्वांगसमता <math>a \equiv 1 \pmod{p}</math> के लिए नगण्य  रूप से मान्य है क्योंकि सर्वांगसम संबंध घातांक के साथ संगत है। यदि p विषम है, तो इसी कारण से, यह <math>a \equiv -1 \pmod{p}</math> के लिए भी नगण्य  रूप से मान्य है। यही कारण है कि कोई प्रायः  अंतराल <math>1 < a < p - 1</math> में
+चूंकि, ध्यान दें कि उपरोक्त सर्वांगसमता <math>a \equiv 1 \pmod{p}</math> के लिए नगण्य रूप से मान्य है क्योंकि सर्वांगसम संबंध घातांक के साथ संगत है। यदि p विषम है, तो इसी कारण से, यह <math>a \equiv -1 \pmod{p}</math> के लिए भी नगण्य रूप से मान्य है। यही कारण है कि कोई प्रायः अंतराल <math>1 < a < p - 1</math> में
 अतः कोई भी यादृच्छिक a चुनता है
 :<math>a^{n-1} \equiv 1 \pmod{n}</math>
-जब n मिश्रित होता है तो उसे फ़र्मेट लियार के रूप में जाना जाता है। इस स्तिथि  में n को आधार a के लिए [[फ़र्मेट स्यूडोप्राइम]] कहा जाता है।
+जब n मिश्रित होता है तो उसे फ़र्मेट लियार के रूप में जाना जाता है। इस स्तिथि में n को आधार a के लिए [[फ़र्मेट स्यूडोप्राइम]] कहा जाता है।
 यदि हम ऐसा कोई चुनते हैं
@@ Line 22: / Line 22: @@
 मान लीजिए हम यह निर्धारित करना चाहते हैं कि ''n = 221'' अभाज्य है या नहीं। यादृच्छिक रूप से 1 < ''a'' < 220, मान लीजिए ''a = 38'' चुनें। हम उपरोक्त समानता की जाँच करते हैं और प्राप्त करते हैं किन्तु यह बनाये रखता है:
 :<math>a^{n-1} = 38^{220} \equiv 1 \pmod{221}.</math>
-या तो 221 अभाज्य है, या 38 फ़र्मेट  मिथ्याभाषी है, इसलिए हम एक ओर a रखते हैं, मान लीजिए 24:
+या तो 221 अभाज्य है, या 38 फ़र्मेट मिथ्याभाषी है, इसलिए हम एक ओर a रखते हैं, मान लीजिए 24:
 :<math>a^{n-1} = 24^{220} \equiv 81 \not\equiv 1 \pmod{221}.</math>
-तो 221 समग्र है और 38 वास्तव में फ़र्मेट  मिथ्याभाषी था। इसके अतिरिक्त , 24 221 की समग्रता के लिए फ़र्मेट  प्रमाणितकर्ता है।
+तो 221 समग्र है और 38 वास्तव में फ़र्मेट मिथ्याभाषी था। इसके अतिरिक्त , 24 221 की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता है।
 ==एल्गोरिदम==
 एल्गोरिथ्म को इस प्रकार लिखा जा सकता है:
-:इनपुट: ''n'': प्रारंभिकता के परीक्षण के लिए मान, ''n''>3; ''k'':  पैरामीटर जो प्रारंभिकता के परीक्षण के लिए समय की संख्या निर्धारित करता है
+:इनपुट: ''n'': प्रारंभिकता के परीक्षण के लिए मान, ''n''>3; ''k'': पैरामीटर जो प्रारंभिकता के परीक्षण के लिए समय की संख्या निर्धारित करता है
-:आउटपुट: ''मिश्रित''  यदि ''n'' समग्र है, अन्यथा ''संभवतः अभाज्य है तब''
+:आउटपुट: ''मिश्रित'' यदि ''n'' समग्र है, अन्यथा ''संभवतः अभाज्य है तब''
 :''k'' बार दोहराएं:
 ::[2, एन - 2] की श्रेणी में यादृच्छिक रूप से चुनें
-::यदि  <math>a^{n-1}\not\equiv1 \pmod n</math>, संभवत: प्रमुख लौटाएं
+::यदि <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''&nbsp;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''&nbsp;log<sup>2</sup>''n'')}} है , जहां k वह संख्या है जितनी बार हम यादृच्छिक a का परीक्षण करते हैं, और n वह मान है जिसे हम प्रारंभिकता के लिए परीक्षण करना चाहते हैं; विवरण के लिए मिलर-राबिन प्राइमलिटी परीक्षण समष्टि मिलर-राबिन प्राइमलिटी परीक्षण देखें।
 ==दोष==
 किसी भी आधार 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> हैं  जिसके लिए <u>सभी</u> मान <math>a</math> साथ <math>\operatorname{gcd}(a, n) = 1</math> फ़र्मेट  मिथ्याभाषी हैं. इन संख्याओं के लिए, फ़र्मेट प्राइमैलिटी परीक्षण का बार-बार उपयोग कारकों के लिए सरल यादृच्छिक खोज के समान ही कार्य करता है। जबकि [[कारमाइकल संख्या|कारमाइकल संख्याएँ]] अभाज्य संख्याओं की तुलना में अधिक दुर्लभ हैं (कारमाइकल संख्याओं की संख्या के लिए एर्डोज़ की ऊपरी श्रेणी <ref>
+इससे भी दोष पूर्ण तथ्य यह है कि [[कारमाइकल संख्या|फ़र्मेट स्यूडोप्राइम्स]] अनंत हैं।<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
   |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> भाज्य संख्या है जो कारमाइकल संख्या नहीं है, तो सभी का कम से कम आधी संख्या होगी
@@ 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</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>
+अधिकांश उच्च संख्या में लाइब्रेरी जैसे कि जीएमपी के साथ वास्तविक में, फ़र्मेट परीक्षण मिलर-राबिन परीक्षण की तुलना में अधिक तीव्र नहीं है, और कई इनपुट के लिए धीमा हो सकता है।<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>
-इस प्रकार से अपवाद के रूप में, ओपनपीएफजीडब्ल्यू संभावित प्राइम परीक्षण के लिए केवल फ़र्मेट परीक्षण का उपयोग करता है। प्रोग्राम का उपयोग सामान्यतः अधिक उच्च इनपुट के साथ अधिकतम गति के लक्ष्य के साथ बहु-हज़ार अंकों वाले इनपुट के साथ किया जाता है। अतः अन्य प्रसिद्ध प्रोग्राम  जो केवल फ़र्मेट परीक्षण पर निर्भर करता है वह [[काफ़ी अच्छी गोपनीयता|पीजीपी]] है जहां इसका उपयोग केवल स्व-निर्मित बड़े यादृच्छिक मानों के परीक्षण के लिए किया जाता है (ओपन सोर्स समकक्ष, [[जीएनयू गोपनीयता गार्ड|जीएनयू प्राइवेसी गार्ड]], मिलर-राबिन परीक्षणों के पश्चात फ़र्मेट प्रीपरीक्षण का उपयोग करता है)।
+इस प्रकार से अपवाद के रूप में, ओपनपीएफजीडब्ल्यू संभावित प्राइम परीक्षण के लिए केवल फ़र्मेट परीक्षण का उपयोग करता है। प्रोग्राम का उपयोग सामान्यतः अधिक उच्च इनपुट के साथ अधिकतम गति के लक्ष्य के साथ बहु-हज़ार अंकों वाले इनपुट के साथ किया जाता है। अतः अन्य प्रसिद्ध प्रोग्राम जो केवल फ़र्मेट परीक्षण पर निर्भर करता है वह [[काफ़ी अच्छी गोपनीयता|पीजीपी]] है जहां इसका उपयोग केवल स्व-निर्मित बड़े यादृच्छिक मानों के परीक्षण के लिए किया जाता है (ओपन सोर्स समकक्ष, [[जीएनयू गोपनीयता गार्ड|जीएनयू प्राइवेसी गार्ड]], मिलर-राबिन परीक्षणों के पश्चात फ़र्मेट प्रीपरीक्षण का उपयोग करता है)।
 ==संदर्भ==

v t e Pierre de Fermat
Work	Fermat's Last Theorem Fermat number Fermat's principle Fermat's little theorem Fermat polygonal number theorem Fermat pseudoprime Fermat point Fermat's theorem (stationary points) Fermat's theorem on sums of two squares Fermat's spiral Fermat's right triangle theorem
Related	List of things named after Pierre de Fermat Wiles's proof of Fermat's Last Theorem Fermat's Last Theorem in fiction Fermat Prize Fermat's Last Tango (2000 musical) Fermat's Last Theorem (popular science book)

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है

Anonymous

Search

फ़र्मेट प्राइमैलिटी परीक्षण: Difference between revisions

Namespaces

More

Page actions

Revision as of 09:48, 22 July 2023

Contents

अवधारणा

उदाहरण

एल्गोरिदम

समष्टि

दोष

अनुप्रयोग

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

फ़र्मेट प्राइमैलिटी परीक्षण: Difference between revisions

Revision as of 09:48, 22 July 2023

अवधारणा

उदाहरण

एल्गोरिदम

समष्टि

दोष

अनुप्रयोग

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories