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

For यह निर्धारित करने के लिए परीक्षण कि कोई फ़र्मेट संख्या अभाज्य है या नहीं, see पेपिन परीक्षण.

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

अवधारणा

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

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

यदि कोई यह परीक्षण करना चाहता है कि क्या p अभाज्य है, तो हम ऐसे यादृच्छिक पूर्णांक चुन सकते हैं जो की p से विभाज्य नहीं हैं और देख सकते हैं कि समानता धारण करता है या नहीं। यदि समानता a के मान के लिए मान्य नहीं है, तो p समग्र है। यदि p समग्र है तो यह सर्वांगसमता यादृच्छिक a के लिए रुकने की संभावना नहीं है। इसलिए, यदि समानता 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²n log log n) = Õ(k log²n) है , जहां k वह संख्या है जितनी बार हम यादृच्छिक a का परीक्षण करते हैं, और n वह मान है जिसे हम प्रारंभिकता के लिए परीक्षण करना चाहते हैं; विवरण के लिए मिलर-राबिन प्राइमलिटी परीक्षण समष्टि मिलर-राबिन प्राइमलिटी परीक्षण देखें।

दोष

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

इससे भी दोष पूर्ण तथ्य यह है कि फ़र्मेट स्यूडोप्राइम्स अनंत हैं। ये संख्याएं $n$ हैं जिसके लिए सभी मान $a$ साथ $\operatorname {gcd} (a,n)=1$ फ़र्मेट मिथ्याभाषी हैं. इन संख्याओं के लिए, फ़र्मेट प्राइमैलिटी परीक्षण का बार-बार उपयोग कारकों के लिए सरल यादृच्छिक खोज के समान ही कार्य करता है। जबकि कारमाइकल संख्याएँ अभाज्य संख्याओं की तुलना में अधिक दुर्लभ हैं (कारमाइकल संख्याओं की संख्या के लिए एर्डोज़ की ऊपरी श्रेणी अभाज्य संख्या प्रमेय से कम है अभाज्य संख्या फ़ंक्शन 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 के साथ समान प्रक्रिया का उपयोग करता है, किन्तु ओपनएसएसएल नहीं करता है।

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

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

संदर्भ

• 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)