СРАВНЕНИЕ АЛГОРИТМОВ ГЕНЕРАЦИИ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ В КРИПТОГРАФИИ

Аннотация

В статье рассматриваются три алгоритма генерации больших простых чисел, применяемых в качестве входных параметров современных криптографических систем. Представлены алгоритмы, основанные на тестах простоты Миллера-Рабина, на теоремах Поклингтона и Диемитко, и позволяющие генерировать простые числа p с фиксированной длиной и известной факторизацией числа p-1. Проводится сравнительный анализ каждого из алгоритмов по скорости выполнения, приводятся их преимущества и недостатки в контексте практического применения в криптографических протоколах. Показано, что выбор конкретного алгоритма зависит от требуемой длины генерируемых простых чисел, допустимого уровня вероятностной ошибки и необходимости получения факторизации числа p-1. Результаты исследования могут быть использованы при разработке криптографических систем, требующих генерации больших простых чисел.