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

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

Составное число n называется псевдо простым Ферма по основанию a, если a и n взаимно просты и (1.2).

                                      .                                           (1.2)

Псевдо простые Ферма по основанию 2 образуют последовательность:

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, … 

а по основанию 3 — последовательность:

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, … 

Число, являющееся псевдо простым  Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.

Нечётное составное число n называется псевдо простым Эйлера — Якоби по основанию a, если оно удовлетворяет сравнению (1.3),

                                                                                 (1.3)

где — символ Якоби. Так как из этого сравнения следует, что то всякое псевдо простое Эйлера — Якоби также является псевдо простым Ферма (по тому же основанию).

Псевдо простые Эйлера — Якоби по основанию 2 образуют последовательность:

561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, … 

а по основанию 3 — последовательность:

121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, … 

Если число a является свидетелем простоты составного нечетного числа m, то число m в свою очередь называется сильно псевдо простым по основанию a. Если число m является сильно псевдо простым по основанию a, то оно также является псевдо простым Ферма по основанию a.

Например, сильно псевдо простые числа  по основанию 2 образуют последовательность:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, … 

а по основанию 3 — последовательность:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, …

 

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

 

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

 • формируются случайные  числа заданного размера и  проверяются являются ли они  простыми с помощью вероятностных  тестов (псевдо простые числа);

 • по определенной  процедуре генерируются простые  числа, проверка которых осуществляется  с помощью детерминированных  тестов на простоту;

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

В первом случае тесты строятся на основе определенных теорем из теории чисел, сформулированных и доказанных для простых чисел. Если число  не удовлетворяет тесту, то оно не является простым и отбрасывается. Для проверки берется следующее  случайное число требуемого размера. Если число проходит тест, то некоторый  переменный параметр, используемый для  тестирование, изменяется и тест повторяется  снова. Число прошедшее большое  число опытов определенного типа считается псевдо простым, поскольку  вероятность, что составное число  может пройти все тесты пренебрежимо мала. Для того, чтобы исключить  некоторые возможные классы составных  чисел, которые могут проходить  тесты конкретного типа, используют несколько различных тестов, по каждому  из которых выполняется большое  число опытов. Достоинством генерации псевдо простых чисел является сравнительная простота процедуры. Недостатком первого подхода является то, что после генерации большого псевдо простого числа p может оказаться достаточно сложным определение разложения числа p-1, которое необходимо, например, в случае электронной цифровой подписи на основе сложности задачи дискретного логарифмирования с сокращенной длиной подписи. Разложение числа p-1 представляет интерес также и для отсеивания некоторых классов слабых простых чисел.

 

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

 

Как известно из предыдущего раздела  – все алгоритмы проверки простоты делятся на две больших подгруппы: детерминированные и вероятностные  проверки. Алгоритмы первой группы позволяют точно сказать, является число простым или составным. Алгоритмы второй группы позволяют  это определить, но с некоторой  вероятностью ошибки. Многократное их повторение для одного числа, но с  разными параметрами, обычно позволяет  сделать вероятность ошибки сколь  угодно малой величиной.

 

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

 

Этот метод относится к группе детерминированных методов. Пусть n Є N. Как проверить, является ли n простым? Пока не существовало необходимости генерировать большие простые числа, можно было использовать методы проверки, которые достаточно легко реализуемы без применения вычислительной техники и не требуют больших усилий для проверки маленьких чисел. Первым из таких методов является, естественно, полный перебор всех возможных делителей. Чаще всего используют модификацию такого перебора, называемую пробным делением (trial division): чтобы проверить число на простоту, делим его на все простые меньше либо равные корню из этого числа. Если n—составное, то n =ab, где , причем . Поэтому для d = 2, 3, . . ., [] следует проверить, делится ли n на d? Если делитель числа n не будет найден, то n—простое. В противном случае будет найден минимальный простой делитель числа n, т.е. мы даже разложим n на два множителя. Сложность метода составляет C*n^1/2 арифметических операций с целыми числами.

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

Возможны модификации этого  метода, которые работают быстрее. Например, мы можем проверить, делится ли n на 2 и на 3 , и если нет, то перебираем далее только числа d вида 1 + 6j и 5+ 6j, j =1, 2, … Сложность метода отличается от предыдущей лишь постоянной в C₁(·)

 

1.3.2 Проверка методом «решето Эратосфена»

 

Для построения простых чисел, меньших  какому-либо N, можно воспользоваться  так называемым решетом Эратосфена. Если мы хотим составить таблицу  всех простых чисел среди чисел 2, 3, . . . , N, то нужно сперва вычеркнуть все числа, делящиеся на 2, кроме 2. Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на3 . Затем взять следующее не вычеркнутое число (т. е. 5) и вычеркнуть все последующие делящиеся на него числа, и так далее. В итоге останутся лишь простые числа. Для реализации метода нужен большой объем памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим. В книге описаны эффективные алгоритмы, реализующие решето Эратосфена для построения таблиц простых чисел и вычисление факторных баз. Этот метод также как и метод пробных делений является детерминированным.

 

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

 

Теорема Вильсона – теорема теории чисел, которая утверждает, что если (1.4) делится на p, то p — простое число.

                                             (p-1)!+1                                                             (1.4)

 Практическое использование  теоремы Вильсона для определения  простоты числа нецелесообразно  из-за сложности вычисления факториала.

 

1.3.4 Проверка с помощью вероятностных тестов

 

Вероятностные тесты, в большинстве  случаев строятся на принципе, что  пусть n Є N, n нечетно, n > 1. Тест на простоту проводится следующим образом. Выбирается случайное a Є N, 1 ≤ a <n, и для него проверяется выполнение некоторых условий. Если какое-то из условий не выполнено, то число n—составное, поскольку для простых чисел эти условия являются необходимыми. Если же все условия выполнены, то из этого еще не следует простота n. Однако можно будет считать, что «n —простое число с некоторой вероятностью». Кроме того, обычно доказывают оценку снизу для этой вероятности. Чем больше значений a мы протестируем, тем ближе эта вероятность к единице.

Для проверки простоты чисел n порядка 10³⁰—10⁴⁰ метод пробных делений уже неприменим, потому что даже на самых мощных компьютерах вычисления займут много времени (несколько лет). В 17 веке французский математик Пьер Ферма выдвинул утверждение, которое лежит в основе практически всех возможных тестов на простоту. Малая теорема Ферма: Если n – простое и a – любое целое, то . В частности, если n не делит a, то (1.2).

На основании этой теоремы можно построить эффективные тесты на простоту. Далее приведём наиболее распространённые вероятностные тесты.

Для начала рассмотрим тест Ферма. Для n > 1 выбираем a > 1 и проверяем малую теорему Ферма. Если малая теорема Ферма не выполнена, то n – составное. Если же она выполнена, то мы еще не можем сделать вывод о простоте n, поскольку теорема дает лишь необходимое условие. Этот тест является малоэффективным для обнаружения простых чисел.

Более еффективным является Тест Соловея — Штрассена, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он распознает числа Кармайкла как составные, на которых всегда ошибается тест Ферма.

Тест Соловея — Штрассена  опирается на малую теорему Ферма  и свойства символа Лежандра. Основан  на следующем утверждении: Если m — нечетное составное число, то количество целых чисел w, взаимнопростых с m и меньших m, удовлетворяющих сравнению (1.5) и не превосходит .

                                                                                       (1.5)

Также достаточно известным  является вероятностный тест Лемана, который заключается в том, что  если для какого-либо целого числа a меньшего n не выполняется условие (1.6), то число n – составное.

                                         a^(n-1)/2 ±1 (mod n)                                                   (1.6)

Если это условие выполняется, то число n – возможно простое, причем вероятность ошибки не превышает 50%. Тест можно естественным образом улучшить, если извлекать корень по модулю не один раз, а столько, сколько получится.

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

                                                                                                            (1.7)

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

 

1.4. Алгоритм теста Рабина-Миллера и практические соображения программной реализации

 

Алгоритм теста достаточно прост и широк в использовании. Алгоритм был разработан Майклом Рабином. В нём частично использованы идеи Гэри Миллера. По сути, это упрощённая версия алгоритма, рекомендованного DSS.

Выберите для тестирования произвольное число p. Вычислите b – число делений p-1 на 2(т.е. – это наибольшая степень числа 2, на которую делится p-1). Затем вычислите , такое, что

1. Выберите случайное число , меньше .

2. Установите и .

3. Если или если , то проходит тест и может быть простым числом.

4. Если и , то не относится к простым числам.

5. Установите . Если  и , установите и вернитесь на этап 4. Если , то проходит тестирование и может быть простым числом.

6. Если и , то p не относится к простым числам.

В практических приложениях  генерация простых чисел выполняется  быстро.

1. Сгенерируйте случайное n-битовое число p.

2. Установите старший и младший бит равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший – обеспечивает его нечётность).

3. Убедитесь, что p не делится на малые простые числа: 3, 5, 7, 11, и т.д. Во многих реализациях проверяется делимость p на все простые числа, меньшие 256. Наиболее надёжна проверка делимости на все простые числа, меньшие 2000. Её можно эффективно выполнить с помощью метода «колеса».

4. Выполните тест Рабина-Миллера для некоторого случайного числа . Если p проходит тест, генерируйте другое случайное число и повторите тест. Для ускорения вычислений выбирайте небольшие значения.

5. Выполните пять тестов. Если p не проходит один из тестов, генерируйте другое число p и попытайтесь снова.

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

Пункт №3 является не обязательным, но это хорошая идея. Проверка, что  случайное число p не делится на 3, 5 и 7 отсекает 54 процента нечётных чисел ещё до этапа, описанного в пункте №4. Проверка делимости на все простые числа, меньшие 100 убирает 76 процентов нечётных чисел, проверка делимости на все простые числа, меньшие 256, убирает 80 процентов нечётных чисел. В общем случае доля нечётных кандидатов, которые не делятся ни на одно простое число, меньше , равна 1.12/ln . Чем больше проверяемое , тем больше предварительных вычислений нужно выполнить до теста Рабина-Миллера.

 

 

 

 

 

 

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

 

2.1 Общие сведения

 

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

Программа называется Test_Rabina_millera2.exe, которая реализована в виде консольного  приложения. Исходный текст программы  находится в файле Test_Rabina_millera.cpp.

Программа реализована на языке С++ и откомпилирована в  среде C++ Builder 6.

Для функционирования программы  необходима операционная система MS Windows XP, MS Windows 7, MS Windows 2000, MS Windows 2003 или другая операционная система Win32.

 

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

 

Назначение программы  состоит в том, чтобы генерировать псевдослучайные числа (раздел 1.1) до тех пор, пока они не пройдут вероятностный тест Рабина-Миллера на то, что это число является простым (раздел 4.1). Затем выполняется проверка того, что полученное простое число является «сильным» простым числом (раздел 1.1). В результате работы программы генерируются два «сильных» простых числа P и Q, произведение которых N может использоваться в криптосистемах с открытым ключом. Кроме того, вычисляется вероятность ошибки теста Рабина-Миллера (формула 1.7). Программа разработана в учебных целях для обучения элементарным криптографическим навыкам и применима только для маленьких размерностей.

 

 

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

 

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

Рисунок 2.1 - Схема алгоритма генерации «сильных»  простых чисел