Тема: Тест простоты Гольдвассера и Килиана на эллиптических кривых
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание
1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 4
1.1. Математические основы 4
1.2. Свойства эллиптических кривых 5
1.3. Теорема Хассе 7
1.4. ECPP- теорема Гольдвассера и Килиана 7
1.5. Алгоритм. (тест на простоту Гольдвассера и Килиана) 8
1.6. Задачи исследования 10
2. РАЗРАБОТКА ПРОГРАММЫ 11
2.1. Средства реализации 11
2.2 Реализация алгоритма 12
3. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 14
3.1. Время работы алгоритма Гольдвассера и Киллиана 14
3.2. Сертификат простоты 15
ЗАКЛЮЧЕНИЕ 17
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 18
ПРИЛОЖЕНИЕ
📖 Введение
Простые числа широко распространены в различных областях математики, и именно их использование привело к решению многих математических задач. Использованию простых чисел в области информационной безопасности способствовало развитие в конце 1970-х гг. криптографии с открытым ключом, которая широко применяется при шифровании информации, а также в электронно-цифровой подписи.
Кроме этого простые числа используются для взлома информации, использующей алгоритмы защиты RSA. Здесь возникает проблема, связанная тем, что использование такого взлома подразумевает умение разложения числа на два простых множителя. Сложность заключается в том, что из-за большого размера числа сделать это довольно затруднительно.
С другой стороны, при генерации ключей используются большие псевдослучайные простые числа. Например, при использовании протокола Диффи-Хеллмана необходимо иметь простое число, задающее конечное поле. Поэтому, использование эффективного теста простоты позволяет повысить надежность алгоритмов генерации таких ключей.
✅ Заключение
Алгоритм Гольвассера и Килиана не только истинно проверяет числа на простоту, но и выдает сертификат. Основным достоинством сертификата является то, что мы можем опубликовать его вместе с исходным числом. Реконструкция доказательства с помощью сертификата занимает намного меньше времени, однако его особенность является не тривиальной, так как многие доказательства простоты можно проверить лишь повторным запуском алгоритма с самого начала.