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

Latest revision as of 12:22, 31 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 1: / Line 1: @@
-{{for|the test for determining whether a Fermat number is prime|Pépin's test}}
+{{for|यह निर्धारित करने के लिए परीक्षण कि कोई फ़र्मेट संख्या अभाज्य है या नहीं|पेपिन परीक्षण}}
-फ़र्मेट प्राइमैलिटी परीक्षण यह निर्धारित करने के लिए एक [[यादृच्छिक एल्गोरिदम]] परीक्षण है कि कोई संख्या संभावित अभाज्य है या नहीं।
+'''फ़र्मेट प्राइमैलिटी परीक्षण''' यह निर्धारित करने के लिए [[यादृच्छिक एल्गोरिदम]] परीक्षण है कि कोई संख्या संभावित अभाज्य है या नहीं है।
 ==अवधारणा==
-फ़र्मेट का छोटा प्रमेय बताता है कि यदि p अभाज्य है और a, p से विभाज्य नहीं है, तो
+फ़र्मेट का छोटा प्रमेय यह दर्शाता है कि यदि p अभाज्य है और a, p से विभाज्य नहीं है, तो
 :<math>a^{p-1} \equiv 1 \pmod{p}.</math>
-यदि कोई यह परीक्षण करना चाहता है कि क्या पी अभाज्य है, तो हम ऐसे यादृच्छिक पूर्णांक चुन सकते हैं जो पी से विभाज्य नहीं हैं और देख सकते हैं कि समानता कायम है या नहीं। यदि समानता 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>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 के लिए [[फ़र्मेट स्यूडोप्राइम]] कहा जाता है।
 यदि हम ऐसा कोई चुनते हैं
-:<math>a^{n-1} \not\equiv 1 \pmod{n}</math>
+:<math>a^{n-1} \not\equiv 1 \pmod{n}                                                                                                                                                                            </math>
-तब a को n की समग्रता के लिए फ़र्मेट गवाह के रूप में जाना जाता है।
+तब a को n की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता के रूप में जाना जाता है।
 == उदाहरण ==
-मान लीजिए हम यह निर्धारित करना चाहते हैं कि 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>
-या तो 221 अभाज्य है, या 38 एक फ़र्मेट झूठा है, इसलिए हम एक और लेते हैं, मान लीजिए 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 की समग्रता के लिए फ़र्मेट प्रमाणितकर्ता है।
 ==एल्गोरिदम==
 एल्गोरिथ्म को इस प्रकार लिखा जा सकता है:
-:इनपुट: ''एन'': प्रारंभिकता के परीक्षण के लिए एक मान, ''एन''>3; ''k'': एक पैरामीटर जो प्रारंभिकता के परीक्षण के लिए समय की संख्या निर्धारित करता है
+:इनपुट: ''n'': प्रारंभिकता के परीक्षण के लिए मान, ''n''>3; ''k'': पैरामीटर जो प्रारंभिकता के परीक्षण के लिए समय की संख्या निर्धारित करता है
-:आउटपुट: ''मिश्रित'' यदि ''एन'' समग्र है, अन्यथा ''संभवतः अभाज्य''
+:आउटपुट: ''मिश्रित'' यदि ''n'' समग्र है, अन्यथा ''संभवतः अभाज्य है तब''
 :''k'' बार दोहराएं:
-::श्रेणी में यादृच्छिक रूप से ''a'' चुनें [2, ''n'' − 2]
+::[2, एन - 2] की श्रेणी में यादृच्छिक रूप से चुनें
-::अगर <math>a^{n-1}\not\equiv1 \pmod n</math>, फिर समग्र लौटें
+::यदि <math>a^{n-1}\not\equiv1 \pmod n</math>, संभवत: प्रमुख लौटाएं
-:यदि कंपोजिट कभी वापस नहीं किया जाता है: संभवतः प्राइम लौटाएं
+:यदि कंपोजिट कभी वापस नहीं किया जाता है: संभवतः प्रमुख लौटाएं
-ए मान 1 और एन-1 का उपयोग नहीं किया जाता है क्योंकि समानता क्रमशः सभी एन और सभी विषम एन के लिए होती है, इसलिए उनका परीक्षण करने से कोई मूल्य नहीं जुड़ता है।
+''a'' मान 1 और ''n''-1 का उपयोग नहीं किया जाता है क्योंकि समानता क्रमशः सभी ''n'' और सभी विषम ''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 वह मान है जिसे हम प्रारंभिकता के लिए परीक्षण करना चाहते हैं; विवरण के लिए मिलर-राबिन प्राइमलिटी टेस्ट#जटिलता|मिलर-राबिन प्राइमलिटी टेस्ट देखें।
+इस प्रकार से [[मॉड्यूलर घातांक]] और बहुपरिशुद्धता गुणन के लिए तीव्र एल्गोरिदम का उपयोग करते हुए, इस एल्गोरिदम का चलने का समय {{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}}
+किसी भी आधार 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){{cn|reason=Erdös' paper makes no comparison to the prime number function AFAICS, and depending on value of the constant c_5 in his formula (6), his function can be smaller or bigger than x/log(x)|date=November 2021}}) उनमें से पर्याप्त हैं कि फ़र्मेट का प्राइमलिटी परीक्षण अक्सर उपरोक्त रूप में उपयोग नहीं किया जाता है। इसके बजाय, फ़र्मेट परीक्षण के अन्य अधिक शक्तिशाली एक्सटेंशन, जैसे बैली-पीएसडब्ल्यू प्राइमलिटी टेस्ट|बैली-पीएसडब्ल्यू, मिलर-राबिन प्राइमलिटी टेस्ट|मिलर-राबिन, और सोलोवे-स्ट्रैसेन प्राइमलिटी टेस्ट|सोलोवे-स्ट्रैसन का अधिक सामान्यतः उपयोग किया जाता है।
+  |journal=Publ. Math. Debrecen |volume=4 |pages=201–206|author-link=Paul Erdős }}</ref> अभाज्य संख्या प्रमेय से कम है अभाज्य संख्या फ़ंक्शन n/log(n)) उनमें से पर्याप्त हैं कि फ़र्मेट का प्राइमलिटी परीक्षण प्रायः उपरोक्त रूप में उपयोग नहीं किया जाता है। इसके अतिरिक्त ,फ़र्मेट परीक्षण के अन्य अधिक सशक्त एक्सटेंशन, जैसे कि बैली-पीएसडब्ल्यू, मिलर-राबिन और सोलोवे-स्ट्रैसन का अधिक सामान्यतः उपयोग किया जाता है।
-सामान्य तौर पर, यदि <math>n</math> एक भाज्य संख्या है जो कारमाइकल संख्या नहीं है, तो सभी का कम से कम आधा
+सामान्य रूप से, यदि <math>n</math> भाज्य संख्या है जो कारमाइकल संख्या नहीं है, तो सभी का कम से कम आधी संख्या होगी
 :<math>a\in(\mathbb{Z}/n\mathbb{Z})^*</math> (अर्थात। <math>\operatorname{gcd}(a,n)=1</math>)
-फ़र्मेट गवाह हैं। इसके प्रमाण के लिए आइए <math>a</math> एक फ़र्मेट गवाह बनें और <math>a_1</math>, <math>a_2</math>, ..., <math>a_s</math> फ़र्मेट झूठे हो. तब
+फ़र्मेट प्रमाणितकर्ता हैं। इसके प्रमाण के लिए, मान लीजिए कि <math>a</math> एक फ़र्मेट प्रमाणितकर्ता है और <math>a_1</math>, <math>a_2</math>, ..., <math>a_s</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>
+अधिकांश उच्च संख्या में लाइब्रेरी जैसे कि जीएमपी के साथ वास्तविक में, फ़र्मेट परीक्षण मिलर-राबिन परीक्षण की तुलना में अधिक तीव्र नहीं है, और कई इनपुट के लिए धीमा हो सकता है।<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>
-अपवाद के रूप में, OpenPFGW संभावित प्राइम परीक्षण के लिए केवल फ़र्मेट परीक्षण का उपयोग करता है। प्रोग्राम का उपयोग आम तौर पर बहुत बड़े इनपुट के साथ अधिकतम गति के लक्ष्य के साथ बहु-हज़ार अंकों वाले इनपुट के साथ किया जाता है। एक अन्य प्रसिद्ध कार्यक्रम जो केवल फ़र्मेट परीक्षण पर निर्भर करता है वह [[काफ़ी अच्छी गोपनीयता]] है जहां इसका उपयोग केवल स्व-निर्मित बड़े यादृच्छिक मूल्यों के परीक्षण के लिए किया जाता है (एक खुला स्रोत समकक्ष, [[जीएनयू गोपनीयता गार्ड]], मिलर-राबिन परीक्षणों के बाद फ़र्मेट प्रीटेस्ट का उपयोग करता है) .
+इस प्रकार से अपवाद के रूप में, ओपनपीएफजीडब्ल्यू संभावित प्राइम परीक्षण के लिए केवल फ़र्मेट परीक्षण का उपयोग करता है। प्रोग्राम का उपयोग सामान्यतः अधिक उच्च इनपुट के साथ अधिकतम गति के लक्ष्य के साथ बहु-हज़ार अंकों वाले इनपुट के साथ किया जाता है। अतः अन्य प्रसिद्ध प्रोग्राम जो केवल फ़र्मेट परीक्षण पर निर्भर करता है वह [[काफ़ी अच्छी गोपनीयता|पीजीपी]] है जहां इसका उपयोग केवल स्व-निर्मित बड़े यादृच्छिक मानों के परीक्षण के लिए किया जाता है (ओपन सोर्स समकक्ष, [[जीएनयू गोपनीयता गार्ड|जीएनयू प्राइवेसी गार्ड]], मिलर-राबिन परीक्षणों के पश्चात फ़र्मेट प्रीपरीक्षण का उपयोग करता है)।
 ==संदर्भ==
@@ Line 68: / Line 71: @@
-{{Pierre de Fermat}}
 {{number theoretic algorithms}}
-[[Category: आदिमता परीक्षण]] [[Category: मॉड्यूलर अंकगणित]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 maint]]
+[[Category:Collapse templates]]
 [[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:मॉड्यूलर अंकगणित]]

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

Latest revision as of 12:22, 31 July 2023

Contents

अवधारणा

उदाहरण

एल्गोरिदम

समष्टि

दोष

अनुप्रयोग

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 12:22, 31 July 2023

अवधारणा

उदाहरण

एल्गोरिदम

समष्टि

दोष

अनुप्रयोग

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories