Тест простоты Гольдвассера и Килиана на эллиптических кривых
Научный руководитель - д-р физ.-мат. наук, профессор, д. н.(доцент) КФУ ИВМиИТ кафедры системного анализа и информационных технологий
В настоящее время существует множество методов обработки, накопления и передачи информации, вследствие этого появляется всё больше угроз, связанных с потерей, утечкой, а также частичным или полным разрушением данных пользователя. Именно поэтому обеспечение информационной безопасности считается приоритетной задачей в области информационных технологий.
Простые числа широко распространены в различных областях математики, и именно их использование привело к решению многих математических задач. Использованию простых чисел в области информационной безопасности способствовало развитие в конце 1970-х гг. криптографии с открытым ключом, которая широко применяется при шифровании информации, а также в электронно-цифровой подписи.
В ходе реализации алгоритма Гольвассер-Килиана было создано приложение, в котором производится расчет среднего времени работы алгоритма в разных числовых диапазонах. Среднее время работы алгоритма берется только на простых числах. Так же приложение выдает сертификат простоты.
В ходе исследования установлено, что алгоритм теста на простоту Гольдвассера-Килиана на эллиптических кривых работает долго. Для его оптимизации нужно реализовать алгоритм Шуфа, который является наиболее распространенным алгоритмом для определения количества точек на эллиптической кривой, что помогает в разы ускорить алгоритм.
Алгоритм ГольвассераКилиана не только истинно проверяет числа на простоту, но и выдает сертификат. Основным достоинством сертификата является то, что мы можем опубликовать его вместе с исходным числом. Реконструкция доказательства с помощью сертификата занимает намного меньше времени, однако его особенность является не тривиальной, так как многие доказательства простоты можно проверить лишь повторным запуском алгоритма с самого начала.
