ТЕСТ ЛУКАСА ЛЕМЕРА

Автор На чтение 40 мин Опубликовано



Из Википедии, свободной энциклопедии

См. эссе «Тесты на примитивность» на J wiki
.

  
 
 
 
 
 
 
 


 
 
 
  
 Простые числа Мерсенна:
М2, М3, М5, М7, М13, М17, М19, М31 
  
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   «Простые числа Мерсенна:» 

 
 
 
 
 
 
 
  
 Простые числа Мерсенна:
М2 М3 М5 М7 М13 М17 М19 М31
  
  
   


   
   
   
   

   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   

   
   
   
   
   
   

   
   

   
   


   
   
   
   

   
   
   
   
   
   

   
   
   
   
   
   
   
   

   
   
   
   

   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   


   
   
   
   
   
   
   

   
   «Простые числа Мерсенна:» 

   
   
   
   
   

   
   
   
   

   
   

   

  
 Простые числа Мерсенна:
 М2 М3 М5 М7 М13 М17 М19 М31

Работает с
: Дельфи
версия 6.0

  
   
   
   



   
   

   
   


   
   
   
   


   

   
   
   
   
   

   

   
   
   
   
   

   

   
   
   
   
   
   
   

   

   
   
   

   




   
   

   
   

   
   






   
   
   
   

   
   
   

   

   

   



  
 2
3
5
7
13
17
19
31

Затраченное время: 10,167 мс.

Перевод
: Эрланг 

  
   
   

   
   

   
   
   

   
   
   
   
   
   
   
   
   
   
   

   

   

   
   
   
   
   
   

   
   
   
   

   
   
   
   

   
   

   




  
 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279
  
  
   
   
   
   

   


[1,б]  
[  
Лукас-Лемер  
]  

   

[  
   
   
распечатка  
   
]  
   

  
 Простые числа Мерсенна:
М2 М3 М5 М7 М13 М17 М19 М31

Использование 64-битного целочисленного типа ограничивает поиск значением M31.

  
   
   
   
   
   


   
   
   
   
   


   
   
   

   

   
   

   
   
   
   
   

   
   
   

   
   
   
   
   

   
   
   

   

   



   
   
   


   
   
   
   



   
   
   

   
   
   
   
   
   
   

   
   
   

   



  
 М2 М3 М5 М7 М13 М17 М19 М31 
  
   

   
   
   

   
   
   
   
   
   

   
   
   

   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   
   

   

   ; запустить его в фоновом режиме 

   

   
   
   
   
   ; список простых кандидатов 


   
   

   
   
   

   
   
   
   ; ; вернуть следующее состояние

Перевод
: Раку

М2
М3
М5
М7
М13
М17
М19
М31
М61
М89
М107
М127
М521
М607
М1279
М2203
М2281
^ С

  
        # синтаксис: GAWK -f LUCAS-LEHMER_TEST. АВК

# преобразовано из Паскаля

Простые числа Мерсенна: M2 M3 M5 M7 M13 M17 M19



 
















      
       
       
       


       
       
       
       
       
       

       
       
       
       
       
       

       
       
       
       
       

       
       
       
       

       
       

       
       
       
       
       
       
       
     
 
  
  
  
  
  
  
  
  
 
  Бесконечный список простых чисел Мерсенна:
 (2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253.
 
   
  % проверка, является ли число простым 
 
  ; - показать.
 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423
 истинный.
 
  19→М
 1→Н
 Для(Е,2,М)
 Если Е=2
 Тогда: 0→С
 Остальное:4→С
 Конец
 (Н+1)*2-1→Н
 Для(I,1,E-2)
 Напоминание(S*S-2,N)→S
 Конец
 Если S=0
 Затем: Disp E
 Конец
 Конец 
  2
 3
 5
 7
 13
 17
 19 
  



     
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      


      
      
      
      

      
      
      
      
      
      
      

     


      Через 3 секунды напечатается
     


      M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607
     


      Тестирование больших чисел (т.е.? 5000) возможно, но это займет несколько минут.
  


  
  Перевод 
:  Кложур 
  



  
  
   
   
   
   
   
   
   
   ;необходим для сокращения, так как «или» реализовано как макрос 


   
   

   
   
   
   
   
   
   

   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   


   
   

   
   
   
   

   
   
   
   
   
   
   

   
   
   
   
   

   
   
   
   
   

   
   

   
          
         
         
         
         
        
        
        


        
        
        
        
        
        
        
        
        
        
        

  
  (2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423)
 
   
 : Лукас-Лемер
 1+ 2 сделать
 4 i 2  * замена абс 1+ дубль + 1- замена
 i 1- 1 ?do dup * 2 - по модулю цикла 0= if ." M" i . затем
 петля кр
 ;
1 15 Лукас-Лемер
 
    Формально пусть     
 
 и     
 
 . 
 
   Формально,     
 
 и     
 
 находятся в  X 
 . По злоупотреблениям языком     
 
 и     
 
 отождествляются со своими изображениями в  X 
 при естественном гомоморфизме колец из     
 
 до  Х 
 который отправляет     
 
 до  Т 
 . 
 
 
   
  ; ; ; Сердце алгоритма 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 
      


      
 
  
  
  
  
  
  
  
  
  
  ; ; ; Тривиальная неоптимизированная реализация базовых простых чисел 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 М2 М3 М5 М7 М13.
  
 с = 0
Экспонента DO = 2, 31
 ЕСЛИ(показатель > 2) s = 4
 п = 2^экспонента - 1
 DO i = 1, показатель степени-2
 s = MOD(s*s - 2, n)
 ЭНДДО
 IF(s == 0) WRITE(Messagebox) 'M', показатель степени, ' — простое число; ', н
ЭНДДО

КОНЕЦ 
  Работает с 
 :  GHCi 
 версия 6.8.2
  Работает с 
 :  ГХК 
 версия 6.8.2
  
   

   


   
   
   
   
   
   
   
   
   
   
   


   
   
   
   
   
   

   
   
   
   
   
   
   
   
   


   
   
   

   
   
   
   
   
   
   


   
   
   
   
   
   
   
   
   
   

  
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

  
 Чтобы подняться до:
 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213
  
  Перевод 
 :  Питон 
  
   
   
   


   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
         

        
        
        
        

        
        
        
       
       
       
       
       

       
       
       
       
       
       

       
       

       
       



       
       
       
       
       
       
       

       
      

      
 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 
  При p до 10_000 печатается:
 
  M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9941 
   
 иэкспмакс=30
 п=1
 для iexp=2:iexpmax
 если iexp==2, то s=0, иначе s=4; конец
 п=(п+1)*2-1
 для я=1:iexp-2
 s=по модулю((s*s-2),n)
 конец
 если s==0, то printf("M%d ",iexp); конец
 конец
 
  М2 М3 М5 М7 М13 М17 М19 
 
  Эта статья о тесте Лукаса-Лемера, который применим только к числам Мерсенна; Для теста Люка-Лемера, применимого к натуральному числу  n 
 , см.  Тест Лукаса на простоту 
 . О тесте Лукаса-Лемера-Ризеля см. . Тест Лукаса-Лемера-Ризеля .
 . 
 
  напечатайте «Простые числа Мерсенна:»
 для р = от 2 до 20
 если lucasLehmer(p) выведите "M",p
 следующий стр
 конец
суб-лукасЛемер (п)
 мп = (2^р)-1
 сн = 4
 для i = 2 до p-1
 сн = (сн ^ 2) - 2
 sn = sn - (mp * этаж(sn/mp))
 следующий
 вернуть sn = 0
 концевой переходник 
  Обработка первого списка показывает, что тест работает. Обработка второго показывает, что он работает с более крупными числами.
  
   


   

   

   



   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   


   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   

   
   


   
   

   

   

   



   
   
   

   
   
   
   

   
   
   

   
   
   

   
   
   
   
   
   
   

   
   
   

   

   
   
   
   
   
   
   
   
   

   
   
   
   

   

   
   
   
   
   

   
   

   

   


  
 М3 М5 М7 М13 М17 М19 М31 М61 М89 М107 М127
М521 М607 М1279 М2203 М2281 М3217 М4253 М4423 М9689 М9941 М11213 М19937.
  
  
        # векторизованный подход, основанный на скалярном коде из primeSieve и mersenne в `numbers` пакета CRAN 


        
        
        
       # обратите внимание, что сито ниже предполагает n > 9 


       # просеять множество простых чисел до n 

       
       
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  «особый случай M2 == 3\n» 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 


        

     
 Фринка 
 функция автоматически определяет числа вида 2  n 
-1 и выполняет над ними тест Люка-Лемера, включая проверку того, является ли n простым, что достаточно для доказательства простоты для этой формы.
     
  для n = простые числа []
 если isPrime[2^n-1]
 println[n] 
  иэкспмакс = 15
 п=1
 выход=""
 Для iexp = 2 Для iexpmax
 Если iexp = 2 Тогда
 с = 0
 Еще
 с = 4
 Конец, если
 п = (п + 1) * 2 – 1
 Для i = 1 Для iexp - 2
 s = (s * s - 2) Mod n
 Следующий
 Если s = 0 Тогда
 выход = выход & "М" & iexp & " "
 Конец, если
 Следующий
 Wscript.echo выход
 М2 М3 М5 М7 М13 
 int64 достаточно хорош до M31:
  
   


   
   
   

   
   
   


   
   
   

   
   
   
   
   
   
   

   

   
   
   
   
   

   
   
   

   

   
   
   

   
   
   
   
   
   
   
   
   // Это избавляет от необходимости использования математического модуля для возведения в степень 

   
   
   
   
   
   
   

   
   
   
   
   
   
   

   
   
   
   
   

   
   
   
   'является ПРАЙМ; ' 

   


  
 :> ./Лукас Лемер
М2 — ПРЕМЬЕР!
 М3 — ПРЕМЬЕР!
 М5 — ПРЕМЬЕР!
 М7 — ПРЕМЬЕР!
 М13 — ПРЕМЬЕР!
 М17 — ПРЕМЬЕР!
 М19 - ПРЕМЬЕР!
 М31 — ПРЕМЬЕР!
  
 Из Википедии, свободной энциклопедии
 Эта статья о тесте Лукаса-Лемера, который применим только к числам Мерсенна! Для теста Люка-Лемера, применимого к натуральному числу  n 
 , см.  Тест Лукаса на простоту 
 . О тесте Лукаса-Лемера-Ризеля см.  Тест Лукаса-Лемера-Ризеля .
 .
 (ранее Perl 6)
  
   
 () { }
   
 ( ) {
   
 "="
   
 "="
   
 "=" ;
   
 !
   
}
   

   
. (,,, … *).(:).( *. ). { .; };
  
 М2
М3
М5
М7
М13
М17
М19
М31
М61
М89
М107
М127
М521
М607
М1279
М2203
М2281
М3217
М4253
М4423
М9689
М9941
М11213
^ С

реальное 0м55.527с
пользователь 6m47.106s
системный 0m0.404s 
 защита Мерсенна( п ) =
 если p == 2, то вернуть true
 
 вар с = 4
 вар M = 2^p - 1
 
 повторить р - 2
 s = (s*s - 2) mod M

 с == 0

импортировать целые числа.простые числа

для р < - primes().filter( Мерсенна ).take
 println('M' + p) 
 М2
М3
М5
М7
М13
М17
М19
М31
М61
М89
М107
М127
М521
М607
М1279
М2203
М2281
М3217
М4253
М4423
  
 Мы используем целые числа произвольной точности, чтобы иметь возможность проверить любое произвольное простое число.
  
   

   
 


   
   
   
   
   
   

   
   
   
   

   
   

   
   
   
   
   
   
   
   
   
   
   

   
   

   
   

   
   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   

   
   

   
   

   

   


   
   
   
   
   
   

   
   
   
   

   
   

   
   

   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   

   
   

   

   


   
   // в качестве аргумента можно указать произвольную верхнюю границу 

   
   
   
   
   
   

   
   

   
   
   
   

   
   
   

   

   
   
   


   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   

   
   
   

   

   


  
 (примерно через восемь часов)
 Нахождение простых чисел Мерсенна в M[2.2147483647]:
 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213
  
  
   
   
   
   

   
   
   
   
        
       

       
       
       
      
 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 
     
      
      
      

      
      
      



      
      
      
      # максимальное запрошенное количество десятичных знаков 2 ** MP-1 # 

      
      
      
      
      
      

      
      
      
      
      
      
      
      # нет беззнакового # 

      
      
      
      # найти 45 простых чисел, если int было передано достаточно битов # 


      
      
      


      
      

      
      
      

      
      
      
      

      
      
      
      

      
      
      

      

      
      
      
      
      



  
  Нахождение простых чисел Мерсенна в M[2.33218]:
 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209 
  Zig изначально поддерживает 128-битные целочисленные типы, что означает, что можно найти все простые числа Мерсенна до M127. (требуется написать процедуру modmul() для вычисления (a * b) % m для 128-битных целых чисел без переполнения.)
  
   
   
   

   
   
   

   
   
   


   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   

   

   

   
   
   «Эти числа Мерсенна простые:» 
   

   
   
   

   
   

   
   
   

   
   
   



   
   
   
   
   

   
   
   
   
   
   
   



   
   
   
   

   
   
   
   

   
   
   
   

   
   

   
   
   
   

   
   
   
   
   

   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   

   
   
   
   

   



   
   
   
   
   
   
   
   

   
   
   
   
   

   
   
   
   
   
   

   
   
   
   
   
   

   
   
   
   
   

   
   
   
   
   
   

   
   
   
   
   
   
   
   
            
           
           
           
           
           
           
          
          

          
          
          

          
          
          
          

          
          
          
          
          
          
          
          
          
          
          
          
          
          
          
          
          

          

          
          


  
  Эти числа Мерсенна являются простыми: M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127.
 
   
 
  
 
   тест Лукаса-Лемера 
 
Вам предлагается  решить эту задачу 
 согласно описанию задачи, используя любой язык, который вы знаете
 для  
 
 
 нечетное простое число, число Мерсенна  
 
 
 является простым тогда и только тогда, когда  
 
 
 делит  
 
 
 где  
 
 
 , и  <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c70179b14d0b79abcccda066ac7fbbd14ab82023" aria-hidden="true" alt="{\displaystyle S
=4}">
 
 
 .
 Задача
 Вычислить все простые числа Мерсенна до реализации
 максимальной точности, или 47 -й 
 Простое число Мерсенна (в зависимости от того, что наступит раньше).
 см. «Простые числа Мерсенна:» + nl
для р = от 2 до 18
 если lucasLehmer(p) см. "M" + p + nl ок
следующий
 
Func Лукас Лемер П
 я = 0 мп = 0 sn = 0
 если p = 2, верните true, ок
 если (p и 1) = 0 вернуть ложь, ок
 мп = мощность(2,р) - 1
 сн = 4
 для i = 3 до p
 sn = мощность(sn,2) - 2
 sn -= (mp * пол(sn / mp))
 следующий
 возврат (сн=0) 
  Перевод 
 :  Д 
 F isPrime(p)
 я р < 2 | р% 2 == 0
 Р п == 2
 L(i) 3. Int(sqrt(p))
 Я п % я == 0
 Р 0Б
 Р 1Б

F isMersennePrime(p)
 Я !isPrime(p)
 Р 0Б
 я р == 2
 Р 1Б
 В mp = BigInt
 ^ p - 1
 В с = BigInt
 Л 3.п
 s = (s^2 - 2)%мп
 Р с == 0

Л(п) 2,2299
 Я isMersennePrime(p)
 print('M'p, end' ' ') 
 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281
  
 Пользуется решетом Эратосфена.
  
   // добавляем пакет attaswift/BigInt из Github 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 


 
 
 

  
 2^3 - 1 = 7 - простое число
2^5 - 1 = 31 - простое число
2^7 - 1 = 127 - простое число
2^13 - 1 = 8191 является простым числом
2^17 - 1 = 131071 является простым числом
2^19 - 1 = 524287 является простым числом
2^31 - 1 = 2147483647 — простое число
2^61 - 1 = 2305843009213693951 — простое число
2^89 - 1 = 618970019642690137449562111 является простым числом.
2^107 - 1 = 162259276829213363391578010288127 является простым числом.
2^127 - 1 = 170141183460469231731687303715884105727 - простое число 
Содержание
  1. 128-битная версия
  2. 30-е и 31-е числа Мерсенна
  3. Великий интернет-поиск чисел Мерсенна
  4. Альтернативная версия для обработки 64- и 128-битных целых чисел.
  5. От до
  6. Факторизация чисел Мерсенна
  7. Версия с пробным делением и быстрым модульным сокращением
  8. Мера адекватности выборки
  9. Доказательство правильности
  10. Совершенные числа
  11. Люка и Лемер
  12. Вариации и обобщения
  13. Теорема множителей Эйлера и Мерсенна
  14. 29-е число Мерсенна
  15. 21-е, 22-е и 23-е числа Мерсенна
  16. Доказательство правильности
  17. Поиск стартового значения
  18. Visual Basic. НЕТ
  19. Простые числа Мерсенна и тест Люка-Лемера
  20. Алгоритмы поиска простых чисел
  21. Решето Эратосфена
  22. Числа Мерсенна и тест Люка-Лемера
  23. Теорема Ферма и тест Миллера-Рабина
  24. Тест Люка и Тест Baillie–PSW
  25. Заключение
 BASIC256 не поддерживает большие целые числа. Вычисления ограничены диапазоном целочисленного типа.
 напечатайте «Простые числа Мерсенна»:
для р = от 2 до 18
если lucasLehmer(p), то выведите «M»; п
следующий стр
конец

функция ЛукасаЛемера (p)
мп = (2^р)-1
сн = 4
для i = 2 до p-1
сн = (сн ^ 2) - 2
sn = sn - (mp * этаж(sn/mp))
 следующий
вернуть sn = 0
конечная функция 
 Используя свою собственную арифметику, BBC BASIC может тестировать только до M23.
  
   
   

   
   

   
   
   
   
   
   

   
   
   
   
   
   

   

   

   

   
   

   
   
   
   

   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   

   
   
   

   
   
   
   
   
   

   
   
   
   
   

   
   
   
   
   
   
   

   

   
   
   
   

  
 Простые числа Мерсенна:
М2
М3
М5
М7
М13
М17
М19
  
  
   
   
   

   
   
   


   
   
   
   
   


   
   
   
   
   


   
   
   
   


   


   
   
   
   


   


   
   
   
   
   
   
   
   
   
   


   
   
   
   
   
   
   
   


   
   
   
   
   
   
   
   
   
   


   
   


   
   
   
   
   

   

   
   
   


   


   

  
 2 3 5 7 
 Из-за очень больших вычисленных чисел,
 привязка Mapm используется для вычислений с произвольной точностью.
 readlib 'mapm';

мапм.xцифры;

мерсенна  := proc(p::number)
 местное с, м;
 с  := 4;
 м  := mapm.xnumber(2^p) - 1;
 если р = 2, то
 вернуть истину
 еще
 для меня от 3 до р сделать
 s  := (mapm.xnumber(s)^2 - 2)  % m
 од;
 вернуть mapm.xtoNumber(s) = 0
 фи
конец;

для меня от 3 до 64 делаю
 если Мерсенна(i), то
 write('M' & я & ' ')
 фи
од; 
 Проверка больших чисел занимает много времени, поэтому мы ограничиваем p до
 быть меньше 1000.
 определить Lucas_Lehmer_Test(p);
 lvars mp = 2**p - 1, sn = 4, i;
 для меня от 2 до р - 1 сделать
 (sn*sn - 2) rem mp -> sn;
 конец для;
 сн = 0;
конец определения;

lvars p = 3;
printf('M2', '%p\n');
пока p  р;
в конце концов; 
 (получено за несколько секунд)
 М2
М3
М5
М7
М13
М17
М19
М31
М61
М89
М107
М127
М521
М607 
  
 

 

 
 
 
 
 
 
 
 
 
 

 

 
 
 
 

 
 
 
 
 

  
  
 
  
 2 3 5 7
 13 17 19 31
 61 89 107 127
 521 607 1279 2203
2281 3217 4253 4423
  
 (де-прем; (N)
 (или
 (= Н 2)
 (и
 (> № 1)
 (бит? 1 Н)
 (пусть S (квадрат N)
 (для (Д 3 Т (+ Д 2))
 (Т (> Д С) Т)
 (T (=0 (% N D)) НОЛЬ)) ) ) ) )

(де Мерсенн? (П)
 (или
 (= П 2)
 (пусть (MP (dec (>> (- P) 1)) S 4)
 (сделать (- П 2)
 (setq S (% (- (* S S) 2) MP)) )
 (=0 С) ) ) ) 
: (для N 10000
 (и (простое? N) (мерсенна? Н) (println N)) )
2
3
5
7
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
9689
9941 
 eratosthenes
 и isprime
 определены в  Решето Эратосфена#Шлатанство 
 .
 [dup temp put
 дублировать бит 1 -
 4
 гнить 2 - раза
 [дуп*
 дублировать временную долю >>
 окунуть [ поверх & ] +
 2dup > нет, если
 [ над - ]
 2 - ]
 0 =
 выход температуры пресечения] is l-l ( n --> b )

 25000 эратосфенов
 [] 25000 раз [ i^ isprime if [ i^ join ] ]
 1 сплит
 с каждым
 [дуп л-л, если присоединюсь, иначе упаду]
 эхо 
 [ 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 ] 
 Modula-3 использует L как литерал для  LONGINT 
 .
 МОДУЛЬ LucasLehmer EXPORTS Main;

ИМПОРТ В/В, Fmt, Длинный;

ПРОЦЕДУРА Мерсенна(p: КАРДИНАЛ): BOOLEAN =
 ВАР
 с := 4L;
 м := Длинный. Сдвиг(1Л,п) - 1Л; (* 2^p - 1 *)
 НАЧИНАТЬ
 ЕСЛИ р = 2, ТО
 ВОЗВРАТ ИСТИНА;
 ЕЩЕ
 FOR i := 3 TO p DO
 s := (s * s - 2L) MOD m;
 КОНЕЦ;
 ВОЗВРАТ с = 0L;
 КОНЕЦ;
 КОНЕЦ Мерсенн;

НАЧИНАТЬ
 FOR i := 2 ДО 63 DO
 ЕСЛИ Мерсенн(i), ТО
 ИО. Put("M" & Fmt. Int(i) & " ");
 КОНЕЦ;
 КОНЕЦ;
 ИО. Вставить("\n");
КОНЕЦ Лукас Лемер? 
 М2 М3 М5 М7 М13 М17 М19 М31 
 607rz2en{J4{J.*2.-2{th}c! **-.%}#R2.-E! н! it}f[2+]{2\/**-.}m[p^ 
 3
7
31
127
8191
131071
524287
2147483647
2305843009213693951
618970019642690137449562111
162259276829213363391578010288127
170141183460469231731687303715884105727
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037 121987999716643812574028291115057151
5311379928167670986895882065524686273295931177270319231994441382004035598608522427391625022652292856688893294862465010153 46579337652707239409519978766587351943831270835393219031728127 
 В JavaScript мы используем BigInt (числа с суффиксом «n»), поэтому мы можем использовать действительно большие числа.
  
   ////////// В JavaScript у нас нет sqrt для BigInt — так что вот реализация 

   
   
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   

   

   
   
   

   


   
   
   

   
   
   
   
   

   
   
   'извлечение квадратного корня из отрицательных чисел не поддерживается' 

   


   
   
   
   
   

   
   

   

   
   
   

   

   ////////// Конец реализации sqrt 


   
   
   

   
   
   
   
   

   
   

   
   
   
   
   
   
   
   
   
   
   
   
   

   
   

   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   

   
   

   

   
   

   

   


   
   
   

   
   
   
   
   

   
   

   
   
   

   
   
   
   
   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   

   
   
   
   

   

   


   
   
   
   

   
   
   
   

   

   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   

   
   
   

   

   

   

  
 Нахождение простых чисел Мерсенна в M[2,5000]:
М2
М3
М5
М7
М13
М17
М19
М31
М61
М89
М107
М127
М521
М607
М1279
М2203
М2281
М3217
М4253
М4423
. Прошло: 107748 мс
  
 Со встроенной арифметикой до 23: для больших чисел необходимо использовать программу MULPREC.
 ПРОГРАММА LL_TEST

!$ДВОЙНОЙ

ПРОЦЕДУРА LUCAS_LEHMER(P%->RES)
 ЛОКАЛЬНЫЙ I%,MP,SN
 ЕСЛИ P%=2, ТО RES%=ИСТИНА, ПРОЦЕДУРА ВЫХОДА ЗАВЕРШАЕТСЯ, ЕСЛИ
 IF (P% AND 1)=0 THEN RES%=FALSE ПРОЦЕДУРА ВЫХОДА ЗАВЕРШАЕТСЯ ЕСЛИ
 МП=2^П%-1
 серийный номер=4
 ДЛЯ I%=3 ДО P%DO
 СН=СН^2-2
 SN-=(MP*INT(SN/MP))
 КОНЕЦ НА
 РЭС%=(СН=0)
ЗАВЕРШЕНИЕ ПРОЦЕДУРЫ

НАЧИНАТЬ
 PRINT("Простые числа Мерсенна:")
 ДЛЯ P%=2 ДО 23 ДО
 LUCAS_LEHMER(P%->RES%)
 IF RES% THEN PRINT("M";P%) END IF
 КОНЕЦ НА
КОНЕЦ ПРОГРАММЫ 
 Простые числа Мерсенна:
М 2
М 3
М 5
М 7
М 13
М 17
М 19
  
 Coffee Script действительно затруднен из-за отсутствия полной синтаксической поддержки генераторов JavaScript. Цикл для сбора чисел Мерсенна должен выполняться в императивном стиле, а не в более функциональном стиле при использовании генератора бесконечных ленивых простых чисел.
  
   
   
   
   # Расширяемое сито Соренсона из задания: Расширяемый генератор простых чисел 


   # Проверяем, является ли 2^n-1 простым числом Мерсенна. 

   # предполагает, что аргумент p является простым. 


   
   

   
   
   
   
   
   

   

   
   
   
   
   
   
   
   

   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   
   


   
   

   
   

   
   
   
   
   

   
   

   
   


   
   «Некоторые простые числа Мерсенна: 
   
   
   
   
   
   
   

  
 Некоторые простые числа Мерсенна: M2,M3,M5,M7,M13,M17,M19,M31,M61,M89,M107,M127,M521,M607,M1279,M2203,M2281.

  
  Работает с 
 :  Фортран 
 версия 90 и новее
 Только число Мерсенна с простым показателем само по себе может быть простым, но для небольших чисел, используемых в этом примере, включать эту проверку не стоило. По мере увеличения размера показателя степени это становится более важным.
  

   


   
   
   
   
   
   

   
   
   
   

   
   
   
   

   

   
   
   
   

   
   
   
   
   

   
   
   

   

   
   
   

   

   
   
   
   
   

   
   
   
   

   
   
   
   
   
   

   

   
   
   
   
   
   «ПРАЙМ» 

   

   


  
  128-битная версия 
 Эта версия может найти все простые числа Мерсенна до M127. Он основан на коде Zig, но написан в стиле Fortran 77 (фиксированный формат, неструктурированные циклы). Работает с GNU Fortran, который поддерживает 128-битные целые числа.
  
   
   

   
   

   
   


   
   
   
   
   

   
   
   


   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   


   
   
   
   «Эти числа Мерсенна простые:» 


   
   
   
   
   
   

   
   
   

   
   
   

   
   
   
   
   
   
   
   


   
   

   



   

   

   
   

   
   
   

   
   
   
   


   
   
   
   
   

   
   
   
   
   

   

   
   
   
   
   

   
   
   

   
   
   
   
   
   
   

   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   
   

   




   
   

   
   


   
   
   

   
   
   
   

   
   
   
   


   
   
   
   
   

   
   
   
   
   

   
   
   
   
   
   

   
   
   
   
   

   

   
   
   
   
   
   
   

   


   
   
   
   
   

   
   
   
   
   
   
   

   
   
   
   
   

   

   
   
   
   
   
   
   

   

   
   

   

  
 Эти числа Мерсенна являются простыми:
 2 3 5 7 13 17 19 31 61 89 107 127
  
  Перевод 
 :  Д 
  Работает с 
 :  лангур 
 версия 0.11
 Полагаю, теоретически возможно провести тест до 47-го простого числа Мерсенна, как указано в описании задачи, хотя это может занять некоторое время. Что касается предела, то он будет очень высоким.
 val .isPrime = f .i == 2 или
 .i > 2, а не любой f(.x) .i div .x, pseries 2 . .я ^/ 2

val .isMersennePrime = f(.p) {
 если .p == 2: вернуть истину
 если нет .isPrime(.p): верните false

 val .mp = 2 ^ .p - 1
 for[.s=4] из 3 . .p {
 .s = (.s ^ 2 - 2) rem .mp
 } == 0
}

writeln join " ", map f $"M\.x;", filter .isMersennePrime, series 2300  
  M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281
  
 30-е и 31-е числа Мерсенна
 Следующие два простых числа Мерсенна: ${M_{132049}}$
 и ${M_{216091}}$
 , — были на самом деле обнаружены еще до 29-го (той же командой, которая обнаружила и 28-е).  Они использовали Cray X-MP, чтобы найти 30-е число Мерсенна в сентябре 1983 года и 31-е — в сентябре 1985 года.  Проверим $\# 30 $
 с помощью функции поиска в диапазоне $110603 \leqslant p \leqslant 139901$
 .  Для проверки каждого ${M_p}$
 в этом диапазоне понадобилось 4 часа и 8 минут.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 Великий интернет-поиск чисел Мерсенна
 С открытием 34-го простого числа Мерсенна — ${M_1257787}$
 — в сентябре 1996 года закончилась эпоха суперкомпьютеров для поиска простых чисел Мерсенна.  Следующие 15 были найдены добровольцами Великого интернет-поиска простых чисел Мерсенна (  GIMPS 
 ), в рамках которого проводится вариант теста Люка-Лемера (в качестве фонового процесса) на персональных компьютерах.  Этот масштабный проект распределенных вычислений в настоящее время достигает уровня производительности, эквивалентного приблизительно 300 терафлопс в секунду, причем задействуется время простоя более чем 1,3 миллиона компьютеров.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Проверим 34-е число Мерсенна с помощью теста Люка-Лемера.  На этом этапе мы достигли предела возможностей личного компьютера.  На тестирование тысячи чисел Мерсенна в этом диапазоне потребуется много дней.  Интересно отметить, что тест Люка-Лемера часто используется в качестве  стресс-теста 
 надежности компьютерного оборудования и программного обеспечения, так как даже одна арифметическая ошибка среди миллиардов вычислений, необходимых для тестирования одного большого простого числа, повлечет за собой неправильный вывод, что будет означать потерю числа Мерсенна или ложный ответ.  Тот факт, что мы проверили каждое ${M_p}$
 для простых чисел в промежутке между 2 и 139901, убедительно доказывает надежность арифметики больших чисел и бинарных операций в системе Mathematica и языке Wolfram Language.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
  
 This example is  incomplete 
 .  This seems to hang, something is wrong in the algo.  Убедитесь, что оно соответствует всем требованиям задачи, и удалите это сообщение.
  Перевод 
 :  иди 
  
   

   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   

   
   


   

   
   

   

   

   


   

   
   
   

   
   
   
   
   
   
   

   
   
   

   
   
   

   
   
   
   
   

   
   
   
   
   

   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   

   

   
   
   
   
   

   

   

   


  
 М3 М5 М7 М13 М17 М19 М31 .
  
 Альтернативная версия для обработки 64- и 128-битных целых чисел.
 Форт поддерживает модульное умножение без переполнения, используя операции смешанного режима, которые работают с 128-битными промежуточными результатами. Также возможно выполнить тест Лукаса-Лемера, используя целые числа двойной точности (128 бит), хотя поддержка этого более ограничена в языке Форт, поэтому требуется написать больше вспомогательного кода. Эта версия содержит код как для 64-битного (смешанный режим), так и для 128-битного режима (режим двойной точности).
  
   
   
   
   \ количество простых чисел < 64 

   
   
   
   \ количество простых чисел < 128 


   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   


   \ Тест Лукаса-Лемера одинарной точности для 64-битных целых чисел. 


   
   
   
   
   
   
   

   
   
   
   
   
   

   
   
   
   
   


   
   
   ( п -- п ) 

   
   
   

   
   
   

   

   
   
   
   

   
   
   
   
   
   
   
   
   
   
   

   
   


   
   
   ( -- ) 

   
   
   
   

   
   
   

   
   
   
   
   
   
   

   
   



   \ Тест двойной точности Лукаса-Лемера для 128-битных целых чисел. 


   
   
   
   

   
   
   
   
   
   

   
   
   ( н -- д ) 

   
   
   

   
   
   

   
   
   
   
   
   

   
   

   
   
   ( д1 д2 д3 -- д ) 
   
  \d1+d2 (модуль d3); д1, д2 < д3 

   
   
   
   
   
   \ d1 d2 d3 -- d1 d2 d3 d3-d1 

   
   
   
   \ если d2 < d3-d1, то модуль не вычитать. 

   
   
   

   
   
   
   

   
   
   ( д -- ж ) 

   
   
   
   
   

   
   
   ( d1 d2 d3 -- d ) 

   
   
   

   
   
   
   

   
   
   
   
   
   
   
   

   
   
   

   
   
   
   
   
   

   
   
   
   
   


   
   
   ( п -- п ) 

   
   
   

   
   
   

   

   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   

   
   


   
   
   ( -- ) 

   
   
   
   

   
   
   

   
   
   
   
   
   
   

   
   

  
 $ gforth ./mersenne.fs
Gforth 0.7.3, Copyright (C) 1995–2008 Free Software Foundation, Inc.
Gforth не предоставляет АБСОЛЮТНО НИКАКИХ ГАРАНТИЙ; для получения подробной информации введите «лицензия»
Введите «пока», чтобы выйти
.mersenne64 M2 M3 M5 M7 M13 M17 M19 M31 M61 ок
.mersenne128 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 ок
  
  
 Пусть  
 
 
 —  простое 
 нечётное. Число Мерсенна  
 
 
 
 простое тогда и только тогда, когда оно делит нацело  
 
 
 
 -й член  последовательности 
  
 
 
 
   [2] 
 
 ,
     LLT    
(p)
 ►Вход: простое нечётное число p
 S = 4
 k = 1
 M = 2       p    
    
 − 1
    До тех пока    
 k != p - 1    выполнять    

 S = ((S × S) − 2) mod M
 k += 1
    Конец цикла    

    Если    
 S = 0    выполнять    

    Возвратить    
 ПРОСТОЕ
    иначе    

    Возвратить    
 СОСТАВНОЕ
    Конец условия    

  
 Если числа  
 
 
 
 и  
 
 
 
 — простые, то  
 
 
 
 .
 От до
 Первым простым числом Мерсенна, обнаруженным на компьютере с помощью теста Люка-Лемера, стало ${M_{521}}$
 , найденное Рафаэлем Робинсоном 30 января 1952 года на базе лампового компьютера SWAC (Standards Western Automatic Computer).  Ниже вы видите блок памяти этого компьютера, содержащий 256 слов по 37 бит каждое.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
20-е простое число Мерсенна было обнаружено  Александром Гурвицем 
 в ноябре 1961 года в результате проведения 50-минутного теста Люка-Лемера на IBM 7090.  Ниже мы воспроизводим эти результаты (на это потребовалось около 151 секунд машинного времени на современном одноядерном ноутбуке).
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Одной из особенностей Wolfram Language, делающей его пригодным для такого рода работы, является его быстрая целочисленная арифметика.  Поиск простых чисел Мерсенна стал настоящим вызовом на рассвете эпохи компьютеризированного поиска.  Исследователи адаптировали методы быстрого преобразования Фурье для преобразования задачи умножения двух больших целых чисел в простое поэлементное произведение трансформированных цифр.  Быстрое умножение целых чисел необходимо для шага возведения в квадрат в тесте Люка-Лемера.  В Wolfram Language используются новейшие алгоритмы, оптимизированые для работы с точными целыми числами с миллиардами символов.  Например, убедимся, что последнее из них, — ${M_{4423}}$
 , — на самом деле простое число Мерсенна, и продемонстрируем все его цифры.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 Факторизация чисел Мерсенна
 Как мы уже видели, количество возможных множителей в разложении чисел вида ${2^p} - 1$
 согласно теореме множителей Мерсенна ограниченно.  Это позволило провести эффективный компьютеризированный поиск делителей больших чисел этой формы.  На момент написания этой статьи все числа Мерсенна (до ${2^{1201}} - 1$
 ) были полностью разложены на множители (иллюстрации можно найти  здесь 
 ).  Проект GIMPS также привел к открытию крупных множителей многих чисел Мерсенна в качестве побочного продукта проверки простоты чисел.  Новую статью, которая представляет собой современный подход к решению этой проблемы (наряду с 17 новыми факторизациями), можно найти  здесь 
 .  Наибольшее факторизованное число составило ${2^{1199}} - 1$
 ; его наименьший из найденных делителей имеет 76 десятичных цифр.  Его наименьший делитель равен 23.  Общее время, необходимое для того, чтобы получить этот результат составляет 7500 лет (речь о компьютерном времени).
Мы можем быстро найти несколько первых множителей ${2^{1201}} - 1$
 с помощью функции  FactorInteger 
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Все простые числа Мерсенна, обнаруженные на сегодняшний день, каталогизированы в Wolfram Language (до 44-го).  Доступ к этой информации обеспечивается функциями   MersennePrimeExponent 
 
 и   MersennePrimeExponentQ 
 
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
  
 LL(p)={
 my(m=Mod(4,1<<p-1));
 для (я = 3, р, м = м ^ 2-2);
 м==0
};

поиск()={
 печать("2^2-1");
 forprime(p=3,43112609,
 if(LL(p), print("2^"p"-1"))
 )
}; 
  Версия с пробным делением и быстрым модульным сокращением 
  
   /* ll(p): введите нечетное простое число 'p'. */ 

   /* возвращает '1', если 2^p-1 является простым числом Мерсенна. */ 

   
   
   

   
   /* пробное деление до разумной глубины (отношение времени tdiv/llt около 0,2) */ 

   
   
   

   
   
   
   
   

   
   
   
   

   

   
   /* Тест Лукаса-Лемера с быстрой модульной редукцией. */ 
   

   
   
   
   

   
   
   
   

   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   

   

   

   
   /* конец ll */ 




   
   
   

   
   
   
   

   
   
   

   

   
   %3dh, %2dmin, %2d,%03d мс 
   
   
   
   
   
   

   
   
   

   

   

   
   
   
   
   
   
   /* ll(p) -> d копирование из параллельного мира в реальный. */ 

   

   
   
   

   
   

   
   %3dh, %2dmin, %2d, %03d мс 
   
   
   
   
   
   

   

   

   
   /* конец запуска */ 



   
   
   /* если ll работает как скрипт */ 

  
 Скомпилировано с опцией gp2c: gp2c-run -g ll.gp.
 #1 M2 0ч, 0мин, 0,000 мс
#2 M3 0ч, 0мин, 0,000 мс
#3 M5 0ч, 0мин, 0,000 мс
#4 M7 0ч, 0мин, 0,000 мс
#5 M13 0ч, 0мин, 0,000 мс
#6 M17 0ч, 0мин, 0,000 мс
#7 M19 0ч, 0мин, 0,000 мс
#8 M31 0ч, 0мин, 0,000 мс
#9 M61 0ч, 0мин, 0,000 мс
#10 M89 0ч, 0мин, 0,000 мс
#11 M107 0ч, 0мин, 0,000 мс
#12 M127 0ч, 0мин, 0,000 мс
#13 M521 0ч, 0мин, 0,001 мс
#14 M607 0ч, 0мин, 0,001 мс
#15 M1279 0ч, 0мин, 0,007 мс
#16 M2203 0ч, 0мин, 0,030 мс
#17 M2281 0ч, 0мин, 0,033 мс
#18 M3217 0ч, 0мин, 0,079 мс
#19 M4253 0ч, 0мин, 0,163 мс
#20 M4423 0ч, 0мин, 0,186 мс
#21 M9689 0ч, 0мин, 1789 мс
#22 M9941 0ч, 0мин, 2022 мс
#23 M11213 0ч, 0мин, 2835 мс
#24 M19937 0ч, 0мин, 23858 мс
#25 M21701 0ч, 0мин, 35268 мс
#26 M23209 0ч, 0мин, 45233 мс
#27 M44497 0ч, 6мин, 53051 мс
#28 M86243 1ч, 3мин, 41811 мс
#29 M110503 2ч, 29мин, 14055 мс
#30 M132049 4ч, 42мин, 27694 мс
? ##
 *** последний результат: время процессора 37 часов, 31 минута, 41 619 мс, реальное время 4 часа, 42 минуты, 46 515 мс. 
 Мера адекватности выборки
 Мера адекватности выборки рассчитывается для каждого показателя как
  
 
 
 и указывает, насколько показатель пригоден для факторного анализа.
 Доказательство правильности
 Представленное здесь доказательство корректности этого теста проще, чем оригинальное доказательство, данное Лемером. Напомним определение
     
 
 Цель — показать, что  M 
   р 
 
 является простым  тогда и только тогда, когда 
     
 
     
 
     
 
 На последнем шаге используется     
 
 Эта закрытая форма используется как при доказательстве достаточности, так и при доказательстве необходимости.
 Предположим     
 
 Затем
     
 
 для некоторого целого числа  k 
 , так
     
 
 Умножение на     
 
 дает
     
 
  <span data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/11bf6306d9d9251a5811dcb27ca886a387c47d5d" data-alt="\omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad
" data-class="mwe-math-fallback-image-inline mw-invert">   
 
     
 
 Понятно, что это умножение замкнутое, т.е. произведение чисел из  X 
 сам находится в  X 
 . Размер  X 
 обозначается     
 
 Сейчас     
 
 и     
 
 , так
     
 
 в  Х 
 .
 Тогда по уравнению
     
 
 в  X 
 , и возведение в квадрат обеих сторон дает
     
 
 Таким образом     
 
 лежит в  X 
 * и имеет обратный     
 
 Кроме того, порядок  
 из     
 
 делит     
 
 Однако     
 
 , поэтому порядок не делится     
 
 Таким образом, порядок равен ровно     
 
 Порядок элемента не превышает порядка (размера) группы, поэтому
  <span data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bae8c85df7be62f85967a99478c3e3be2d4e592d" data-alt="2^{p}\leq |X^{*}|\leq q^{2}-1   
 
 Но  д 
 - наименьший простой делитель композита     
 
 , так
     
 
 Отсюда следует противоречие  <span data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f748a7175332e9cecf0d0f6c281069880a4def73" data-alt="2^{p}   
 
 . Следовательно,     
 
 является простым.
     
 
 Напротив, 2 представляет собой  квадратичный остаток 
 по модулю     
 
 поскольку     
 
 и так     
 
 На этот раз критерий Эйлера дает
     
 
 Объединение этих двух отношений эквивалентности дает
  <span data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/952171a3ad86a3de534dc9f109def1fb31e79f9d" data-alt="24^{\frac {M_{p}-1}{2}}\equiv \left(2^{\frac {M_{p}-1}{2}}\right)^{3}\left(3^{\frac {M_{p}-1}{2}}\right)\equiv
^{3}(-1)\equiv -1{\pmod {M_{p}}}." data-class="mwe-math-fallback-image-inline mw-invert">   
 
     
 
, где первое равенство использует  Биномиальную теорему в конечном поле 
 , который
     
 
 ,
, а второе равенство использует  малую теорему Ферма 
 , который
     
 
 для любого целого числа  a 
 . Значение     
 
 было выбрано так, что     
 
 Следовательно, это можно использовать для вычисления     
 
 на ринге  Х 
 как
     
 
 Остаётся только умножить обе части этого уравнения на     
 
 и используйте     
 
 , который дает
     
 
 Поскольку     
 
 равен 0 в  X 
 , это также 0 по модулю     
 
  
 Требование  нечётности 
  
 
 
 в основных критериях качества, так как  
 
 
 —  простое 
 , но  
 
 
 .
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 Один из подходов к доказательству, основанный на использовании  Функции Люка 
 :
  
 
 
  
 
 
 где  
 
 
 — корни  квадратного уравнения 
  
 
 
 с  дискриминантом 
  
 
 
 причём  
 
 
 и  
 
 
  взаимно просты 
 .
 1.  
 
 
 2.  
 
 
 3.  
 
 
 4. Если  
 
 
 ,  
 
 
 ,  
 
 
 и
  
 
 
 ,
 то
  
 
 
 5. Если  
 
 
 — простое, такое, что  
 
 
 взаимно просто с  
 
 
 , то  
 
 
 делит нацело  
 
 
 ,
 где  
 
 
 , а  
 
 
 —  символ Лежандра 
 .
  
 Из свойств 4. по модулю  
 
 
 
 при  
 
 
 
 ,  
 
 
 
 , следует:
  
 
 
 
 ,
 а по свойству 2.
  
 
 
 
 ,
  
 
 
 
  
 
 
 
  
 
 
 
 , поэтому если  
 
 
 
 — простое, то  
 
 
 
 и из последних двух свойств  
 
 
 
 делит
  
 
 
 
 Далее, из свойств 1.  и 2.
  
 
 
 
 ,
 но по свойству 3.
  
 
 
 
 ,
 то есть  
 
 
 
 делит  
 
 
 
 , а значит и  
 
 
 
 .
  
 Если  
 
 
 
 делит  
 
 
 
 , то из доказательства необходимости следует, что оно делит и  
 
 
 
 .  
 
 
 
 взаимно просто с  
 
 
 
 по свойству 1., а по свойству 2.  — делит  
 
 
 
 .  Но тогда каждый простой делитель числа  
 
 
 
 представим в виде  {\sqrt {N}}}">
 
 
 
 , то есть  
 
 
 
 — простое.
  
 LLR — это программа, которая выполняет LLR-тест.  Программа разработана Жаном Пене (Jean Penné).  Винсент Пене (Vincent Penné) модифицировал программу, чтобы можно было проверять простоту числа через интернет.  Программа может использоваться как для индивидуального поиска, но также включена в некоторые проекты  распределенных вычислений 
 , включая  Riesel Sieve 
 и  PrimeGrid 
 .
  
 Для  целого 
 числа  
 
 
 
 и числа Мерсенна  
 
 
 
 имеет место  сравнение по модулю 
  
 
 
 
 ,
 причём умножение на  
 
 
 
 по модулю  
 
 
 
 равносильно  левому циклическому сдвигу 
 на  
 
 
 
  бит 
 (если  <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d59e54fad8568e90715f2b10521d3e39bc45fca9" aria-hidden="true" alt="k
 
 
 
 , то сдвиг осуществляется в обратную сторону).
 Например, чтобы вычислить остаток от деления числа  
 
 
 
 на  
 
 
 
 , нужно исходное число преобразовать в двоичный вид:  
 
 
 
 , и, согласно теореме, разбивать  
 
 
 
 на две части каждый раз, когда оно превосходит  
 
 
 
 :
  
 
 
 
  
 The Kaiser–Meyer–Olkin criterion is calculated and returns values between 0 and 1.
  
 
 
 
 Here  
 
 
 
 is the correlation between the variable in question and another, and  
 
 
 
 is the partial correlation.
 Совершенные числа
 Существует интересная связь между простыми числами Мерсенна и совершенными числами.  Совершенное число 
 — это число, равное сумме всех своих делителей (отличных от самого числа).  Евклид предполагал, а Эйлер доказал, что все четные совершенные числа, имеют вид $P = {2^{p - 1}}\left( {{2^p} - 1} \right) = {2^{p - 1}}{M_p}$
 .  Функция Wolfram Language   PerfectNumberQ 
 
 проверяет, является ли число совершенным.  Продемонстрируем это свойство на ${M_{31}}$
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
  
 Тест Люка — Лемера — Ризеля является частным случаем проверки простоты порядка группы.  В тесте показывается, что некоторое число — простое в связи с тем, что некоторая группа имеет порядок, который был бы равен этому простому числу, для чего выявляется элемент группы, имеющий в точности нужный порядок.
 В тестах, подобных тестам Люка, для числа  
 
 
 
 используется мультипликативная группа квадратичного расширения целых по модулю  
 
 
 
 .  Если  
 
 
 
  — простое, порядок мультипликативной группы равен  
 
 
 
 , и она имеет подгруппу порядка  
 
 
 
 , для целей теста ищется  порождающее множество 
 этой подгруппы.
 Можно найти неитеративное выражение для  
 
 
 
 .
 Следуя модели теста Люка — Лемера, положим  
 
 
 
 и получим по индукции  
 
 
 
 .
 Рассмотрим 2   i 
 
 -ый элемент последовательности  
 
 
 
 .
 Если  a 
 удовлетворяет квадратному уравнению, это последовательность Люка, и она подчиняется выражению  
 
 
 
 .
 В действительности мы ищем  
 
 
 
 -ый элемент другой последовательности, но поскольку при децимации (выборка каждого  k 
 -го элемента) последовательности Люка получаем также последовательность Люка, мы можем выбирать множитель  k 
 путём выбора стартовой точки.
  
  1.   Для проверки простоты похожих на эти  чисел Прота 
      —  
     
     
     
     используется либо  Теорема Прота 
     (  вероятностный алгоритм 
     ), либо один из детерминированных алгоритмов, описанных Брилхартом, Лемером и Селфриджом в 1975 году — см.  Brillhart, Lehmer, Selfridge, 1975 
     
  3.    Riesel, 1994 
     , p. 194. 
 Люка и Лемер
 Следующим важным шагом стало открытие  Эдуардом Люка 
 метода для проверки простоты чисел данной формы.  Он использовал свой метод в 1876 году для проверки, является ли ${M_{127}}$
 (самое большое число Мерсенна "докомпьютерной" эпохи) простым.  В начале двадцатого века, когда основы двоичной арифметики и алгебры стали широко известны,  Дерек Генри Лемер 
 усовершенствовал метод Люка.  Полученный в результате тест  простоты чисел Люка-Лемера 
 обеспечивал эффективную проверку, если число данной формы являлось простым.  Проверка проводилась с помощью сравнения по модулю:
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Это означает, что $k$
 идентично числу, представленному его $p$
 битами низшего порядка, плюс — числами, представленными остальными битами.  Это соотношение может применяться рекурсивно до тех пор, пока  <img src="https://habrastorage.org/getpro/habr/post_images/03d/a0b/92e/03da0b92e858e6f0953a0e4769012127.svg" alt="$k
 .
Рассмотрим следующий пример.  Здесь мы покажем, что ТЕСТ ЛУКАСА ЛЕМЕРА
 для $k = {\text{1234567891}}$
 .  Обратите внимание, что ТЕСТ ЛУКАСА ЛЕМЕРА
 (23 бита низшего порядка) и ТЕСТ ЛУКАСА ЛЕМЕРА
 — означает, что остальные биты сдвинуты в крайнее нижнее положение.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Функция ниже задает этот метод для вычисления $k\bmod \left( {{2^p} - 1} \right)$
 с использованием только битовых операций (без деления).  Обратите внимание на то, что ${2^n} - 1$
 имеет двоичную форму ${111...111_2}$
 , при этом нет ни одного 0, и поэтому она также служит в качестве маски для $p$
 битов низшего порядка числа $k$
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Следующая функция реализует тест простоты Люка-Лемера (LLT).  Определим последовательность ${s_0} = 4$
 , ТЕСТ ЛУКАСА ЛЕМЕРА 0$" data-tex="inline">
 .  Тогда ${M_p} = {2^p} - 1$
 является простым тогда и только тогда, когда ${s_{p - 1}} \equiv 0\left( {\bmod {M_p}} \right)$
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Опыт показывает, что основное время выполнения этих функций тратится на целочисленную арифметику.
Чтобы проверить, является ли ${2^p} - 1$
 простым, лучше сначала проверять простоту на небольших простых делителях и выполнять другие проверки простоты.  Сначала мы используем теорему делителей простых чисел Мерсенна, закодированную в  checkMPDivisors 
 , а затем функцию  PrimeQ 
 .  Если это не сработает, применим тест Люка-Лемера.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Здесь мы представляем расширенную версию функции  PrimeQ 
 , которая применяет тест Люка-Лемера для больших чисел вида ${2^p} - 1$
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 Вариации и обобщения
  
 
 
 
 .
 Теорема множителей Эйлера и Мерсенна
 Первые важные достижения в области проверки на простоту принадлежат великому математику  Леонарду Эйлеру 
 , который незадолго до 1772 года уточнил, что ${M_{31}}$
 является простым.  Он сделал это, продемонстрировав, что любой простой делитель ${M_{31}}$
 должен быть равен 1 или 62 (mod 248).
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Такой относительно короткий список даже во времена Эйлера мог быть проверен с помощью пробного деления (вручную).  Ему принадлежит применение  теоремы Мерсенна 
 , в которой говорится, что если $q$
 является делителем ${M_p}$
 , то $q \equiv 1 \vee - 1\left( {\bmod 8} \right)$
 , $q \equiv 1\left( {\bmod p} \right)$
 и $q \equiv 2kp + 1$
 для некоторого целого положительного числа $k$
 .  Эти факты значительно ограничивают количество возможных делителей ${M_p}$
 .  С помощью функций, представленных ниже, демонстрируется использование этой теоремы с целью предоставления списка возможных делителей ${M_p}$
 , меньших, чем $\sqrt {{2^p} - 1} $
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Мы используем эти функции, чтобы быстро найти делитель ${2^{41}} - 1$
 .  Обратите внимание, что $q$
 является делителем ${2^{p}} - 1$
 тогда и только тогда, когда ${2^p} \equiv 1\left( {\bmod q} \right)$
 .  Это дает возможность использовать функцию   PowerMod 
 
 , что обеспечивает эффективное возведение в степень по модулю.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Ниже приводится число Мерсенна с 161649 знаками:
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 29-е число Мерсенна
 Поскольку теперь нам требуется более серьезное компьютерное время, мы также производим отметку времени для каждого прогона.  Теперь мы проверяем диапазон $87557 \leqslant p \leqslant 110597$
 .  Через 1 час и 44 минут компьютер показал: $\# 29 = {M_{110503}}$
 .  Это число впервые было обнаружено 29 января 1988 года Уокер Колкуиттом и Люком Уэлшем (суперкомпьютер NEC DX-2; статью можно найти  здесь 
 ).
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
  
  
   

   

   

   


   


   
   
   

   

   
   
   
   
   
   

   
   
   
   
   
   

   
   
   
   
   
   

   
   
   
   
   
   


   
   
   
   
   
   

   

   
   
   
   
   
   
   
   
   
   

   
   

   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   

   
   

   


   
   
   
   
   

   

   
   
   
   
   

   
   
   
   
   
   
   

   
   
   

   

   

   
   

   


   
   
   
   

   

   
   
   
   

   
   
   
   
   

   
   
   

   

   

   


  
 (Выполнять только до 11213)
 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213
  
 Функция мод, ( %
 ) имеет вычислительную стоимость, эквивалентную операции деления. В этом случае комбинация операторов «и», сдвигов и сложений может заменить функцию mod. Еще одним изменением является создание списка возможных чисел Мерсенна в порядке убывания, при этом необходимо сначала начать более трудоемкие вычисления. Это позволяет избежать долгих вычислений, которые происходят сами по себе в конце Parallel.For
 очередь. Также добавлен шаг пробного деления, переведенный с  Rust 
 и  С 
 версии.
  
   

   

   

   


   
   
   


   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   


   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   

   
   // пробное подразделение 

   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   

   
   // главное событие 

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   
   
   
   
   

   

   
   
   
   
   
   
   
   

   
   
   
   

   
   
   

   


  
 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213
00:00:26.8747764 
  
  
   

   


   
   
   


   
   
   
   
   
   

   
   

   


   
   

   
   
   
   
   
   
   
   

   
   
   
   
   
   
   
   

   

   
   
   
   
   
   
   
   
   
   

   


   
   
   
   
   
   



   


   
   

   
   

   
   

   
   
   

   
   
   

   
   

   

   
   //std::cout &lt <  "P" < <  check < <  " " < <  std::flush;     

       
       
       

       

       

       
       
       
       
       
       
       
       
       

       

       


  
 (Incomplete;   It takes a long time.)
  M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209 M44497
  
  
 Simple arbitrary-precision version:
        
       
       
       
       
       

       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       


       
       
       
       
       

       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       

       
       
       

  
        
       
       
       

       
       
       
       
       
       
       
    "Exponent must be > = 2"    

       
       
       
       
       
       
       
       


       
       
       
       
       
       

       
       
       

       
       
       
       
       
       
       
       
       
       

       
       
       
       
       
       
       
       
       
       
       
       

       

       
       
       
       
       

  
 Version using library folding function (way shorter and faster than the above):
        
       
       
       

       
       
       
       
       
       
       
    "Exponent must be > = 2"    

       
       
       
       
       
       
       
       


       
       
       

       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       

       

       
       
       

  
  
  Translation of 
 :  VBScript 
        
m = 15
n = 1
For j = 2 To m
 If j = 2 Then
 s = 0
 Else
 s = 4
 EndIf
 n = (n + 1) * 2 - 1
 For i = 1 To j - 2
 s = (s * s - 2)  % n
 Next i
 If s = 0 Then Print "M"; j
Next
  
 21-е, 22-е и 23-е числа Мерсенна
 Перейдем к переоткрытию 21-го, 22-го и 23-го чисел Мерсенна (будем обозначать их далее в форме вида $\# 21$
 ): $\# 21 = {M_{9689}}$
 , $\# 22 = {M_{9941}}$
 , $\# 23 = {M_{11213}}$
 ; Все они были обнаружены Дональдом Гиллисом, который запускал LLT на ILLIAC II всю весну 1963 года (см.  здесь 
 ).  Для проверки всех чисел вида ${2^p} - 1$
 для простых чисел в промежутке $7927 \leqslant p \leqslant 17389$
 нам понадобилось около 6 минут.
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 ТЕСТ ЛУКАСА ЛЕМЕРА
 Доказательство правильности
 Представленное здесь доказательство корректности этого теста проще, чем оригинальное доказательство, данное Лемером. Напомним определение
  
 
 
 Цель — показать, что  M 
   р 
 
 является простым  тогда и только тогда, когда 
  
 
 
  
 
 
  
 
 
 На последнем шаге используется  
 
 
 Эта закрытая форма используется как при доказательстве достаточности, так и при доказательстве необходимости.
 Предположим  
 
 
 Затем
  
 
 
 для некоторого целого числа  k 
 , так
  
 
 
 Умножение на  
 
 
 дает
  
 
 
  <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/11bf6306d9d9251a5811dcb27ca886a387c47d5d" aria-hidden="true" alt="\omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad
">
 
 
  
 
 
 Понятно, что это умножение замкнутое, т.е. произведение чисел из  X 
 сам находится в  X 
 . Размер  X 
 обозначается  
 
 
 Сейчас  
 
 
 и  
 
 
 , так
  
 
 
 в  Х 
 .
 Тогда по уравнению
  
 
 
 в  Х 
 , и возведение в квадрат обеих сторон дает
  
 
 
 Таким образом  
 
 
 лежит в  X 
 * и имеет обратный  
 
 
 Кроме того, порядок  
 из  
 
 
 делит  
 
 
 Однако  
 
 
 , поэтому порядок не делится  
 
 
 Таким образом, порядок ровно  
 
 
 Порядок элемента не превышает порядка (размера) группы, поэтому
  <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bae8c85df7be62f85967a99478c3e3be2d4e592d" aria-hidden="true" alt="2^{p}\leq |X^{*}|\leq q^{2}-1
 
 
 Но  д 
 - наименьший простой делитель композита  
 
 
 , так
  
 
 
 Отсюда следует противоречие  <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f748a7175332e9cecf0d0f6c281069880a4def73" aria-hidden="true" alt="2^{p}
 
 
 . Следовательно,  
 
 
 является простым.
  
 
 
 Напротив, 2 представляет собой  квадратичный остаток 
 по модулю  
 
 
 с  
 
 
 и так  
 
 
 На этот раз критерий Эйлера дает
  
 
 
 Объединение этих двух отношений эквивалентности дает
  <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/952171a3ad86a3de534dc9f109def1fb31e79f9d" aria-hidden="true" alt="24^{\frac {M_{p}-1}{2}}\equiv \left(2^{\frac {M_{p}-1}{2}}\right)^{3}\left(3^{\frac {M_{p}-1}{2}}\right)\equiv
^{3}(-1)\equiv -1{\pmod {M_{p}}}.">
 
 
  
 
 
 где первое равенство использует  Биномиальную теорему в конечном поле 
 , который
  
 
 
 ,
, а второе равенство использует  малую теорему Ферма 
 , который
  
 
 
 для любого целого числа  a 
 . Значение  
 
 
 было выбрано так, что  
 
 
 Следовательно, это можно использовать для вычисления  
 
 
 на ринге  Х 
 как
  
 
 
 Остаётся только умножить обе части этого уравнения на  
 
 
 и используйте  
 
 
 , который дает
  
 
 
 С  
 
 
 равен 0 в  X 
 , это также 0 по модулю  
 
 
 Поиск стартового значения
  
 
 
 и  
 
 
 .
 Для проверки необходимо лишь несколько измерений  
 
 
 (5, 8, 9 или 11 перекрывают 85 %).
  
 Алгоритм очень похож на тест Люка — Лемера, но начинается со значения, составляющего его от  
 
 
 . Для алгоритма используется  по очереди Люка 
  
 
 
 , задаваемая для  0}">
 
 
 формулой:
  
 
 
 .
  
 
 
 это просто в том и только в том случае, когда оно делит  
 
 
 .
 Visual Basic. НЕТ
  
   
   

   
   
   
   
   
   
   
   
   
   

   
   
   
   

   
   
   
   
   

   
   
   
   
   

   
   
   

   
   
   

   
   
   
   
   
   

   
   
   
   
   

   
   
   

   

   
   
   

   
   

   
   
   
   
   
   
            
            
            

            
            
            
            
            
            
            
            

            
            
            
            
            
            
            
            
            

            
            

            
            
            
            
            

            
            
            
            
            
            
            
            
            

            
           

           
           

           
           

           

  
  М2 М3 М5 М7 М13 М17 М19 М31 
  Пример в R 
   
  
  
  
  
  
  
        
       
       

       
       
       

       
       
       

       
       
       
       
       

       
       
       
       
       
       

       
       
       
       

  
  
 This version is very speedy and is bounded.
        
       
       
       
       
       

       
       
       
       
       
       
       
       
       
       
       
       
       
       
                 
                           
                           
                           
                           

                           
                           
                           
                           
                           
                         
                       
                       
                       

                       
                       
                       
                       


                       
                       
                       
                       
                       
                       
                       
                       
                       
                       
                       
                       
                       
                       

  
  This version is unbounded (and timed):
 
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 
      
      
      
      
 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 
  I’ll see what this gets.
 
  27-е и 28-е числа Мерсенна 
 
 Далее мы проверили диапазон 
 , чтобы найти число 
 ; Оно было обнаружено в апреле 1979 года Гарри Нельсоном и его командой (они использовали суперкомпьютер Cray-1).  Наш поиск завершился за 15 минут. 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
 
Следующее число Мерсенна, 
 .  Оно был открыто в сентябре 1982 года Дэвидом Словински — также на Cray-1.  Этот суперкомпьютер весил около 5 тонн и потреблял около 115 киловатт электроэнергии, а его вычислительная производительность достигала 160  мегафлопс 
 .  Он поставлялся с 1 миллионом 64-разрядных слов памяти (8 мегабайт), а стоил около 16000000$ в сегодняшних ценах.  Ниже показана деталь его системы охлаждения.  Для сравнения:  Raspberry Pi 
 весит несколько унций, работает на 4 Вт, обеспечивает около 410 мегафлопс и снабжен 1Гб оперативной памяти, и это все — за 40$.  А еще он поставляется сразу с системой  Mathematica 
 . 
  
 
 
  
 
 
 
Число 
 содержит 25962 цифры.  Это значение мы нашли за 1 час и 14 минут (на моем ноутбуке, а не на Raspberry Pi), проводя испытания в диапазоне 
 .
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 Простые числа Мерсенна и тест Люка-Лемера
  Время на прочтение
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 
Выражаю огромную благодарность  Полине Сологуб 
 за помощь в переводе и подготовке публикации 
 Алгоритмы поиска простых чисел
  Время на прочтение
 
Натуральное число называется простым, если оно имеет только два различных делителя: единицу и само себя.  Задача поиска простых чисел не дает покоя математикам уже очень давно.  Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом.  В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.
  
 Решето Эратосфена
  Решето Эратосфена 
 — алгоритм, предложенный древнегреческим математиком Эратосфеном.  Этот метод позволяет найти все простые числа меньше заданного числа  n 
 .  Суть метода заключается в следующем.  Возьмем набор чисел от 2 до  n 
 .  Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2.  Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3.  Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до  n 
 .  После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.
Алгоритм можно несколько оптимизировать.  Так как один из делителей составного числа  n 
 обязательно $\leqslant \sqrt{n}$
 , алгоритм можно останавливать, после вычеркивания чисел делящихся на $\sqrt{n}$
 .
Иллюстрация работы алгоритма из Википедии:
 
 
 
 Сложность алгоритма составляет 
 , при этом, для хранения информации о том, какие числа были вычеркнуты требуется 
 памяти. 
 
Существует ряд оптимизаций, позволяющих снизить эти показатели.  Прием под названием  wheel factorization 
 состоит в том, чтобы включать в изначальный список только числа  взаимно простые 
 с несколькими первыми простыми числами (например меньше 30).  В теории предлагается брать первые простые примерно до 
 .  Это позволяет снизить сложность алгоритма в 
 раз.  Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование.  Изначальный набор чисел делится на сегменты размером 
 и для каждого сегмента решето Эратосфена применяется по отдельности.  Потребление памяти снижается до 
 . 
  Решето Аткина 
 
 Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название  Решето Аткина 
 .  Этот способ основан на следующих трех свойствах простых чисел. 
 
Если  n 
 — положительное число, не кратное квадрату простого числа и такое, что 
 .  То  n 
 — простое, тогда и только тогда, когда число корней уравнения 
 нечетно. 
 
Если  n 
 — положительное число, не кратное квадрату простого числа и такое, что 
 .  То  n 
 — простое, тогда и только тогда, когда число корней уравнения 
 нечетно. 
 
Если  n 
 — положительное число, не кратное квадрату простого числа и такое, что 
 .  То  n 
 — простое, тогда и только тогда, когда число корней уравнения 
 нечетно. 
 
Доказательства этих свойств приводятся в  этой статье 
 . 
 
На начальном этапе алгоритма решето Аткина представляет собой массив  A 
 размером  n 
 , заполненный нулями.  Для определения простых чисел перебираются все 
 .  Для каждой такой пары вычисляется $4x^2+y^2$
 , $3x^2+y^2$
 , $3x^2-y^2$
 и значение элементов массива $A[4x^2+y^2]$
 , $A[3x^2+y^2]$
 , $A[3x^2-y^2]$
 увеличивается на единицу.  В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа.  На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.
Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют $O(n)$
 .  При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до $O(n / \log\log n)$
 , а потребление памяти до $O(\sqrt{n})$
 .
 Числа Мерсенна и тест Люка-Лемера
 Конечно при таких показателях сложности, даже оптимизированное решето Аткина невозможно использовать для поиска по-настоящему больших простых чисел.  К счастью, существуют быстрые тесты, позволяющие проверить является ли заданное число простым.  В отличие от алгоритмов решета, такие тесты не предназначены для поиска всех простых чисел, они лишь способны сказать с некоторой вероятностью, является ли определенное число простым.
Один из таких методов проверки —  тест Люка-Лемера 
 .  Это детерминированный и безусловный тест простоты.  Это означает, что прохождение теста гарантирует простоту числа.  К сожалению, тест предназначен только для чисел особого вида $2^p-1$
 , где  p 
 — натуральное число.  Такие числа называются числами Мерсенна.
Тест Люка-Лемера утверждает, что число Мерсенна $M_p=2^p-1$
 простое тогда и только тогда, когда  p 
 — простое и $M_p$
 делит нацело $(p-1)$
 -й член последовательности $S_k$
 задаваемой рекуррентно: $S_1=4, S_k=S_{k-1}^2-2$
 для ТЕСТ ЛУКАСА ЛЕМЕРА 1$» data-tex=»inline»>
 .
Для числа $M_p$
 длиной  p 
 бит вычислительная сложность алгоритма составляет ${\displaystyle O(p^{3})}$
 .
Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна.  Самое большое известное простое число на сегодня — $2^{82,589,933}-1$
 , его десятичная запись состоит из 24,862,048 цифр.  Полюбоваться на эту красоту можно  здесь 
 .
 Теорема Ферма и тест Миллера-Рабина
 Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел.  Одним из таким способов является  тест простоты Ферма 
 .  Он основан на малой теореме Ферма, которая гласит, что если  n 
 — простое число, то для любого  a 
 , которое не делится на  n 
 , выполняется равенство $a^{n-1}\equiv 1{\pmod {n}}$
 .  Доказательство теоремы можно найти на  Википедии 
 .
Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений  a 
 , если хотя бы для одного из них выполняется неравенство $a^{n-1} \not\equiv 1 \pmod n$
 , то число  n 
 — составное.  В противном случае,  n 
 — вероятно простое.  Чем больше значений  a 
 использовано в тесте, тем выше вероятность того, что  n 
 — простое.
К сожалению, существуют такие составные числа  n 
 , для которых сравнение $a^{n-1}\equiv 1{\pmod {n}}$
 выполняется для всех  a 
 взаимно простых с  n 
 .  Такие числа называются  числам Кармайкла 
 .  Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма.  Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.
Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа  p 
 не существует других корней уравнения $x^2 \equiv 1 \pmod p$
 , кроме 1 и -1.  Тест Миллера-Рабина перебирает несколько значений  a 
 и проверяет выполнение следующих условий.
Пусть  p 
 — простое число и $p-1=2^sd$
 , тогда для любого  a 
 справедливо хотя бы одно из условий:
  1.  Существует целое число  r < s 
     такое, что $a^{2^{r}d}\equiv -1{\pmod {p}}$
 По теореме Ферма $a^{p-1}\equiv1\pmod p$
 , а так как 
 из свойства о корнях уравнения 
 следует что если мы найдем такое  a 
 , для которого одно из условий не выполняется, значит  p 
 — составное число.  Если одно из условий выполняется, число  a 
 называют свидетелем простоты числа  n 
 по Миллеру, а само число  n 
 — вероятно простым.
 
Чем больше свидетелей простоты найдено, тем выше вероятность того, что  n 
 — простое.  Согласно теореме Рабина вероятность того, что случайно выбранное число  a 
 окажется свидетелем простоты составного числа составляет приблизительно $1/4$
 .
Следовательно, если проверить  k 
 случайных чисел  a 
 , то вероятность принять составное число за простое $\approx(1/4)^k$
 .
Сложность работы алгоритма $O(k\log^3p)$
 , где  k 
 — количество проверок.
Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел.  Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей  работе 
 , этого не всегда оказывается достаточно.
Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.
 Тест Люка и Тест Baillie–PSW
 Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест  Baillie–PSW 
 .  Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест.  За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30.  Приз пока так и не был востребован.
Ряд исследователей  проверили 
 все числа до $2^{64}$
 и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW.  Поэтому, для чисел меньше $2^{64}$
 тест считается детерминированным.
Суть теста сводится к последовательной проверке числа на простоу двумя различными методами.  Один из этих методов уже описанный выше тест Миллера-Рабина.  Второй —  тест Люка на сильную псевдопростоту 
 .
  Тест Люка на сильную псевдопростоту 
  Последовательности Люка 
 — пары рекуррентных последовательностей $\{U_{n}(P,Q)\}, \{V_{n}(P,Q)\}$
 , описываемые выражениями:
 ${\displaystyle U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1,\quad U_{n+2}(P,Q)=P\cdot U_{n+1}(P,Q)-Q\cdot U_{n}(P,Q),\,n\geq 0}$
 
 ${\displaystyle V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P,\quad V_{n+2}(P,Q)=P\cdot V_{n+1}(P,Q)-Q\cdot V_{n}(P,Q),\,n\geq 0}$
 
 Пусть $U_n(P,Q)$
 и $V_n(P,Q)$
 — последовательности Люка, где целые числа P и Q удовлетворяют условию ${\displaystyle D=P^{2}-4Q\neq 0}$
Вычислим  символ Якоби 
 : $\left({\frac {D}{p}}\right)=\varepsilon$
 .
Найдем такие  r, s 
 для которых выполняется равенство $n-ε=2^rs$
Для простого числа  n 
 выполняется одно из следующих условий:
  1.   n 
     делит $U_s$
  2.   n 
     делит $V_{2^js}$
     для некоторого  j < r 
 В противном случае  n 
 — составное.
Вероятность того, что составное число  n 
 успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15.  Следовательно, после применения теста  k 
 раз, эта вероятность составляет $(4/15)^k$
 .
Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число  p 
 прошло оба теста, оно простое.  Именно на этом свойстве основывается тест Baillie–PSW.
 Заключение
 В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел.  К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до $10^8$
 .  Затем для каждого числа  p 
 из списка, с помощью теста Люка-Лемера, на простоту проверяется 
 .
 
Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число  a 
 и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW.  Согласно  теореме о распределении простых чисел 
 , у случайно выбранного числа от 1 до  n 
 шанс оказаться простым примерно равен 
 .  Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов. 
  P. S.  Исходники 
 
 Реализацию всех описанных алгоритмов на Go можно посмотреть на  GitHub 
 . 
  24-е, 25-е и 26-е числа Мерсенна 
 
 Далее мы расширяем поиск, чтобы найти 
 , 
 , 
 .  Последнее из них было обнаружено в феврале 1979 г.  Лэндоном Куртом Ноллом и Лорой Никель.  Они искали в диапазоне от ${M_{21001}}$
 до ${M_{24499}}$
 на суперкомпьютере CDC Cyber 174 (почитать об этом можно  здесь 
 ).  Наши расчеты становятся более долгими, так что мы начинаем использовать параллельную обработку.  Поскольку тесты независимы, для ускорения работы мы можем использовать   ParallelMap 
 
 .  Проверка диапазона $17393 \leqslant p \leqslant 27449$
 занимает приблизительно три с половиной минуты (используются 4 ядра).
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
Обратите внимание на то, что специализированный тест Люка-Лемера значительно быстрее, чем более общая функция  PrimeQ 
 (для данных чисел Мерсенна).
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
 
 ТЕСТ ЛУКАСА ЛЕМЕРА
Оцените статью
© 2024 EDU.VSU.RU - Электронный университет ВГУ