Простые числа Мерсенна и тест Люка-Лемера

Насчет GIMPS — есть более продвинутый проект на базе распределенных вычислений, PrimeGrid www.primegrid.com. Они там ищут несколько разных форм простых чисел — числа Прота, например, m*2ⁿ+1.

Либо тут опечатка, либо с эффективностью что-то не то.

Я посмотрел статью, на которую в тексте приводили ссылку.

Theorem.
If S(1) = 4 and S(n+1) = S(n)^2-2 then Mp is prime if and only if S(p-i) = 0 (mod Mp).
The test takes about 50 minutes of machine time for p = 4423

Я так понимаю, 50 минут уходило на то, чтобы для одного фиксированного p, взять Mp=2^p-1 и потом вычислить по его модулю S(p-1).

Что именно делают и меряют в wolfram alpha — мне не понятно.

Я попробовал простое решение "в лоб" на Scala — оно перебирает все простые числа до p=5000 за 30 секунд.

  val start = System.currentTimeMillis()
  var count = 0

  for (p <- 2 to 5000 if BigInt(p).isProbablePrime(20)) {
    val mp = BigInt(2).pow(p) - 1
    if (mp.isProbablePrime(20)) {
      count += 1
      println(s"$count numbers found, time = ${System.currentTimeMillis() - start}ms")
      println(s"2^$p - 1 = $mp")
    }
  }

Ещё попробовал алгоритм Люка-Лермера, для p = 4423 проверяет за 0.2 секунды. Получается, в 15000 раз быстрее, чем за 50 минут)
Перебор для всех простых p от 2 до 5000, как ни странно, у меня работает за те же 30 секунд.

тест Люка-Лермера на википедии

  def lucasLehmer(p: Int): Boolean = {
    var S = BigInt(4)
    val mp = BigInt(2).pow(p) - 1
    for (k <- 1 until (p - 1)) {
      S = (S * S - 2) mod mp
    }
    S == 0
  }

  val start = System.currentTimeMillis()
  lucasLehmer(4423)
  println(s"time = ${System.currentTimeMillis() - start}ms")