1 Введение
2 Эллиптические кривые и их применение
2.1 Обзор методов проверки чисел на простоту
2.2 Эллиптические кривые над конечным полем
2.3 Теорема о простоте
2.4 Методика тестирования
3.1 Алгоритмы Гольдвассер - Килиана и Аткина - Морейна
4 Постановка задачи
4.1 Метод Аткина - Морейна
4.2 Алгоритм тестирования
5 Разработка программного модуля
5.1 Выбор средств разработки
5.2 Проектирование
5.3 Реализация
5.4 Пример использования
5.5 Тестирование
Заключение
Список литературы
Вопрос о простоте некоторого числа часто возникает при работе с криптографическими алгоритмами. В частности, алгоритм RSA для генерации ключей требует два больших простых числа. Системы шифрования, работающие на эллиптических кривых, так же нуждаются в простых числах. Есть множество алгоритмов, отвечающих на данный вопрос. Их условно можно разделить на две большие группы: вероятностные и истинные. Среди вероятностных алгоритмов широкое распространение получил тест Миллера-Рабина. Именно он используется во многих криптографических алгоритмах. Главным недостатком данного теста, является не нулевая вероятность ошибки. Напротив, истинные тесты дают точный ответ о простоте числа. Одним из таких тестов, является тест Аткина- Морейна. Данный тест имеет одну из лучших оценок сложности среди тестов, доказывающих строго тот факт, что число простое. Кроме того, для чисел, успешно прошедших данный тест, можно составить сертификат, который может быть проверен намного легче, чем построен.
В ходе дипломной работы создан программный модуль для проверки чисел на простоту методом Аткина - Морейна. Данный тест, является истинным тестом простоты, а это значит, что число, успешно прошедшее данный тест, точно является простым. В ходе проведенных тестов алгоритм показал приемлемое время работы. Вычислительно сложными этапами являются этапы факторизации, получения гильбертова многочлена с комплексными коэффициентами и поиск корней полиномов больших степеней. Вопросы факторизации и полиномиальной арифметики в конечных полях заслуживают отдельных исследований и над ними работают не малое количество ученых.
В программном модуле, созданным в ходе данной дипломной работы, в качестве алгоритма факторизации применен р - метод Полларда. Модуль спроектирован таким образом, что данный метод может быть без особых усилий заменен на более мощный. Однако, необходимо всегда помнить о рациональном использовании вычислительных ресурсов. Очевидно, что применение, например, метода квадратичного решета для факторизации небольших чисел прироста производительности не даст, а даже наоборот, замедлит процесс.
Для каждого тестируемого числа на шаге определения порядков возможных кривых, есть выбор как минимум из 2-х порядков. Получив разложение для каждого порядка #EC = кq,есть смысл выбрать тот, в разложении которого число q наименьшее. Таким образом снижается время работы следующих рекурсивных вызовов, а в лучшем случае удастся добиться уменьшения уровня рекурсии.
Неоспоримым преимуществом является создание сертификата простоты в ходе работы теста Аткина - Морейна. Благодаря этому можно организовать тестирование чисел на мощных серверах, а на клиентских машинах по необходимости проверять сертификат
