लुकास-लेमर प्राथमिकता परीक्षण

Question

लागू करने में समस्याएं मैं मेर्सन संख्याओं (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test) के लिए लुकास-लेमर परीक्षण (एलएलटी) प्रारंभिक परीक्षण को लागू करने का प्रयास करता हूं। यह बहुपद होना चाहिए और इसलिए तेज़ होना चाहिए।

function countPrimeNumberWithDigits(numberOfDigits) 
    { 
     if(numberOfDigits < 1) 
     {return "Please give a valid input!";} 

     var shouldBeMoreThanThis = Math.pow(10, numberOfDigits-1), n = 3, M = countMWithIndex(n); 
     while(M < shouldBeMoreThanThis) 
     { 
      n += 2; 
      M = countMWithIndex(n); 
     } 

     console.log(n); 

     while(true) 
     { 
      var S = 4, k = 1; 
      M = countMWithIndex(n); 

      while(k != n - 1) 
      { 
       S = (S*S - 2)%M; 
       k +=1; 
      } 

      if(S!=0) 
      {n+=2;} 
      else 
      {break;} 
     } 

     return "Prime number: " + countMWithIndex(n); 
    } 

function countMWithIndex(n) 
    {return Math.pow(2, n) - 1;} 

यहाँ एल्गोरिथ्म का उपयोग करने के प्रयास के ऊपर लागू किया गया है: यहाँ मेरी कोड है https://oobarbazanoo.github.io/findPrimeNumberWithSpecifiedQuantumOfDigits/

जब मैं जो कम से कम 7 सब कुछ ठीक है है, लेकिन जब मैं के लिए पूछने की कोशिश अंकों की संख्या की कोशिश कम से कम 7 अंकों के साथ प्राइम नंबर प्रोग्राम सिर्फ ठोकर खाता है और जवाब नहीं देता है।

कृपया मेरी मदद करें। मेरे एल्गोरिदम कार्यान्वयन में क्या गलत है या मेरे प्रोग्राम के साथ क्या गलत है?

Answer 1

अगर मैं इस परिवर्तन के साथ https://repl.it/languages/javascript पर कोड चलाएँ:

S = (S*S - 2 + M)%M; 

तो यह (प्रतीत होता है) किसी भी अंकों की संख्या के लिए खत्म। हालांकि, परिणाम गलत प्रतीत होते हैं: यह अनुरोध से अधिक अंकों के साथ गैर-प्राइम आउटपुट करता है।

समस्या यह है कि जावास्क्रिप्ट नकारात्मक परिणामों के लिए मॉड्यूल का मूल्यांकन कर सकता है। उदाहरण के लिए, -2 % 5-2 होगा। यह गणितीय रूप से सही है, लेकिन अधिकांश कंप्यूटर विज्ञान एल्गोरिदम को सकारात्मक मानों की आवश्यकता होती है, इसलिए इस मामले में।

उस सूत्र में M जोड़ना सुनिश्चित करेगा कि परिणाम भाषा quirks परवाह किए बिना सकारात्मक है।

लुकास-लेह्मर परीक्षण इस प्रकार काम करता है:

समस्या गलत परिणाम के साथ तथ्य यह है कि आप इस आवश्यकता का पालन नहीं करते की वजह से होने की संभावना है। एमपी = 2 ** पी -1 को का परीक्षण करने के लिए मेर्सन नंबर होना चाहिए, जिसमें एक विषम प्राइम है।

p वहाँ अपने कोड में n है। कहीं भी आप सुनिश्चित नहीं करते हैं कि n प्रमुख है।

तब भी जावास्क्रिप्ट का पूर्णांक प्रकार पर्याप्त नहीं हो सकता है। n23 से बड़ा के साथ, यह इसकी सीमा तक पहुंचने लगता है। उदाहरण के लिए, 7 अंकों के साथ कोई मेर्सन प्राइम नहीं है। अगला 10 अंकों के साथ है, जो 2**31 - 1 है।

हालांकि आप इसे (शुद्ध) जावास्क्रिप्ट में नहीं ढूंढ पाएंगे, क्योंकि गणना में 2**31 - 1, which exceeds the bounds of javascript's integers स्क्वायरिंग शामिल है।