Сказать "Спасибо"
Свойства отдельных алгоритмов, возможность их использования в криптографии
| Название | Тип теста | Сложность | Где используется |
|---|---|---|---|
| Пробное деление | детерминированный | экспоненциальная | В чистом виде не используется, из-за большой вычислительной сложности. Пробное деление на маленькие простые числа используется как один из шагов многих тестов. |
| Ферма | вероятностный | Ячейка 2*3 | В чистом виде нигде не используется. Может использоваться на начальных стадиях проверки для больших чисел |
| Леманна | вероятностный | Ячейка 2*3 | Не используется - хуже аналогичного теста Миллера-Рабина |
| Рабина-Миллера | вероятностный | полиномиальная | В чистом виде может использоваться в криптосистемах с открытым ключом для построения простых ключей длиной 512, 1024 и 2048 бит. Но в большинстве случаев эта проверка вытеснена объединенным тестом. |
| Миллера | детерминированный | Ячейка 2*3 | На практике не используется, так как пока не доказана расширенная гипотеза Рабина. |
| Объединенный(Р-М+пробное деление) | вероятностный | Ячейка 2*3 | В криптосистемах с открытым ключом для построения простых ключей длиной 512, 1024 и 2048 бит |
| Лукаса | детерминированный | Ячейка 2*3 | Для получения больших простых чисел определенного вида |
| Поклингтона | детерминированный | Ячейка 2*3 | Для получения больших простых чисел с частично известной факторизацией  . Также на основании теоремы аналогичной этой построены тесты APR и ECPP.
|
| Пепина | детерминированный | полиномиальная от длины числа 
| Для получения больших простых чисел Ферма. |
| Прота | детерминированный | Ячейка 2*3 | Для получения больших простых чисел определенного вида. |
| Лукаса-Лемера | детерминированный | Ячейка 2*3 | Для получения больших простых чисел Мерсенна. |
| APR | детерминированный | Ячейка 2*3 | В качестве детерминированной быстрой проверки на простоту. |
| ECPP | детерминированный | Ячейка 2*3 | В качестве детерминированной быстрой проверки на простоту. |
| AKS | детерминированный | Ячейка 2*3 | В качестве детерминированной полиномиальной проверки на простоту. |
Источник
Кучин Эссе по курсу "Защита информации" Обзор проверок на простоту
(c) Источник
