लुकास प्राइमैलिटी टेस्ट: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{for multi|the test for Mersenne numbers|Lucas–Lehmer primality test|the Lucas–Lehmer–Riesel test|Lucas–Lehmer–Riesel test|the Lucas probable prime test|Lucas pseudoprime}}
{{for multi|मेर्सन संख्याओं के लिए परीक्षण|लुकास-लेहमर प्राइमैलिटी परीक्षण|लुकास-लेहमर-रिसेल परीक्षण|लुकास-लेहमर-रिसेल परीक्षण|लुकास संभावित अभाज्य परीक्षण|लुकास स्यूडोप्राइम}}


[[कम्प्यूटेशनल संख्या सिद्धांत]] में, लुकास परीक्षण एक प्राकृतिक संख्या ''एन'' के लिए एक [[प्रारंभिक परीक्षण]] है; इसके लिए आवश्यक है कि ''n'' - 1 के अभाज्य गुणनखंड पहले से ही ज्ञात हों।<ref>{{cite book |last1=Crandall |first1=Richard |last2=Pomerance |first2=Carl
[[कम्प्यूटेशनल संख्या सिद्धांत]] में, लुकास परीक्षण एक प्राकृतिक संख्या ''n'' के लिए एक [[प्रारंभिक परीक्षण]] है; इसके लिए आवश्यक है कि ''n''-1 के अभाज्य गुणनखंड पहले से ही ज्ञात हों।<ref>{{cite book |last1=Crandall |first1=Richard |last2=Pomerance |first2=Carl
  |title=Prime Numbers: a Computational Perspective
  |title=Prime Numbers: a Computational Perspective
|year=2005|publisher=Springer|isbn=0-387-25282-7 |page=173 |edition=2nd }}</ref><ref>{{cite book |last1=Křížek |first1=Michal |last2=Luca |first2=Florian |last3=Somer |first3=Lawrence |title=17 Lectures on Fermat Numbers: From Number Theory to Geometry  |series=CMS Books in Mathematics |volume= 9|year=2001|publisher=Canadian Mathematical Society/Springer|isbn=0-387-95332-9 |page=41}}</ref> यह [[प्रैट प्रमाणपत्र]] का आधार है जो संक्षिप्त सत्यापन देता है कि n अभाज्य है।
|year=2005|publisher=Springer|isbn=0-387-25282-7 |page=173 |edition=2nd }}</ref><ref>{{cite book |last1=Křížek |first1=Michal |last2=Luca |first2=Florian |last3=Somer |first3=Lawrence |title=17 Lectures on Fermat Numbers: From Number Theory to Geometry  |series=CMS Books in Mathematics |volume= 9|year=2001|publisher=Canadian Mathematical Society/Springer|isbn=0-387-95332-9 |page=41}}</ref> यह [[प्रैट प्रमाणपत्र]] का आधार है जो संक्षिप्त सत्यापन देता है कि n अभाज्य है।


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


:<math>a^{n-1}\ \equiv\ 1 \pmod n \, </math>
:<math>a^{n-1}\ \equiv\ 1 \pmod n \, </math>
और n - 1 के प्रत्येक अभाज्य गुणनखंड q के लिए
और n- 1  


:<math>a^{({n-1})/q}\ \not\equiv\ 1 \pmod n \, </math>
:<math>a^{({n-1})/q}\ \not\equiv\ 1 \pmod n \, </math>
तब n अभाज्य है. यदि ऐसी कोई संख्या मौजूद नहीं है, तो n या तो 1, 2 या भाज्य संख्या है।
के प्रत्येक अभाज्य कारक 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 के लिए है, तो हम यह निष्कर्ष निकाल सकते हैं कि 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 को फ़र्मेट प्राइमैलिटी टेस्ट#कॉन्सेप्ट कहा जाता है।
ध्यान दें कि यदि कोई a < n स्थित है, जिससे कि प्रथम समतुल्यता विफल हो जाती है, तो n की समग्रता के लिए a को फ़र्मेट प्राइमैलिटी परीक्षण अवधारणा कहा जाता है।


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


:<math>17^{70}\ \equiv\ 1 \pmod {71}.</math>
:<math>17^{70}\ \equiv\ 1 \pmod {71}.</math>
Line 26: Line 25:


:<math>a^{n - 1}\equiv 1 \pmod{n}\ \text{  if and only if } \text{ ord}(a)|(n-1).</math>
:<math>a^{n - 1}\equiv 1 \pmod{n}\ \text{  if and only if } \text{ ord}(a)|(n-1).</math>
इसलिए, 17 (मॉड 71) का गुणन क्रम आवश्यक रूप से 70 नहीं है क्योंकि 70 का कुछ कारक ऊपर भी काम कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:
इसलिए, 17 (मॉड 71) का गुणन क्रम आवश्यक रूप से 70 नहीं है क्योंकि 70 का कुछ कारक ऊपर भी कार्य कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:


:<math>17^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>
:<math>17^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>
:<math>17^{14}\ \equiv\ 25\ \not\equiv\ 1 \pmod {71}</math>
:<math>17^{14}\ \equiv\ 25\ \not\equiv\ 1 \pmod {71}</math>
:<math>17^{10}\ \equiv\ 1\ \equiv\ 1 \pmod {71}.</math>
:<math>17^{10}\ \equiv\ 1\ \equiv\ 1 \pmod {71}.</math>
दुर्भाग्य से, हमें वह 17 मिलता है<sup>10</sup>≡1 (मॉड 71)। इसलिए हम अभी भी नहीं जानते कि 71 अभाज्य है या नहीं।
दुर्भाग्य से, हमें वह 17<sup>10</sup>≡1 (मॉड 71) मिलता है। इसलिए हम अभी भी नहीं जानते कि 71 अभाज्य है या नहीं।


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


:<math>11^{70}\ \equiv\ 1 \pmod {71}.</math>
:<math>11^{70}\ \equiv\ 1 \pmod {71}.</math>
फिर, इससे यह नहीं पता चलता कि 11 (मॉड 71) का गुणन क्रम 70 है क्योंकि 70 का कुछ गुणनखंड भी काम कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:
फिर, इससे यह नहीं पता चलता कि 11 (मॉड 71) का गुणन क्रम 70 है क्योंकि 70 का कुछ गुणनखंड भी कार्य कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:


:<math>11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>
:<math>11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>
Line 43: Line 42:
तो 11 (मॉड 71) का गुणन क्रम 70 है, और इस प्रकार 71 अभाज्य है।
तो 11 (मॉड 71) का गुणन क्रम 70 है, और इस प्रकार 71 अभाज्य है।


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


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


  एल्गोरिथम lucas_primality_test है
  '''algorithm''' lucas_primality_test '''is'''
     इनपुट: ''n'' > 2, प्रारंभिकता के लिए परीक्षण किया जाने वाला एक विषम पूर्णांक।
     '''input''': ''n'' > 2, an odd integer to be tested for primality.
             ''k'', एक पैरामीटर जो परीक्षण की सटीकता निर्धारित करता है।
             ''k'', a parameter that determines the accuracy of the test.
     आउटपुट: ''प्राइम'' यदि ''एन'' प्राइम है, अन्यथा ''मिश्रित'' या ''संभवतः मिश्रित''।
     '''output''': ''prime'' if ''n'' is prime, otherwise ''composite'' or ''possibly composite''.
   
   
     ''n''-1 के अभाज्य गुणनखंड निर्धारित करें।
     determine the prime factors of ''n''−1.
   
   
     LOOP1: ''k'' बार दोहराएँ:
     LOOP1: '''repeat''' ''k'' times:
         [2, ''एन'' - 1] की सीमा में ''ए'' को बेतरतीब ढंग से चुनें           
         pick ''a'' randomly in the range [2, ''n'' − 1]
{{nowrap|'''if''' <math>a^{n-1} \not\equiv 1 \pmod n</math> '''then'''}}
            '''if'''  '''then'''
                 ''समग्र'' लौटें
                 '''return''' ''composite''
             अन्य {{nowrap|{{color|gray|#}} <math>\color{Gray}{a^{n-1} \equiv 1 \pmod n}</math>}}
             '''else''' # 
                 LOOP2: ''n''-1 के सभी अभाज्य गुणनखंड ''q'' के लिए:                    
                 LOOP2: '''for''' all prime factors ''q'' of ''n''−1:
{{nowrap|'''if''' <math>a^\frac{n-1}q \not\equiv 1 \pmod n</math> '''then'''}}
                    '''if'''  '''then'''
                         यदि हमने ''n''-1 के सभी अभाज्य गुणनखंडों के लिए इस समानता की जाँच की
                         '''if''' we checked this equality for all prime factors of ''n''−1 '''then'''
                             ''प्राइम'' लौटाएं
                             '''return''' ''prime''
                         अन्य
                         '''else'''
                             LOOP2 जारी रखें
                             '''continue''' LOOP2
                     अन्य {{nowrap|{{color|gray|#}} <math>\color{Gray}{a^\frac{n-1}q \equiv 1 \pmod n}</math>}}
                     '''else''' # 
                         LOOP1 जारी रखें
 
                         '''continue''' LOOP1
   
   
     ''संभवतः मिश्रित'' लौटें।
     '''return''' ''possibly composite''.


== यह भी देखें ==
== यह भी देखें ==
* एडौर्ड लुकास, जिनके नाम पर इस परीक्षण का नाम रखा गया है
* एडौर्ड लुकास, जिनके नाम पर इस परीक्षण का नाम रखा गया है
* फ़र्मेट का छोटा प्रमेय
* फ़र्मेट की छोटी प्रमेय
[[पॉकलिंगटन प्राइमैलिटी टेस्ट]] परीक्षण, इस परीक्षण का एक उन्नत संस्करण जिसमें केवल n − 1 के आंशिक गुणनखंडन की आवश्यकता होती है
 
* [[पॉकलिंगटन प्राइमैलिटी टेस्ट|पॉकलिंगटन प्राइमैलिटी परीक्षण]], इस परीक्षण का एक उन्नत संस्करण जिसमें मात्र n − 1 के आंशिक गुणनखंडन की आवश्यकता होती है
*प्राथमिकता प्रमाण पत्र
*प्राथमिकता प्रमाण पत्र


Revision as of 09:51, 6 July 2023

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

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

अवधारणाएँ

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

और n- 1

के प्रत्येक अभाज्य कारक 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 (मॉड 71) का गुणन क्रम आवश्यक रूप से 70 नहीं है क्योंकि 70 का कुछ कारक ऊपर भी कार्य कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:

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

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

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

तो 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.

यह भी देखें

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

टिप्पणियाँ

  1. ↑ Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: a Computational Perspective (2nd ed.). Springer. p. 173. ISBN 0-387-25282-7.
  2. ↑ Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics. Vol. 9. Canadian Mathematical Society/Springer. p. 41. ISBN 0-387-95332-9.

[Category:Primality tes

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लुकास_प्राइमैलिटी_टेस्ट&oldid=213173’