Neuroware
@Neuroware
Программист в свободное от работы время

Каким алгоритмом можно проверить Большое число на простоту?

Есть ли методы гарантированной проверки числа на простоту без необходимости полного "перебора"?
Везде встречаются либо метод "поделить на все числа меньше данного" либо вероятностные (не дают гарантии коррекности), другого способа определить нет?
Если для чисел до 100 знаков можно еще "перебрать" все хотябы до половины, то с числами в сотни тысяч знаков это бессмысленная затея, мне казалось должны быть способы определить подобное без необходимости совершать 10^100500 операций.
  • Вопрос задан
  • 2436 просмотров
Решения вопроса 1
@SeptiM
Расклад примерно такой. Пусть n -- длина числа, т.е. обычный перебор работает за 2^{c * n}.

1) Вероятностный тест Рабина-Миллера можно реализовать за O(k n^2 log n), где k -- число попыток. Вероятность ложноположительной ошибки 4^-k. При k=100 это значение настолько безумно мало, что скорее в вашей программе найдется критический баг, процессор сделает ошибку в вычислениях и взломщик выиграет в лотерею и все это одновременно, чем число окажется составным.

2) Детерминированный AKS (en.wikipedia.org/wiki/AKS_primality_test). Работает за O(n^{6 + eps}). Интересен скорее теоретически.

3) Эллиптический тест на простоту (en.wikipedia.org/wiki/Elliptic_curve_primality). Эмпирически работает за O(n^5). Интересен тем, что в случае успеха возвращает сертификат простоты.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
@kir_vesp
Web Developer
Как вариант: поделить на все простые числа, не превышающие квадратного корня из данного числа.
Ответ написан
honor8
@honor8
Принципы быстродействия VBA в описании
методы гарантированной проверки

Математики очень плохо дружат с псевдоязыками, но алгоритм описан в тесте AKS.

b57ef5f35bb3412cbb1f8669dd4e4a7f.jpg
Вместо перебора делителей можно использовать http://ru.wikipedia.org/wiki/Признаки_делимости
Ответ написан
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
Быстро это сделать не выйдет. Не спроста же большие простые числа используют в криптографии. Даже если принять во внимание тот факт, что вы не пытаетесь разложить это добро на множители.
Ответ написан
struggleendlessly
@struggleendlessly
.net Senior developer
на сколько я помню, это очень тяжелая задача, и за нахождение простого числа в миллиард знаков дают около полумиллиона долларов. Дерзайте)
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы