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

For the test for determining whether a Fermat number is prime, see Pépin's test.

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

अवधारणा

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

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

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

हालाँकि, ध्यान दें कि उपरोक्त सर्वांगसमता तुच्छ है $a\equiv 1{\pmod {p}}$, क्योंकि सर्वांगसमता संबंध मॉड्यूलर अंकगणित#गुण है। यह भी तुच्छ रूप से मान्य है $a\equiv -1{\pmod {p}}$ यदि p विषम है, तो उसी कारण से। यही कारण है कि कोई आमतौर पर अंतराल में एक यादृच्छिक ए चुनता है $1<a<p-1$.

कोई भी ऐसा कि

$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 एक फ़र्मेट झूठा है, इसलिए हम एक और लेते हैं, मान लीजिए 24:

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

तो 221 समग्र है और 38 वास्तव में एक फ़र्मेट झूठा था। इसके अलावा, 24 221 की समग्रता के लिए एक फ़र्मेट गवाह है।

एल्गोरिदम

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

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

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

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

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

अगर $a^{n-1}\not \equiv 1{\pmod {n}}$, फिर समग्र लौटें

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

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

जटिलता

मॉड्यूलर घातांक और बहुसटीक गुणन के लिए तेज़ एल्गोरिदम का उपयोग करते हुए, इस एल्गोरिदम का चलने का समय है 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 के साथ एक समान प्रक्रिया का उपयोग करता है, लेकिन ओपनएसएसएल नहीं करता है।

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

संदर्भ

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