Реализация упрощённого варианта генерации «сильных» простых чисел с использованием вероятностного теста рабина-миллера(для искусственн

 

Министерство образования и науки, молодежи и спорта Украины

Харьковский национальный университет  радиоэлектроники

 

 

Факультет Компьютерной инженерии  и управления

Кафедра Безопасности информационных технологий

 

 

 

КУРСОВАЯ РАБОТА

 

Дисциплина: "Технологии программирования"

на тему:  РЕАЛИЗАЦИЯ УПРОЩЁННОГО ВАРИАНТА ГЕНЕРАЦИИ «СИЛЬНЫХ» ПРОСТЫХ ЧИСЕЛ С ИСПОЛЬЗОВАНИЕМ ВЕРОЯТНОСТНОГО ТЕСТА РАБИНА-МИЛЛЕРА(ДЛЯ ИСКУССТВЕННО МАДЕНЬКИХ РАЗМЕРНОСТЕЙ)

 

 

 

 

Выполнил:

студент І курса 

группы БИКС-10-1

Пономарёва Ксения

Научный руководитель:

Мельникова О.А.

 

 

 

Харьков-2011

Харьковский национальный университет  радиоэлектроники

 

Факультет:         КИУ               Кафедра:       Безопасность информационных технологий

 

Специальность: “Безопасность информационных и коммуникационных систем”

Дисциплина: “Технологии программирования”

 

                       УТВЕРЖДАЮ

                       Зав. кафедры БИТ      

                       проф. И.Д. Горбенко

                                                                                                “ 15  “ марта  2011 г.

ЗАДАНИЕ

НА КУРСОВУЮ РАБОТУ

Студенту Пономарёвой Ксении Константиновне

 

1. Тема работы: Реализация упрощённого варианта генерации «сильных» простых чисел с использованием вероятностного теста Рабина-Миллера(для искусственно маленьких размерностей)

2. Срок сдачи студентом законченной работы:  15.06.2011 г.

3. Выходные данные к проекту:

4. Содержание пояснительной записки: необходимо  осуществить реализацию генерации случайных чисел и проверить их на простоту с помощью вероятностного теста Рабина-Миллера. После проверить являются ли эти простые числа «сильными » простыми числами.

5. Перечень графического материала:

________________________________________________________________

     6. Основная литература и источники: Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Триумф, 2002. — С. 296—300. — 816 с.; Горбенко І.Д., Гріненко Т.О. Захист інформації в інформаційно-телекомунікаційних системах: Навчальний посібник. Частина 1: Криптографічний захист інформації ) – Харків. ХНУРЕ, 2004. – 376 с.

      7. Дата выдачи задания: 21.02.2011 г.

8. Дата сдачи задания: 16.06.2011 г.

Руководитель работы:    Мельникова Оксана Анатольевна

                                                                       

Задание принял к выполнению  _______________________________

                                               (подпись студента)

 

 Студент: Пономарёва Ксения Константиновна                    _________

                                                                                                     (подпись)

 

РЕФЕРАТ

 

 

Курсовая работа содержит 31 с., 5 рис., 7 формул, 6 источников.

Объектом исследования являются простые числа.

Предметом  исследования – реализация вероятностного теста Рабина-Миллера.

Основной задачей работы является реализация упрощённого варианта генерации «сильных» простых чисел с использованием вероятностного теста Рабина-Миллера (для искусственно маленьких размерностей).

ВЕРОЯТНОСТНЫЙ ТЕСТ, СИЛЬНОЕ ПРОСТОЕ ЧИСЛО, ГЕНЕРАЦИЯ, АЛГОРИТМ, ПРОСТОТА, ПРОВЕРКА.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

 

ВВЕДЕНИЕ…………………………………………………………………………..6

1 ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ………………………………..7

1.1 Общие сведения о простых числах…………………………………………..7

1.2 Способы генерации простых чисел………………………………………...12

1.3 Методы проверки чисел  на простоту………………………………………13

1.3.1 Метод пробных делений………………………………………………13

1.3.2 Проверка способом  «решето Эратосфена»…………………………..14

1.3.3 Метод на основе теоремы Вильсона………………………………….15

1.3.4 Проверка с помощью вероятностных тестов……………………...…15  1.4 Алгоритм теста Рабина-Миллера и практические соображения программной реализации…………………………………………………………………………..17

2 ОПИСАНИЕ ПРОГРАММЫ…………………………………………………….19

2.1Общие сведения……………………………………………………………...19

2.2Функциональное назначение программы………………………………….19

2.3 Описание логической структуры…………………………………………..20

2.3.1 Блок-схема алгоритма…………………………………………………20

2.3.2 Структура программы с описанием функций………………………..21

2.4 Используемые технические средства ……………………………………..21

2.5 Входные и выходные данные………………………………………………21

ВЫВОДЫ…………………………………………………………………………...23

ПЕРЕЧЕНЬ ССЫЛОК……………………………………………………………...24

ПРИЛОЖЕНИЕ А Код программы……………………………………………….25

ПРИЛОЖЕНИЕ Б Результаты работы программы………………………………31

 

 

 

 

ВВЕДЕНИЕ

 

 

Тематика генерации больших  простых чисел является ключевой для изучения криптографических  методов защиты информации. Почти  каждый криптографический алгоритм с открытым ключом требует генерации  простого числа размером не менее 512 бит. В процессе использования таких  алгоритмов приходится многократно  создавать такие числа, причем некоторые  алгоритмы требуют простые числа  специального вида. Например, алгоритм цифровой подписи (ЦП) стандарта ГОСТ Р 34.11-94 требует генерации двух простых  чисел p и q таких, что q является делителем  числа (p-1).

В криптографии под случайным  простым числом понимается простое  число, содержащее в двоичной записи заданное количество битов k, на алгоритм генерации которого накладываются  определенные ограничения. Получение  случайных простых чисел является неотъемлемой частью процедур выработки  ключей во многих криптографических  алгоритмах, включая RSA и ElGamal.

Ввиду того, что тестирование простоты больших чисел требует  существенных временных затрат, требование простоты получаемого числа часто  ослабляют до сильной псевдо простоты по нескольким различным случайным  основаниям. Существующие алгоритмы  тестирования сильной псевдо простоты на порядки быстрее лучших известных  алгоритмов тестирования простоты. В  то же время, числа, успешно прошедшие  тестирования сильной псевдо простоты по нескольким случайным основаниям, с большой вероятностью являются простыми, причем эта вероятность  растет с ростом количества оснований, по которым проводится тестирование. В данном курсовом проекте для  проверки числа на простоту используется вероятностный тест Рабина-Миллера (для искусственно маленьких размерностей).

 

 

1 ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ

 

 

1. Общие сведения о простых числах

 

Положительные целые числа  могут быть разделены на три группы: число 1, простые числа и составные  объекты, как это показано на рис. 1.1

 

 
Рисунок 1.1. – Три группы положительных  целых чисел

Положительное целое число —  простое число тогда и только тогда, когда оно точно делимо без остатка на два целых числа  — на 1 и на само себя. Составной  объект — положительное целое  число больше с чем двумя делителями.

Наименьшее простое число  — 2, оно делится без остатка  на 2 (само на себя) и 1. Обратите внимание, что целое число 1 — не простое  число согласно определению, потому что простое число должно быть делимо без остатка двумя различными целыми числами, не больше и не меньше. Целое число 1 делимо без остатка  только на себя; поэтому1 — это не простое число.

Простых чисел бесконечно много. Самое  старое известное доказательство этого  факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число  не делится ни на одно из конечного  набора простых чисел, потому что  остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма всех чисел, обратных к простым, расходится.

Известная теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растёт как n / ln(n).

Издавна ведутся записи, отмечающие наибольшие известные на то время  простые числа. Один из рекордов поставил в своё время Эйлер, найдя простое  число 2³¹ − 1 = 2147483647.

Наибольшим известным простым  числом по состоянию на февраль 2011 года является 2^43112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M_43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел  из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 долларов США.

Далее приведены некоторые свойства простых чисел, из теории чисел, групп, колец и других разделов математики.

• Если p_i — простое, p_{i + 1} следующее за ним простое число, p_{i + 2} следующее за p_{i + 1} простое число, то для всех простых чисел справедливо 3p_{i + 1} − p_i > p_{i + 2} (постулат Шкулева).
• Если p — простое, и p делит ab, то p делит a или b. Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется в доказательстве основной теоремы арифметики.
• Кольцо вычетов является полем тогда и только тогда, когда n — простое.
• Характеристика каждого поля — это ноль или простое число.
• Если p — простое, а a — натуральное, то a^p − a делится на p (малая теорема Ферма).
• Если G — конечная группа с pⁿ элементов, то G содержит элемент порядка p.
• Если G — конечная группа, и pⁿ — максимальная степень p, которая делит | G | , то G имеет подгруппу порядка pⁿ, называемую силовской подгруппой, более того, количество силовских подгрупп равно pk + 1 для некоторого целого k (теоремы Силова).
• Натуральное p > 1 является простым тогда и только тогда, когда (p − 1)! + 1 делится на p (теорема Вильсона).
• Если n > 1 — натуральное, то существует простое p, такое, что n < p < 2n (постулат Бертрана).
• Ряд чисел, обратных к простым, расходится. Более того, при

• Любая арифметическая прогрессия вида a,a + q,a + 2q,a + 3q,..., где a,q > 1 — целые взаимно-простые числа, содержит бесконечно много простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).
• Всякое простое число, большее 3, представимо в виде 6k + 1 или 6k − 1, где k — некоторое натуральное число. Отсюда, если разность между последовательными простыми числами одинакова, то она кратна 6.
• Если p > 3 — простое, то p² − 1 кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3).
• Теорема Грина-Тао: Существуют сколь угодно длинные арифметические прогрессии, состоящие из простых чисел.
• Никакое простое число не может иметь вид n^k − 1, где n>2, k>1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, большим 2. Из этого следует также, что если простое число имеет вид 2^k − 1, то k — простое (см. числа Мерсенна).
• Никакое простое число не может иметь вид n^{2k + 1} + 1, где n>1, k>0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, большим 1.

Большие простые числа (порядка 10³⁰⁰) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ вихрь Мерсенна).

Сильное простое число — простое число с определёнными свойствами, которые определяются по разному в криптографии и теории чисел.

В криптографии сильным называется простое число p, такое что:

1. p достаточно велико

2. p − 1 имеет достаточно большие простые делители, то есть q₁ в p = a₁q₁ + 1

3. q₁ − 1 имеет достаточно большие простые делители, то есть q₂ в q₁ = a₂q₂ + 1

4. p + 1 имеет достаточно большие простые делители

Иногда также добавляют дополнительные условия, например a₁ = 2, a₂ = 2 и т.п.

В теории чисел простое число  называется сильным, если оно больше, чем среднее арифметическое из предыдущего  и следующего простого числа:                                                                                                                                                         (1.1)

Последовательность сильных простых  чисел начинается так:

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, ...

Для простых близнецов (p,p + 2) действительно: если p > 5, p всегда сильное простое число.

Натуральное число называется псевдо простым, если оно обладает некоторыми свойствами простых чисел, являясь тем не менее составным числом. В зависимости от рассматриваемых свойств существует несколько различных типов псевдо простых чисел.