ВВЕДЕНИЕ 3
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ТЕОРИИ ЧИСЕЛ И ТЕОРИИ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ 5
1.1. Простые числа 5
1.2. Поиск и распознавание простых чисел 5
1.2.1. Метод пробных делений 6
1.2.2. Решето Эратосфена 6
1.2.3. Тесты Миллер-Рабина и Соловей-Штрассена 7
1.3. Введение в эллиптические кривые 9
1.4. Алгоритмы подсчета точек на эллиптической кривой 14
ГЛАВА 2. ECPP-TEOPEMA И АЛГОРИТМ ГОЛЬДВАССЕР-КИЛИАНА... 21
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА 24
3.1. Реализация алгоритма Гольдвассер-Килиана 24
3.2. Модификация алгоритма Шенкса-Местре 26
3.3. Сравнение реализаций 28
ЗАКЛЮЧЕНИЕ 30
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 31
ПРИЛОЖЕНИЕ
Купить

Тесты числа на простоту играют важнейшую роль в теории чисел, т.к. они связаны с задачей факторизации числа. Самый первый алгоритм на простоту числа был придуман Эратосфеном для того, чтобы эффективно генерировать множество простых чисел от 1 до п за время O(nloglogn). В следствии развития области информационной безопасности и криптографии, в частности криптографии с открытым ключом, важность поиска больших простых чисел возросла. Используя идеи теоремы Ферма, Соловей и Штрассен в 1977 году, и Миллер и Рабин в 1980 году разработали вероятностные тесты простоты. Несмотря на то, что ответ в этих тестах не всегда верен, данные алгоритмы были использованы в криптографии с открытым ключом для построения множества криптосистем таких как RSA, протокол Диффи-Хеллмана, схемы Эль-Гамаля.
Алгоритм Гольдвассер-Килиана использует эллиптические кривые для того, чтобы свести вопрос о простоте числа р, к вопросу о простоте числа q, которое в свою очередь много меньше р. Итерации схемы алгоритма генерируют сертификат, который может быть использован любым, кто хочет удостоверится в простоте числа р.
Цель магистерской диссертации - улучшить алгоритм Гольдвассер- Килиана. Для того чтобы достичь данной цели необходимо решить следующие задачи:
1) Проанализировать теоретический материал, начиная с элементарных понятий из теории чисел.
2) Исследовать алгоритмы для проверки простоты числа.
3) Изучить материал по теории эллиптических кривых, эллиптической арифметике.
4) Выявить основные алгоритмы для вычисления порядка эллиптических кривых.
5) Реализовать алгоритм Гольдвассер-Килиана с использованием алгоритма Шенкса-Местре для подсчета точек на эллиптических кривых.
6) Модифицировать алгоритм Шенкса-Местре.
7) Сравнить и проанализировать «стандартную» и «модифицированную» версии алгоритма.
Новизна работы состоит в следующем:
1) Впервые использован алгоритм Шенкса-Местре в теле алгоритма Г ольдвассер-Килиана
2) Разработана модификация алгоритма Шенкса-Местре
3) Проведено сравнение реализаций

Купить