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

Revision as of 09:58, 6 July 2023

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

↑ Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: a Computational Perspective (2nd ed.). Springer. p. 173. ISBN 0-387-25282-7.
↑ 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 test

[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.

[1]

[2]

@@ Line 1: / Line 1: @@
 {{for multi|मेर्सन संख्याओं के लिए परीक्षण|लुकास-लेहमर प्राइमैलिटी परीक्षण|लुकास-लेहमर-रिसेल परीक्षण|लुकास-लेहमर-रिसेल परीक्षण|लुकास संभावित अभाज्य परीक्षण|लुकास स्यूडोप्राइम}}
-[[कम्प्यूटेशनल संख्या सिद्धांत]] में, लुकास परीक्षण एक प्राकृतिक संख्या ''n'' के लिए एक [[प्रारंभिक परीक्षण]] है; इसके लिए आवश्यक है कि ''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
-|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 अभाज्य है।
 ==अवधारणाएँ==
@@ Line 12: / Line 12: @@
 :<math>a^{({n-1})/q}\ \not\equiv\ 1 \pmod n \, </math>
-के प्रत्येक अभाज्य कारक q के लिए तो 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 हैं। हम यादृच्छिक रूप से a=17 <n का चयन करते हैं। अब हम गणना करते हैं:
+इस प्रकार से उदाहरण के लिए, n = 71 लें। फिर n-1 = 70 और 70 के अभाज्य गुणनखंड 2, 5 और 7 हैं। अतः हम यादृच्छिक रूप से a=17 <n का चयन करते हैं। इस प्रकार से अब हम गणना करते हैं:
 :<math>17^{70}\ \equiv\ 1 \pmod {71}.</math>
@@ Line 25: / Line 25: @@
 :<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^{14}\ \equiv\ 25\ \not\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>
-फिर, इससे यह नहीं पता चलता कि 11 (मॉड 71) का गुणन क्रम 70 है क्योंकि 70 का कुछ गुणनखंड भी कार्य कर सकता है। तो 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:
+अतः फिर, इससे यह नहीं पता चलता कि 11 (मॉड 71) का गुणन क्रम 70 है क्योंकि 70 का कुछ गुणनखंड भी कार्य कर सकता है। इस प्रकार से फिर 70 को उसके अभाज्य गुणनखंडों से विभाजित करके जाँचें:
 :<math>11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>
@@ Line 42: / Line 42: @@
 तो 11 (मॉड 71) का गुणन क्रम 70 है, और इस प्रकार 71 अभाज्य है।
-(इन [[मॉड्यूलर घातांक]] को पूर्ण करने के लिए, कोई तीव्र घातांक एल्गोरिदम का उपयोग कर सकता है जैसे कि [[वर्ग द्वारा घातांक]] या [[जोड़-श्रृंखला घातांक]])।
+(इस प्रकार से इन [[मॉड्यूलर घातांक|'''मॉड्यूलर घातांक''']] को पूर्ण करने के लिए, कोई तीव्र घातांक एल्गोरिदम का उपयोग कर सकता है जैसे कि [[वर्ग द्वारा घातांक|'''वर्ग द्वारा घातांक''']] या [[जोड़-श्रृंखला घातांक|'''योग-श्रृंखला घातांक''']])।
 ==एल्गोरिदम==
@@ Line 82: / Line 82: @@
 {{number theoretic algorithms}}
-[[Category: आदिमता परीक्षण]] [Category:Primality tes
+[[Category: आदिमता परीक्षण]]
+[Category:Primality test
 [[Category: Machine Translated Page]]
 [[Category:Created On 30/06/2023]]

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:58, 6 July 2023

Contents

अवधारणाएँ

उदाहरण

एल्गोरिदम

यह भी देखें

टिप्पणियाँ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 09:58, 6 July 2023

अवधारणाएँ

उदाहरण

एल्गोरिदम

यह भी देखें

टिप्पणियाँ

Navigation

Wiki tools

Page tools

Other projects

Categories