Các vấn đề khi thực hiện kiểm tra nguyên thủy Lucas – Lehmer

Question

Tôi cố gắng thực hiện kiểm tra nguyên thủy của bài kiểm tra Lucas – Lehmer (LLT) cho các số Mersenne (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test). Nó nên được đa thức và do đó nhanh chóng. Đây là mã của tôi:

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;} 

đây là cố gắng sử dụng các thuật toán thực hiện trên: https://oobarbazanoo.github.io/findPrimeNumberWithSpecifiedQuantumOfDigits/

Khi tôi cố gắng số chữ số đó là dưới 7 mọi thứ đều ổn, nhưng khi tôi cố gắng yêu cầu số nguyên tố có ít nhất 7 chữ số chương trình chỉ bị lỗi và không đưa ra câu trả lời.

Xin hãy giúp tôi. Điều gì là sai với việc thực hiện thuật toán của tôi hoặc những gì là sai với chính chương trình của tôi?

Answer 1

Nếu tôi chạy mã trên https://repl.it/languages/javascript với sự thay đổi này:

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

Sau đó, nó kết thúc cho (dường như) bất kỳ số lượng chữ số. Tuy nhiên, kết quả có vẻ không chính xác: kết quả đầu ra không phải số nguyên tố có nhiều chữ số hơn số được yêu cầu.

Vấn đề là javascript có thể đánh giá modulo thành kết quả âm. Ví dụ: -2 % 5 sẽ là -2. Đây là toán học chính xác, nhưng hầu hết các thuật toán khoa học máy tính yêu cầu giá trị dương, vì vậy 3 trong trường hợp này.

Thêm M vào công thức đó sẽ đảm bảo rằng kết quả là dương bất kể ngôn ngữ quirks.

Vấn đề với kết quả không chính xác có thể do thực tế là bạn không làm theo yêu cầu này:

Các thử nghiệm Lucas-Lehmer hoạt động như sau. Gọi Mp = 2 ** p - 1 là số Mersenne để kiểm tra với p là số nguyên lẻ.

p có mã số n trong mã của bạn. Không nơi nào bạn đảm bảo rằng n là số nguyên tố.

Sau đó, cũng có loại số nguyên của javascript có thể không đủ lớn. Với n lớn hơn 23, nó bắt đầu đạt đến giới hạn của nó. Ví dụ, không có số nguyên tố Mersenne với 7 chữ số. Tiếp theo là 10 chữ số, là 2**31 - 1.

Tuy nhiên, bạn sẽ không thể tìm thấy nó trong (thuần) javascript, vì tính toán liên quan đến bình phương 2**31 - 1, which exceeds the bounds of javascript's integers.