Какие методы существуют для проверки простоты числа в компьютерной науке?

В компьютерной науке существуют детерминированные и вероятностные методы проверки простоты числа. journal.tusur.ru infourok.ru

Детерминированные методы дают гарантированно точный ответ о простоте числа, но имеют большую вычислительную сложность. journal.tusur.ru Некоторые из них:

• Перебор делителей. spravochnick.ru infourok.ru Алгоритм определяет простоту числа путём полного перебора всех возможных потенциальных делителей. infourok.ru На практике не применяется, так как требует больших вычислительных мощностей. spravochnick.ru
• Метод Вильсона. spravochnick.ru Натуральное число больше единицы будет простым только в определённых случаях. spravochnick.ru
• Алгоритм Поклингтона. spravochnick.ru

Вероятностные методы позволяют определить простоту числа, но с некоторой вероятностью ошибки. journal.tusur.ru infourok.ru Некоторые из них:

• Тест Рабина–Миллера. journal.tusur.ru Применяется в криптографической системе RSA, а также в большинстве математических пакетов. journal.tusur.ru
• Тест Соловея–Штрассена. libeldoc.bsuir.by infourok.ru В каждой итерации выбирается случайное число, и если НОД (a, n) > 1, то число n — составное. infourok.ru Если сравнение выполняется, то a — свидетель простоты числа n. infourok.ru
• Тесты с использованием эллиптических кривых. libeldoc.bsuir.by Являются одними из самых быстрых из известных методов проверки числа на простоту. libeldoc.bsuir.by

Также существуют истинные тесты, которые позволяют точно определить простоту числа, но работают лишь для ряда заранее определённых чисел. libeldoc.bsuir.by Некоторые из них:

• Тест Люка. libeldoc.bsuir.by Основан на одноимённой теореме, работает за полиноминальное время. libeldoc.bsuir.by
• Тест Адлемана — Померанса — Румели. libeldoc.bsuir.by Универсальный тест, может быть применим на практике в связи с медленнорастущей сложностью. libeldoc.bsuir.by
• Тест Агравала — Каяла — Саксены. libeldoc.bsuir.by Основан на обобщённой теореме Ферма, полиномиален, универсален, детерминирован и безусловен. libeldoc.bsuir.by