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

Question

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

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

Также, может быть, если два числа отличаются только по 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 ₂ ] Вы можете использовать сито Эратостен для проверки делимости на небольшие числа.

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