Тест на простоту чисел вида 10^n + k

Question

У меня есть некоторые числа в форме 10^N + K, где N составляет около 1000, а K действительно мало (ниже 500). Я хочу проверить эти числа на простоту. В настоящее время я использую тест Ферма по базе 2, перед которым проверяются небольшие факторы (<10000).

Тем не менее, это довольно медленно для моих целей. Есть ли алгоритм быстрее, чем это? Можно ли как-то использовать эту особую форму?

Также, может быть, если два числа отличаются только по K, возможно ли проверить эти два числа немного быстрее?

Answer 1

Если K имеет множитель 2 или 5, то 10^N + K является составным. Это позволяет быстро протестировать небольшое количество. Большие простые числа таковы, что P mod 6 = 1 или 5. Вы можете использовать это, чтобы исключить 2/3 возможных значений K. Немного поработав, вы можете настроить колесо 2-4, чтобы избежать большого разделения:

increment <- either 2 or 4 as required
repeat
  K <- K + increment
  increment <- 6 - increment
  if (K mod 5 = 0) then 
    continue 
  endif
until (isPrime(10^N + K) or (K > 500))

Пробный факторинг до 10000, если штраф. Вы сначала строите список простых чисел до 10 000? Используйте Сито Эратосфена, чтобы создать список и просто считать цифры.

Запуск Fermat Test Base 2 - хорошее начало, он довольно быстро находит множество композитов.

После этого вам нужно реализовать вероятностный тест Миллера-Рабина и запускать его достаточно много раз, чтобы повысить вероятность отказа вашего оборудования, а не составного числа.

Answer 2

Также, может быть, если два числа отличаются только по K, возможно ли проверить эти два числа немного быстрее?

Чтобы проверить простые числа в относительно небольшом интервале, например, [10^N+ K₁, 10^N+ K₂], вы можете использовать сито эратостены для проверки делимости на небольшие числа.

Остальные главные кандидаты могут быть проверены с помощью вероятностного теста, такого как Миллер-Рабин.