Какие свидетели мне нужны для теста Рабина-Миллера на числа до 10¹⁸?
Какого набора свидетелей достаточно, чтобы критерий Миллера-Рабина был верным для всех чисел до 10¹⁸? Я знаю, что использование простых чисел до 17 в качестве свидетелей достаточно для n < 341550071728321.
3 ответа
Согласно этой странице записи, набор из 7 баз SPRP: {2, 325, 9375, 28178, 450775, 9780504, 1795265022} достаточно для детерминированного теста, по крайней мере, n = 2^64 ( > 10^19),
Если вы готовы использовать тест Билли-Вагстаффа вместо теста Миллера-Рабина, он был сертифицирован как безошибочный при классификации простых чисел до 2^64. Кодирование не намного сложнее, функция выполняется быстрее, чем тест Миллера-Рабина, и нет известных ошибок классификации.
Согласно OEIS, использование свидетелей до 23 достаточно для номеров до 3825123056546413051