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

For मेर्सन संख्याओं के लिए परीक्षण, see लुकास-लेहमर प्राइमैलिटी परीक्षण. For लुकास-लेहमर-रिसेल परीक्षण, see लुकास-लेहमर-रिसेल परीक्षण. For लुकास संभावित अभाज्य परीक्षण, see लुकास स्यूडोप्राइम.

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

अवधारणाएँ

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

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

और n- 1

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

के प्रत्येक अभाज्य कारक q के लिए तो 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 अभाज्य है।

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

एल्गोरिदम

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

algorithm lucas_primality_test is
    input: n > 2, an odd integer to be tested for primality.
           k, a parameter that determines the accuracy of the test.
    output: prime if n is prime, otherwise composite or possibly composite.

    determine the prime factors of n−1.

    LOOP1: repeat k times:
        pick a randomly in the range [2, n − 1]
            if  then
                return composite
            else # 
                LOOP2: for all prime factors q of n−1:
                    if  then
                        if we checked this equality for all prime factors of n−1 then
                            return prime
                        else
                            continue LOOP2
                    else # 

                        continue LOOP1

    return possibly composite.

यह भी देखें

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

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

टिप्पणियाँ

[Category:Primality test