लुकास प्राइमैलिटी टेस्ट

For the test for Mersenne numbers, see Lucas–Lehmer primality test. For the Lucas–Lehmer–Riesel test, see Lucas–Lehmer–Riesel test. For the Lucas probable prime test, see Lucas pseudoprime.

कम्प्यूटेशनल संख्या सिद्धांत में, लुकास परीक्षण एक प्राकृतिक संख्या एन के लिए एक प्रारंभिक परीक्षण है; इसके लिए आवश्यक है कि n - 1 के अभाज्य गुणनखंड पहले से ही ज्ञात हों। यह प्रैट प्रमाणपत्र का आधार है जो संक्षिप्त सत्यापन देता है कि n अभाज्य है।

अवधारणाएँ

माना कि एन एक धनात्मक पूर्ण संख्या है। यदि कोई पूर्णांक a, 1<a<n मौजूद है, तो ऐसा है

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

और n - 1 के प्रत्येक अभाज्य गुणनखंड q के लिए

$a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}\,$

तब n अभाज्य है. यदि ऐसी कोई संख्या मौजूद नहीं है, तो n या तो 1, 2 या भाज्य संख्या है।

इस दावे की सत्यता का कारण इस प्रकार है: यदि पहली समतुल्यता a के लिए है, तो हम यह निष्कर्ष निकाल सकते हैं कि a और n सहअभाज्य#गुण हैं। यदि a भी दूसरे चरण में जीवित रहता है, तो समूह (गणित) ('Z'/n'Z')* में a का क्रम (समूह सिद्धांत) n−1 के बराबर है, जिसका अर्थ है कि उस समूह का क्रम है n−1 (क्योंकि समूह के प्रत्येक तत्व का क्रम समूह के क्रम को विभाजित करता है), जिसका अर्थ है कि n अभाज्य संख्या है। इसके विपरीत, यदि n अभाज्य है, तो एक आदिम रूट मोडुलो n मौजूद है, या समूह के समूह ('Z'/n'Z')* का जनरेटिंग सेट मौजूद है। ऐसे जनरेटर का क्रम होता है |('Z'/n'Z')*| = n−1 और दोनों समतुल्यताएं ऐसे किसी भी आदिम मूल के लिए मान्य होंगी।

ध्यान दें कि यदि कोई a < n मौजूद है, जिससे कि पहली समतुल्यता विफल हो जाती है, तो n की समग्रता के लिए a को फ़र्मेट प्राइमैलिटी टेस्ट#कॉन्सेप्ट कहा जाता है।

उदाहरण

उदाहरण के लिए, n = 71 लें। फिर n - 1 = 70 और 70 के अभाज्य गुणनखंड 2, 5 और 7 हैं। हम यादृच्छिक रूप से a=17 <n का चयन करते हैं। अब हम गणना करते हैं:

$17^{70}\ \equiv \ 1{\pmod {71}}.$

सभी पूर्णांकों के लिए यह ज्ञात है कि

$a^{n-1}\equiv 1{\pmod {n}}\ {\text{ if and only if }}{\text{ ord}}(a)|(n-1).$

इसलिए, 17 (मॉड 71) का गुणन क्रम आवश्यक रूप से 70 नहीं है क्योंकि 70 का कुछ कारक ऊपर भी काम कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:

$17^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}$

$17^{14}\ \equiv \ 25\ \not \equiv \ 1{\pmod {71}}$

$17^{10}\ \equiv \ 1\ \equiv \ 1{\pmod {71}}.$

दुर्भाग्य से, हमें वह 17 मिलता है¹⁰≡1 (मॉड 71)। इसलिए हम अभी भी नहीं जानते कि 71 अभाज्य है या नहीं।

हम एक और यादृच्छिक a आज़माते हैं, इस बार a = 11 चुनते हैं। अब हम गणना करते हैं:

$11^{70}\ \equiv \ 1{\pmod {71}}.$

फिर, इससे यह नहीं पता चलता कि 11 (मॉड 71) का गुणन क्रम 70 है क्योंकि 70 का कुछ गुणनखंड भी काम कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:

$11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}$

$11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}$

$11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}.$

तो 11 (मॉड 71) का गुणन क्रम 70 है, और इस प्रकार 71 अभाज्य है।

(इन मॉड्यूलर घातांक को पूरा करने के लिए, कोई तेज़ घातांक एल्गोरिथ्म का उपयोग कर सकता है जैसे कि वर्ग द्वारा घातांक या जोड़-श्रृंखला घातांक)।

एल्गोरिदम

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

एल्गोरिथम lucas_primality_test है
    इनपुट: n > 2, प्रारंभिकता के लिए परीक्षण किया जाने वाला एक विषम पूर्णांक।
           k, एक पैरामीटर जो परीक्षण की सटीकता निर्धारित करता है।
    आउटपुट: प्राइम यदि एन प्राइम है, अन्यथा मिश्रित या संभवतः मिश्रित।

    n-1 के अभाज्य गुणनखंड निर्धारित करें।

    LOOP1: k बार दोहराएँ:
        [2, एन - 1] की सीमा में ए को बेतरतीब ढंग से चुनें             

if $a^{n-1}\not \equiv 1{\pmod {n}}$ then

                समग्र लौटें
            अन्य # $\color {Gray}{a^{n-1}\equiv 1{\pmod {n}}}$
                LOOP2: n-1 के सभी अभाज्य गुणनखंड q के लिए:                     

if $a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$ then

                        यदि हमने n-1 के सभी अभाज्य गुणनखंडों के लिए इस समानता की जाँच की
                            प्राइम लौटाएं
                        अन्य
                            LOOP2 जारी रखें
                    अन्य # $\color {Gray}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}$
                        LOOP1 जारी रखें

    संभवतः मिश्रित लौटें।

यह भी देखें

• एडौर्ड लुकास, जिनके नाम पर इस परीक्षण का नाम रखा गया है
• फ़र्मेट का छोटा प्रमेय

पॉकलिंगटन प्राइमैलिटी टेस्ट परीक्षण, इस परीक्षण का एक उन्नत संस्करण जिसमें केवल n − 1 के आंशिक गुणनखंडन की आवश्यकता होती है

• प्राथमिकता प्रमाण पत्र

टिप्पणियाँ

[Category:Primality tes