Операция "Раздолбай"

Свойства отдельных алгоритмов, возможность их использования в криптографии

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

Источник

Кучин Эссе по курсу "Защита информации" Обзор проверок на простоту
(c) Источник


Система Orphus

Комментарии (показать)