Актуальность Большие простые числа (порядка 10³⁰–10⁵⁰⁰) используются:

• в ассиметричной криптографии
• в хеш-таблицах
• для генерации псевдослучайных чисел.

В данной работе рассматривается так называемый N+1 метод, позволяющий дать некоторые достаточные условия простоты, а иногда и критерии простоты. Данный метод является эффективным для чисел N специального вида, таких как 2ⁿh+1, где h нечетно, 2rq+1, где q – нечетное простое число, и r ≤2q +1.

Целью написания данной работы является анализ существующих методов N+1 определения простоты большого числа и реализация на программном уровне.

Для этого необходимо решить следующие задачи:

- рассмотреть существующие методы N+1 определения простоты числа;

- разработка программы для построения больших простых чисел.

Практической частью исследования является создание программы, который наглядно показал бы в действии способ определения простых чисел.

——————————————————————————————————————————————————

Содержание работы

Введение.

Глава 1. Анализ методов группы N+1 построения больших простых чисел..

1.1 Сведения из теории чисел используемые в N+1 методах.

1.2 Рассмотрение методов группы P+1.

1.3 Использование методов факторизации.

Глава 2. Формулировка алгоритмов и анализ их эффективности

2.1. Разработка архитектуры программы.

2.2. Разработка интерфейса программы.

2.3. Описание алгоритма программы.

Глава 3. Экспериментальные исследования программы.

Заключение

Список литературы:.

Приложение

Проблема определения того, является ли число простым, важна с практической точки зрения для применения в криптосистемах с открытым ключом. Хотя простые числа изучаются уже достаточно долго, наибольшее развитие тема вероятностных проверок получила во второй половине двадцатого века именно в связи с необходимостью генерировать большие (сто и более десятичных цифр) простые числа для таких криптосистем как RSA.

Цель: проверка больших чисел (длиной > 256 бит) на простоту.

Задачи:

1) Провести обзор методов проверки числа на простоту.

2) Разработка и реализация алгоритма Рабина-Миллера.

3) Получить временные оценки прохождения теста Рабина-Миллера.

Актуальность: алгоритм Рабина-Миллера находит применение в криптосистемах RSA и программе PGP

Содержание работы

Введение

Глава 1. Методы тестирования чисел на простоту

• Необходимые сведения из теории чисел и теории групп
• Обозначения
•  Китайская теорема об остатках
• Гипотеза Римана
• Обзор методов проверки числа на простоту
• Метод пробных делений
• Решето Эратосфена
• Вероятностные тесты
• Объединение тестов
• Составление таблицы для сравнения имеющихся алгоритмов проверки числа на простоту

Глава 2. Реализация алгоритма Рабина-Миллера

• Выбор языка программирования для написания программы
• Разработка алгоритма Рабина-Миллера

Глава 3. Исследование разработанной программы

• Проверка работы программы
• Исследование зависимости времени выполнения программы от количества цифр в числе

Заключение

Список литературы

Основные задачи исследования:

1.     Анализ алгоритмов группы «N-1» построения простых чисел

2.     Выбор языка программирования.

3.     Программная реализация алгоритма.

4.     Генерация больших простых чисел и оценка времени, необходимого для их построения.

——————————————————————————————————————————————————-

Содержание работы

Введение

Глава I.   Анализ «N-1» алгоритмов построения простых чисел. Выбор алгоритма        

1.1     Используемые факты, теоремы и определения из теории    чисел

1.2     Элементарные (классические) алгоритмы построения простых чисел и проверки на простоту

1.3     «N-1» — алгоритмы построения и проверки простых чисел.                                                                                            

1.4     Выбор алгоритма

Глава II.  Разработка алгоритма

2.1             Проблемы, связанные с реализацией алгоритма.

2.2             Выбор языка программирования

2.3             Описание и блок-схема алгоритма

2.4             Программная реализация

Глава III. Исследования результатов выполнения программы

3.1             Характеристика компьютера

3.2             Результаты

3.3             Анализ результатов

Заключение

Приложение 1. Обозначения

Приложение 2. Листинг программы

Список литературы

——————————————————————————————————————————————————-

Характеристига работы

Объем курсовой работы составляет 43 листа, имеется листинг программы