Алгоритм генерации больших простых чисел. Алгоритмы, используемые при реализации асимметричных криптосхем. Построение больших простых чисел

18.03.2019

Аудио

Тест Миллера-Рабина:

Вход: n=2sr+1 – нечетное число, проверяемое на простоту, s≥0, r – нечетное. t - количество итераций, параметр надежности.

1. Повторить t раз следующие шаги:

1.1. Случайным образом выбрать a {2,…, n-2};

1.2. Построить последовательность b0, b1,…,bs, по правилу:

b0=ar mod n, bj=(bj-1)2 mod n, j=1,2,…,s.

1.3. Если в построенной последовательности не встретилась

«1», то идти на Выход с сообщением «n - составное».

1.4. Если перед первой единицей в последовательности стоит не

«-1», то идти на Выход с сообщением «n - составное».

2. Идти на Выход с сообщением «n – простое с вероятностью εt ».

Обратим внимание на то, что в последовательности b 0,b 1,…,bs каждый последующий член является квадратом предыдущего по модулю n , а последний член есть ни что иное как an -1 mod n .

Вероятность ошибки теста на одной итерации составляет ε≤φ(n )/4n , то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма.

Пример использования теста Миллера-Рабина:

n =65=64+1=26+1. r =1, s =6. t =5.

1. 1-я итерация:

1.1. a =8.

1.2. Составляем последовательность: b0=8, b1=64=-1, b2=1,

b3=1, b4=1, b5=1, b6=1.

1.3. В последовательности встретилась «1».

1.4. Перед первой единицей стоит «-1».

1. 2-я итерация:

1.1. a =11.

1.2. Составляем последовательность: b0=11, b1=56, b2=16,

b3=61, b4=16, b5=61, b6=16.

1.3. В последовательности не встретилась «1».

Выход: « n - составное число».

Задания к разделу 2

1) Реализовать процедуру генерации простых чисел методом случайного поиска среди 128-битных чисел, старший бит которых равен 1 и проверки

а) тестом Ферма

б) тестом Соловея-Штрассена

в) тестом Миллера-Рабина.

Количество итераций вероятностного теста должно быть таково, чтобы вероятность ошибки не превышала 0,1. Вероятность ошибки определяется исходя из оценки ε для теста. Количество итераций для теста Ферма задать равным 50.

2) Получить с помощью этой процедуры 10 простых чисел. Для каждого эксперимента найти количество перебранных чисел до получения простого. Результаты оформить в виде таблицы.

Здесь №-номер эксперимента, p – найденное простое число, n – количество перебранных чисел до получения простого.

Данные для самопроверки к разделу 2

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

· Задать значение параметра надежности теста t =1.

· Подставить в качестве входного параметра n число из колонки «Числа для проверки».

· Несколько (10-20) раз «прогнать» программу с заданными входными параметрами.

· Выводы о корректности реализованного теста следует делать на основании сравнения результата теста с данными из таблицы (колонка «Результат теста»).

Тип числа	Числа для проверки	Результат теста
Простые числа			Всегда «простое»




Числа Кармайкла			Для теста Ферма - всегда «простое», для тестов Миллера-Рабина и Соловея-Штрассена - чаще «составное»,чем «простое»




Составные, нечетные, не являющиеся числами Кармайкла			Чаще «составное»,чем «простое»

РАЗДЕЛ 3. ДОКАЗУЕМО ПРОСТЫЕ ЧИСЛА

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

Подход к получению доказуемо простых чисел отличается от подхода, рассмотренного ранее. Для построения таких чисел не используется случайный поиск. С использованием таблицы простых чисел небольшого размера, построенной заранее, строится число m (равное произведению нескольких простых чисел либо произведению простых чисел и случайного числа), затем число n =2m +1 проверяется на простоту одним из нижеприведенных тестов. Достоинством такого подхода является не только получение гарантированно простого числа n , но также получение порождающего элемента группы Z n *. Поэтому доказуемо простые числа, как правило, используются в качестве модулей криптосистем, основанных на проблеме дискретного логарифмирования, таких как шифр Шамира, криптосистема Эль-Гамаля и связанные с ней стандарты цифровой подписи ГОСТ Р 34.11-94, ГОСТ Р 34.11-2001, DSA и EСDSA.

3.1. Тест Миллера на простоту

Тест Миллера основан на теореме Сэлфриджа.

Алгоритм построения простого числа с помощью теста Миллера следующий:

q i

2. Строится число m =(где qi-различные случайные простые числа из таблицы, αi – случайные целые числа), размер которого на 1 бит меньше требуемого размера для простого числа;

3. Вычисляется значение n =2m +1;

4. Построенное число n испытывается тестом Миллера с заданным параметром надежности. Если результат проверки отрицательный, то следует вернуться на шаг 2 и построить новое число m .

Тест Миллера:

Вход: n – число для проверки, n -1=https://pandia.ru/text/78/045/images/image051_14.gif" width="44" height="43">mod n . Если какой-либо из результатов не равен единице, то идти на шаг 3, взять следующее qi . Если все результаты равны «1», то идти на Выход с сообщением «вероятно, n – составное число».

4. Идти на Выход с сообщением «n – простое число».

Если число n было предварительно проверено на простоту вероятностным тестом Миллера-Рабина, то в тесте Миллера достаточно перебрать 4-6 значений aj .

Если n – нечетное простое число, то вероятность того, что n по случайно выбранному основанию 1< a < n пройдет проверку на шаге 3.1, есть j(n-1)/(n-1).

3.2. Тест Поклингтона

Тест Поклингтона основан на теореме Поклингтона и позволяет проверять простоту числа n , если каноническое разложение числа (n -1) известно лишь частично.

Алгоритм построения простого числа с помощью теста Поклингтона следующий:

1. Строится таблица малых простых чисел q i (или используется готовая таблица);

2..gif" width="104" height="32"> - каноническое разложение; t – параметр надежности.

1. Выбрать t различных целых случайных чисел aj : 1< aj < n .

2. Для каждого aj вычислить (ajn -1 mod n . Если какой-либо из результатов не равен «1», то идти на Выход с сообщением «n – составное число».

3. Для каждого ai выполнить:

3.1. Для каждого qj вычислить () mod n . Если какой-либо из результатов равен единице, то идти на шаг 3, взять следующее ai . Если все результаты не равны «1», то идти на Выход с сообщением «n – простое число».

4. Идти на Выход с сообщением «вероятно, n – составное число».

Если n = RF+1 – нечетное простое число, F>https://pandia.ru/text/78/045/images/image055_12.gif" width="99" height="29">, НОД(R, F)=1, то вероятность того, что случайно выбранное 1< a < n будет удовлетворять условиям теоремы Поклингтона, есть https://pandia.ru/text/78/045/images/image057_10.gif" width="28" height="27 src=">-1<63.

n - 1=4020=22·3·5·67. F=67, R=22·3·5=60.

Проверка условий:

a = 2.

1) 24020 mod 4021=1.

2)24020/67 mod 4021 =260 mod 4021=1452.

Выход: n = 4021 – простое число.

(Заметим, что вероятность того, что наугад выбранное a будет удовлетворять условиям теоремы Поклингтона для данного примера, есть (1-1/67)≈0,985).

3.3. Процедура генерации простых чисел ГОСТ Р 34.10-94

В отечественном стандарте на цифровую подпись ГОСТ Р34.10-94 рекомендована процедура генерации доказуемо простых чисел заданного размера. ГОСТ Р 34.10-2001 также предписывает использование этой процедуры. Данная процедура основана на теореме Диемитко.

Теорема Диемитко

Пусть n = qR + 1, где q – простое число, R – четное, R <4(q +1).

Если найдется a < n : 1) an -1≡1(mod n ); 2) 1(mod n ), то n – простое число.

Итак, если имеем простое число q , то, перебирая четные числа R , строим числа n = qR + 1 и испытываем их на простоту согласно теореме Диемитко, пока не получим простое число. По полученному числу можно построить еще одно простое число и т. д., пока не будет достигнут требуемый размер числа.

Приведем алгоритм перехода от меньшего простого числа q : |q |= к большему p : |p |=t , использующийся в ГОСТе. Фигурирующая в процедуре ξ есть равномерно распределенная на (0,1) случайная величина, получаемая с помощью линейного конгруэнтного генератора. Каждый раз на шаге 1 получают новое значение ξ.

Алгоритм перехода от меньшего простого числа к большему:

Вход: t – требуемая размерность простого числа, q – простое число: |q |=.

1..gif" width="15 height=20" height="20">1(mod p ), то идем на Выход.

6. Вычисляем u = u +2. Возвращаемся на шаг 3.

Выход: p – простое число.

Первое слагаемое в построении числа N на шаге 1 обеспечивает минимальный требуемый размер числа p , а второе вносит в процедуру поиска новых простых чисел необходимый элемент случайности.

Проверка на шаге 4 необходима, чтобы число p не превышало своей верхней границы, а проверка на Шаге 5 есть проверка условия теоремы Диемитко при a =2.

Пример

Вход: t= 4, q= 3=2

1. N=0 " style="margin-left:-101.3pt;border-collapse:collapse;border:none">

Результат проверки вероятностным тестом

Здесь № - номер эксперимента, p – построенное простое число, в третьей строке результат проверки построенного числа вероятностным тестом (+ или -), k – количество отвергнутых чисел, определенных вероятностным тестом как простые.

Количество итераций вероятностного теста должно быть таково, чтобы вероятность ошибки не превышала 0,1.

Данные для самопроверки к разделу 3

Для тестов Миллера и Поклингтона

1) реализованный тест следует проверить таблицей составных чисел. В качестве входных параметров реализованного теста следует подставить числа из колонки «Числа для проверки» если в результате тест выдаст сообщение о том, что данное число отвергается, то следует перейти к следующему этапу проверки. Если хотя бы одно из этих чисел опознается тестом как простое, то тест реализован с ошибками.

2) Затем следует воспользоваться таблицами согласно реализованному тесту. Для проверки этими таблицами следует подставить в качестве входных параметров данные из таблиц (для теста Миллера проверяемое простое число p и каноническое разложение числа (p -1), для теста Поклингтона – проверяемое простое число p , число R и каноническое разложение числа F). Установить количество итераций теста t =1. Проверить число p этим тестом несколько раз (30-100). Затем рассчитать частоту события, когда проверяемое простое число будет принято за составное, и сравнить это значение с данными из колонки «Вероятность ошибки». Если эти данные приблизительно равны рассчитанному значению частоты, то тест реализован верно.

Для процедуры генерации чисел ГОСТ 31.10-94

Для проверки лабораторной работы следует выставить параметр ξ = 0 (то есть избавиться от случайности). Затем следует подставить в качестве входных параметров данные из таблицы (q и t ). Результат должен совпадать со значением из колонки «Построенное число».

Таблица составных чисел

Числа для проверки (p )	Разложение p -1	Разложение F	Результат теста
			Всегда отвергаются

Транскрипт

1 ЛЕКЦИЯ 15 ПРОСТЫЕ ЧИСЛА Натуральное число p, больше единицы называется простым, если оно делится нацело только на 1 и на себя. Теорема (Эвклид). Множество простых чисел бесконечно. Обозначим через π(x) функцию, которая равна числу простых чисел p в интервале 1 < x p. Российский математик П. Л. Чебышев в 1850г. показал , что 0,921 x / ln x < π(x) < 1,106 x / ln x. Простые числа являются важным понятием в криптографии. Многие современные криптографические системы строятся на базе простого числа. Поэтому алгоритмы генерации простых чисел и проверки на простоту сформированного числа являются важными инструментами при создании криптографической системы. Простые числа встречаются довольно часто. Заметим, что существует около простых чисел длиной от 1 до 512 бит включительно , а количество простых чисел меньших приблизительно равно . Для чисел близких n вероятность произвольно выбранному числу оказаться простым числом, равна 1/ln n. При случайном выборе двух простых чисел в диапазоне от 1 до 151 бита вероятность совпадения этих чисел ничтожно мала. Простые числа играют важную роль в современной криптографии. Многие современные криптографические системы с открытыми (или не симметричными) ключами формируются с применением простых чисел. Для простых чисел будем рассматривать три задачи: построение простых чисел; проверка чисел на простоту; факторизация (разложения) чисел на простые множители. На самом деле все эти три задачи фактически дают

2 ответ на один вопрос: является ли рассматриваемое число простым. Но для каждой из этих задач применяются свои методы. Для первой задачи, используя необходимые условия простоты, можно давать ответы типа: заданное число n не простое; вероятность того, что заданное число n не простое, меньше заданного числа ε. Для второй задачи можно строить некоторую последовательность чисел специального вида. И для чисел данной последовательности применять некоторые тесты до тех пор, пока не найдем среди них простое число. Приведем некоторые определения, теоремы, алгоритмы, которые связаны с вопросами решения поставленных задач (см., например ; ; ). Определение 1. Числа F k = 2 α + 1, α = 2 k, k = 0, 1, 2, называются числами Ферма. Теорема 1. Число Ферма n = F k при k > 0 является простым тогда и только тогда, когда 3 (n 1)/2 1 mod n. Определение 2. Пусть p простое число. Числа вида M p = 2 p 1 называются числами Мерсенна. Кстати, все четные совершенные числа имеют вид 2 p 1 M p, где M p является числом Мерсенна. Напомним, совершенным числом называется число, которое равно сумме всех своих делителей, меньших, чем оно само. Например, 28 = Числа Мерсенна редки. В 2001году было найдено тридцать девятое число Мерсенна для p = Для проверки простоты чисел Мерсенна применяется следующая теорема . Теорема 2. Пусть n простое число, n > 2, M n = 2 n 1. Рассмотрим последовательность L 0, L 1, которая определяется соотношениями L 0 = 4, L 2 j+1 = L 2 j 2 mod n, 0 j < n. Число M n простое тогда и только тогда, когда L q 2 0

3 mod n. ПРОВЕРКА НА ПРОСТОТУ Простые числа необходимы для большинства криптографических систем с открытыми ключами. Теоретический материал к вопросу построения больших простых чисел можно найти в и . Здесь будут сформулированы только некоторые практические подходы к формированию больших простых чисел. Для генерации больших простых чисел могут быть использованы следующие два подхода: формируются случайные числа заданного порядка, и при помощи существующих тестов проверяется, являются ли они простыми. по определенному алгоритму генерируются простые числа, и при помощи определенных тестов производится проверка чисел на простоту. Сначала рассмотрим те тесты, которые используются при реализации первого подхода формирования простого числа. Пробное деление Один из самых простых способов проверки числа p на простоту состоит в последовательном делении числа p на все нечетные числа, которые содержатся в интервале . Если в процессе деления получим целый результат, то число p составное. Если же при переборе всех нечетных чисел из интервала разделить число p на эти числа нацело нельзя, то число p простое. Данный метод называется пробным делением. Этот метод трудоемок по числу арифметических операций, и он используется в основном для проверки небольших простых чисел.

4 Решето Эратосфена Если мы хотим составить таблицу всех простых чисел среди чисел 2, 3, N, то надо последовательно вычеркнуть все числа, которые делятся на 2, кроме 2; на 3, кроме 3; на 5 кроме 5; на следующее число, которое не вычеркнуто, кроме этого числа; и т. д. В итоге среди чисел от 1 до N останутся лишь простые числа. Для реализации метода нужен большой объем памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим . Более того, разрабатываются специальные процессоры, на которых операции «просеивания» выполняются очень эффективно . Замечание. Пробное деление и решето Эратосфена можно применять при решении задачи разложения целого числа на множители. Тест на основе малой теоремы Ферма Малая теорема Ферма утверждает, что если n простое число, то выполняется условие: при всех a {2, 3, n 1} имеет место сравнение A n 1 1 mod n. На основании этой теоремы можно построить вероятностный алгоритм проверки на простоту числа n. Если для некоторого целого a из интервала соотношение a n 1 1 mod n не выполняется, то число n составное. Если же теорема выполняется, то вывод, что число n простое, сделать нельзя, так как

5 теорема дает лишь необходимое условие. Поэтому, если для некоторого a имеет место соотношение a n 1 1 mod n, то говорят, что число n является псевдопростым по основанию a . Существует бесконечно много пар чисел a и n, где n составное и псевдопростое. Вообще для любого a > 1 существуют бесконечно много псевдопростых чисел по основанию a . Вообще, справедливы следующие два утверждения. Если пара (2, n) удовлетворяют сравнению a n 1 1 mod n, то и пара чисел (2, 2 n 1) также ему удовлетворяют. Для любого простого числа n и любого a > 2 такого, что (a 2 1, n) = 1, число (a 2n 1)/(a 2 1) является псевдопростым по основанию a. Определение. Составные числа n, для которых при всех основаниях выполняется сравнение a n 1 1 mod n, называются числами Кармайкла. Схема алгоритма на базе малой теоремы Ферма Дано число n и параметр γ = 1 для идентификации результата проверки. 1) делается случайный выбор целого числа a из интервала ; 2) используя алгоритм Эвклида, вычисляется НОД для чисел a и n; 3) если НОД больше 1, то выполняется шаг 7; 4) для числа a проверяется сравнение a n 1 1 mod n; 5) если сравнение не выполняется, то определяется параметр γ = 0 (число составное) переход на шаг 7. 6) если сравнение выполнено, то можно повторить тест; 7) выдать результат проверки (γ = 0 число составное).

6 При завершении работы алгоритма возможны следующие выводы: число n составное (γ = 0); если γ = 1, то число n является либо простым, либо составным и числом Кармайкла. Здесь уместно заметить , что числа Кармайкла достаточно редки. Так существуют всего чисел Кармайкла, которые не превосходят, и всего 16 чисел, которые не превосходят числа Тест Соловея Штрассена Тест Соловея Штрассена проверки на простоту числа p базируется на теореме 4. Теорема 4. Для любого нечетного n следующие условия эквивалентны: n простое; для любого a Z * n выполняется сравнение a (n 1)/2 mod n L(a, n), где Z * n мультипликативная группа, элементами которой являются элементы a Z n (Z n кольцо вычетов по модулю n). Для проверки простоты числа p используется алгоритм вычисления символа Якоби. Схема алгоритма на базе малой теоремы Ферма Пусть дано нечетное число p. Надо проверить является ли число p простым. 1. Выбирается случайное число a, меньшее p. 2. Если НОД (a, p) 1, то p составное число. 3. Вычисляется сравнение L(a, p) a (p 1)/2 mod p. 4. Вычисляется символ Якоби J(a, p). 5. Если L(a, p) J(a, p), то число p составное. 6. Если L(a, p) = J(a, p), то вероятность того, что число p составное не превышает 50 %.

7 Если проверка повторяется k раз, то вероятность того, что число p составное, не превышает 1/2 k. Тест Рабина Миллера Обоснование алгоритма Рабина Миллера можно найти в . Здесь дадим только самые общие соображения. Известно, что если число p простое, то уравнение x 2 1 mod p имеет лишь два решения: x ±1 mod p. Итак, пусть p нечетное целое число, которое надо проверить на простоту. Если p простое, то по теореме Ферма для любого целого a взаимно простого с p выполняется сравнение a m 1 1 mod p. Так как p 1 четно, то получаем a (m 1)/2 ±1 mod p. Если оказывается, что (m 1)/2 четно, то можно повторить рассуждение, при котором получим, что a (m 1)/4 ±1 mod p, и т. д. Поэтому, чтобы проверить на простоту нечетное число p, выбираем случайным образом число a из интервала и вычисляем a t mod p, a 2t mod p, a βt mod p, где t нечетное и число β = 2 s. Если одно из этих чисел не совпадает с +1 или 1, то можно сделать вывод, что число p является числом составным. Если значения чисел совпадают с +1 или 1, то повторяем этот тест k раз. После повторения этого теста k раз вероятность того, что составное число p не будет выявлено, не превосходит 1/4 k. После высказанных соображений перейдем к формулировке алгоритма Рабина Миллера. В некоторой литературе данный алгоритм называют тестом Миллера Рабина . Схема алгоритма Рабина Миллера Пусть дано нечетное число p. Надо проверить

8 является ли число p простым. Далее предположим, что p 1 = 2 s t. 1. Выбираем случайное число a, меньшее p и определяем k = Вычисляем с помощью алгоритма Эвклида НОД двух чисел a и p. Если НОД (a, p) 1, то p составное число. 3. Вычисляем b a t mod p. Если b = 1 или b = p 1, то число p вероятно простое. 4. Если b 1 и b p 1, то вычисляем b b 2 mod p и k = k Если число b = p 1, то число p вероятно простое. Перейти на шаг Пока k < s выполнять пункт Завершить работу алгоритма. Рассмотрим примеры. Пример. Пусть p = 181. Имеем p 1 = По представленному разложению определяем значение параметра t = Выбираем случайное число a = 52 < p, и определяем k = Используем алгоритм Эвклида для вычисления НОД двух чисел 52 и 181: делим число 181 на число 52, получаем 181 = ; делим число 52 на число 25, получаем 52 = ; делим число 25 на число 2, получаем 25 = ; делим число 2 на число 1, получаем 2 = ; получаем, что НОД двух чисел 181 и 52 равен 1. Так как НОД не позволяет установить является ли число 181 составным, то продолжаем выполнять алгоритм Рабина Миллера. 3. Последовательно вычисляем

9 b 52 t mod mod 181: 52 2 mod mod mod 181, 52 4 mod mod mod mod 181, 52 8 mod mod mod mod 181, mod mod mod mod 181, mod ` mod mod mod 181, mod 181 (52 32 mod 181)(52 8 mod 181) () mod mod mod 181, mod 181 (52 40 mod 181)(52 mod 181) (80 52) mod mod mod 181, mod 181 (52 41 mod 181)(52 4 mod 181) () mod mod 181 = 180 mod 181. Итак, получили b = 180 = p 1. Откуда следует, что число p = 181 вероятно простое. Замечание. Для генерации даже небольших простых чисел вычисления довольно громоздки. Поэтому для реальных чисел, несомненно, подобные проверки чисел на простоту надо делать при помощи программ на компьютере. В дается некоторое руководство при генерации простых чисел для практических приложений. Это руководство сводится к реализации нескольких этапов (шагов). 1. Сгенерируйте случайное n-битовое число p. 2. Установите старший и младший биты равными 1. Старший бит в этом случае гарантирует требуемую длину простого числа, а младший его нечетность.

10 3. Убедитесь, что число p не делится на малые простые числа 3, 5, 7, 11 и т. д. Наиболее надежна проверка делимости на все простые числа, меньше Выполните тест Рабина Миллера для некоторого случайного числа a. Если p проходит тест, то сгенерируйте другое случайное число a и повторите тест. Для практических приложений достаточно повторить тест Рабина Миллера пять раз. 5. Если p не проходит один из тестов, надо сгенерировать другое число p и повторить данное руководство снова. Другое число p, если оно оказалось не простым, можно получить не генерируя новое, а последовательно перебирая все целые, начиная от p + 1, p + 2, и т. д., пока не найдется простое число. Перейдем теперь к вопросу о генерировании больших простых чисел. Построение больших простых чисел и детерминированные алгоритмы проверки чисел на простоту Рассмотрим еще один способ формирования простых чисел. Этот способ базируется на определенной процедуре генерирования простых чисел, проверка которых осуществляется с помощью тестов на простоту. Такой подход применяется, например, в стандарте электронной цифровой подписи (ЭЦП) ГОСТ Р и основывается на следующей теореме . Теорема 5. Пусть p = qn + 1, где q нечетное простое число, N четное число и p < (2q + 1) 2. Число p является простым, если выполняются два условия: 1) 2 qn = 1 mod p; 2) 2 N 1 mod p.

11 Генерация простого числа с использованием теоремы 5 осуществляется по несколько упрощенной в принятом стандарте схеме . Пусть требуется сформировать простое число p длины t 17 бит. С этой целью строится убывающая последовательность чисел {t i }, где i = 0, 1, s, для которых t 0 = t, t i = . Далее последовательно вырабатывается последовательность простых чисел p s, p s 1, p 0, для всех i = 1, s. Генерация простого числа p i 1 осуществляется с использованием следующее формулы p i 1 = p i N + 1, где число N удовлетворяет следующим условиям : N четное; N такое, что длина числа p i 1 = p i N + 1 в точности должна быть равна t i 1. В стандарте ГОСТ дается некоторый алгоритм вычисления числа N. Для учебного варианта N случайное четное число, которое получают с помощью датчика случайных чисел (если N нечетно, то N = N + 1). Число p i 1 считается полученным, если одновременно выполнены следующие два условия: 1) 2 β = 1 mod p i, β = p i 1 N; 2) 2 N 1 mod p i. Если хотя бы одно из условий не выполняется, то значение числа N увеличивается на 2, и вычисляется новое значение p i 1, которое снова проверяется на простоту по двум условиям. Данный процесс продолжается до тех пор, пока не будет получено простое число p i 1 (т. е. условия 1 и 2 алгоритма генерации простого числа будут выполнены). Заметим, что с 2002 года вышеупомянутый отечественный стандарт ЭЦП заменен на новый ГОСТ Р .

12 Проверка чисел Мерсенна на простоту Напомним, что число M s = 2 s 1 (s 2 простое число) называется числом Мерсенна. Критерием простоты чисел Мерсенна служит следующее утверждение . Теорема. Число Мерсенна M s = 2 s 1, где s 3 нечетное число, является простым тогда и только тогда, когда число s простое; выполняется сравнение L n 2 0 mod M s, где последовательность {L k } формируется по такому правилу: L 0 = 4, L k+1 = (L 2 k 2) mod M s при k 0.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТРУДЫ XIII ВСЕРОССИЙСКОЙ КОНФЕРЕНЦИИ СТУДЕНЧЕСКИХ

ЛЕКЦИЯ 14 Вычисление квадратных корней по составному модулю Из приведенной выше теории следует, что если =, где и простые числа, группа Z изоморфна пространству Z Z. Поскольку изоморфизм сохраняет свойства

Раздел 2. Теоретико-численные методы в криптографии Задание на самостоятельную работу Изучить алгоритмы, которые широко применяются в криптографии. Элементы теории чисел: расширенный алгоритм Евклида;

Глоссарий основных терминов Абелева группа(коммутативная группа) группа по сложению, в которой групповая операция коммутативна: a + b = b + a. Авторизация это процедура разделения пользователей на группы

Краткое введение в начала элементарной теории чисел Денис Кириенко Летняя компьютерная школа, 1 января 2009 года Целочисленное деление Пусть дано два целых числа a и b, b 0. Целочисленным частным от деления

ЛЕКЦИЯ 6 СТЕПЕННЫЕ ВЫЧЕТЫ Пусть дан модуль n и некоторое число a, взаимно простое с модулем n. Рассмотрим последовательность степеней a, a 2, a t, Найдем наименьшее число k, при котором a k 1 mod n. Определение.

Незнакомые алгоритмы поиска простых чисел среди нечётных О.А. Черепанов В классической теории чисел есть две теоремы с именем Пьера Ферма Большая x n + y n = z n и Малая a 1(mod р). Но если о первой знают

ЛЕКЦИЯ 2 ВЫЧИСЛЕНИЕ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ Алгоритм Евклида При работе с большими составными числами их разложение на простые множители, как правило, неизвестно. Но для многих прикладных задач теории

Министерство образования и науки Российской Федерации ФГБОУ ВО «Тверской государственный университет» УТВЕРЖДАЮ Руководитель ООП Цветков ВП 2015г Рабочая программа дисциплины (с аннотацией) Теория чисел

Занятие 8 ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ПРОЦЕДУРЫ ИХ МАШИННОЙ ГЕНЕРАЦИИ При статистическом моделировании систем одним из основных вопросов является учет стохастических воздействий. Количество случайных

Арифметические алгоритмы Простые числа Решето Эратосфена Поиск делителей (наименьший и наибольший) Разложение числа на множители НОД и НОК Перевод в другую систему счисления Арифметика остатков Простые

Министерство образования Российской Федерации Уральский государственный педагогический университет А.П. Ильиных ТЕОРИЯ ЧИСЕЛ Учебное пособие Екатеринбург 2003 УДК 511 И 45 РЕЦЕНЗЕНТ: член - корреспондент

Алгоритм поиска гиперэллиптических кривых Об авторе Ю.Ф. Болтнев ст. преп., РГУ им. И. Канта. УДК 511 К.Г. Мкртчян СРАВНИТЕЛЬНЫЙ АНАЛИЗ 105 АЛГОРИТМОВ МЕТОДА КВАДРАТИЧНОГО РЕШЕТА 105 ДЛЯ ФАКТОРИЗАЦИИ БОЛЬШИХ

Лабораторная работа 11 Составить программу вычисления символа Лежандра Цель работы используя алгоритм для вычисления символа Лежандра, составить программу вычисления символа Лежандра. Задание к работе

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). II 1 / 78 Часть I Конечные поля (поля Галуа). II ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). II 2 / 78 Поля вычетов по модулю простого

СПРАВОЧНИК ПО МАТЕМАТИКЕ 5 9 классы МОСКВА «ВАКО» 201 УДК 32.851 ББК 4.262.22 С4 6+ Издание допущено к использованию в образовательном процессе на основании приказа Министерства образования и науки РФ

Лекция 3 4. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМА Принципы построения численных методов. Применение необходимых и достаточных условий безусловного экстремума эффективно для решения ограниченного

2008 г 3 Труды ФОРА ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ПРОСТЫХ И СОСТАВНЫХ ЧИСЕЛ Кубанский государственный университет, г. Краснодар Работа посвящена доказательству малой теоремы Ферма. В ней предлагается простой

Тема. Основы элементарной теории чисел и приложения-. Первообразные корни, индексы. Теоретический материал Пусть а, m натуральные взаимно простые числа, причем m, тогда, согласно теореме Эйлера, a m)

1 - Тема 1 Элементы теории погрешностей 11 Источники и классификация погрешностей Численное решение любой задачи, как правило, осуществляется приближенно, те с некоторой точностью Это может быть обусловлено

Дискретная математика Домашнее задание 22 (повторение), решения 1 Найдите максимальное количество рёбер в таких ориентированных графах на n вершинах, которые не имеют ориентированных циклов Решение Между

1 Показатели. Первообразные корни. 1.1 Понятие показателя. Простейшие свойства. Определение. Будем говорить, что число a, (a, n) = 1 принадлежит показателю N по модулю n, если - минимальное число, такое

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 1 / 78 Часть I Конечные поля или поля Галуа. II ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 2 / 78 Поля вычетов по модулю

Лекция 4. СТАНДАРТ AES. АЛГОРИТМ RIJNDAEL. Стандарт AES (Advnced Encrypton Stndrd) представляет собой новый стандарт шифрования с одним ключом, который заменил стандарт DES. Алгоритм Rjndel (рейн-дал)

20 Янв 2017 База ЕГЭ Задание 19 Решение всех прототипов задания 19 (база ЕГЭ). Задача 1366. Найдите шестизначное натуральное число, которое записывается только цифрами 2 и 0 и делится на 24. В ответе укажите

Симплекс-метод решения задач линейного программирования Основным численным методом решения задач линейного программирования является так называемый симплекс-метод. Термин «симплекс-метод» связан с тем

В.М. Ситников ТЕОРИЯ ЧИСЕЛ Учебное пособие Челябинск 204 0 Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Челябинский

ЗРОССИЙСКАЯ ОТКРЫТАЯ АКАДЕМИЯ ТРАНСПОРТА МОСКОВСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ПУТЕЙ СООБЩЕНИЯ Одобрено кафедрой «Железнодорожная автоматика, телемеханика и связь» О С Н О В Ы И Н Ф О Р М А Ц И О Н

ФГОС ИННОВАЦИОННА ШКОЛА РАБОЧАЯ ТЕТРАДЬ к учебнику «Математика. 6 класс» под редакцией академика РАН В.В. Козлова и академика РАО А.А. Никитина В ЧЕТЫРЕХ ЧАСТЯХ Часть 1 Москва «Русское слово» 2013 НАПРАВЛЕНИЕ

УДК 511. Кольца целых чисел квадратичных полей Журавлев Е.В., Токарев В.Н. Алтайский государственный университет, Алтайский государственный технический университет [email protected], [email protected]

Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования Национальный исследовательский университет «Высшая школа экономики»

Лабораторная работа Методы минимизации функций одной переменной, использующие информацию о производных целевой функции Постановка задачи: Требуется найти безусловный минимум функции одной переменной (

ЧАСТЬ 3 ПОСЛЕДОВАТЕЛЬНОСТЬ НЕЗАВИСИМЫХ ИСПЫТАНИЙ Лекция 4 НЕЗАВИСИМЫЕ ИСПЫТАНИЯ. ФОРМУЛА БЕРНУЛЛИ. АСИМПТОТИЧЕСКИЕ ФОРМУЛЫ МУАВРА ЛАПЛАСА И ПУАССОНА ЦЕЛЬ ЛЕКЦИИ: ввести понятие независимого испытания и

~ 1 ~ «Признаки монотонности функции» Теорема: Для того чтобы функция f(x), дифференцируемая на a,b возрастала (убывала) на a,b необходимо и достаточно, чтобы x a,b выполнялось неравенство f (x) 0 (f (x)

КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ Н.А. Корешков, М.Ф. Насрутдинов СБОРНИК ЗАДАЧ ПО ТЕОРИИ ЧИСЕЛ Казань 2016 Казанский (Приволжский) федеральный университет Н.А. Корешков, М.Ф. Насрутдинов СБОРНИК ЗАДАЧ

А. П. Иванов Методические указания Тема 4: Метод Ньютона решения нелинейных уравнений и систем уравнений факультет ПМ ПУ СПбГУ 2007 г. Оглавление 1. Решение скалярных уравнений...........................

Math-Net.Ru Общероссийский математический портал В. М. Журавлëв, П. И. Самовол, Экспоненциальные диофантовы уравнения и сумма цифр числа, Матем. просв., 2016, выпуск 20, 167 199 Использование Общероссийского

1. Требования к уровню подготовки учащихся. Учащийся, заканчивающий 9 класс, должен уметь: выполнять арифметические действия, сочетая устные и письменные приёмы; находить значения корня натуральной степени,

99 УДК 004.94 ЭФФЕКТИВНОСТЬ ИСПОЛЬЗОВАНИЯ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ В КРИПТОГРАФИЧЕСКИХ СИСТЕМАХ Губенко Н.Е., Назаров Е.А. Донецкий национальный технический университет, г. Донецк Кафедра компьютерных

11 Поточные криптосистемы 11.1 Поточные криптосистемы Напомним наше определение поточной криптосистемы. Пусть имеется слово X A длины X = T. Для зашифрования данного слова на ключе θ Θ выполняются следующие

СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ После изучения данной темы вы сможете: проводить численное решение задач линейной алгебры. К решению систем линейных уравнений сводятся многочисленные практические задачи, решение

9., 9. класс Модуль 5 «Последовательности. Степени и корни» В тесте проверяются теоретическая и практическая части. Последовательности Числовые последовательности. Способы задания числовых последовательностей:

Раздел 2 Теория пределов Тема Числовые последовательности Определение числовой последовательности 2 Ограниченные и неограниченные последовательности 3 Монотонные последовательности 4 Бесконечно малые и

Math-Net.Ru All Russian mathematical portal V. M. Zhuravlev, P. I. Samovol, Экспоненциальные диофантовы уравнения и сумма цифр числа, Mat. Pros., 2016, Issue 20, 167 199 Use of the all-russian mathematical

Рассмотрено на заседании МО учителей математики и физики 2013 г. Руководитель МО А.М.Бобкова Утверждаю 2013 г. Директор МАОУ лицея 29 А.И.Мексичев КАЛЕНДАРНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ ПО МАТЕМАТИКЕ в 6

Статистическое моделирование. Общая характеристика метода статистического моделирования На этапе исследования и проектирования систем при построении и реализации машинных моделей широко используется метод

Занятие 3 Задача 1. a)найти все первообразные корни по модулю 27. Заметим, что ϕ(27) = 27 9 = 18 = 2 3 2. Воспользуемся критерием и проверим, является ли 2 первообразным корнем по модулю 27: 2 6 64 10

Конспект к лекции. (Казань, 4 апреля 207 г.) Используемые обозначения Для неориентрированных графов мы используем обозначение G pv, Eq, где V есть множество вершин, а E множество рёбер. При этом мы допускаем

ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ПРОГРАММИРОВАНИЕ ЯЗЫКИ ПРОГРАММИРОВАНИЯ Обработка одномерных массивов данных (практическое занятие) Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем

Предельные теоремы для независимых одинаково распределенных случайных величин. Сходимость по вероятности сходимость с вероятностью единица. Неравенство П.Л.Чебышева. Закон больших чисел для последовательности

Министерство образования и науки Российской Федерации ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САРАТОВСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ЛЕКЦИЯ 7 ЭЛЛИТИЧЕСКИЕ КРИВЫЕ Эллиптические кривые это математический аппарат, который часто используется в различных алгоритмах шифрования. Он имеет ряд преимуществ: при использовании эллиптичесих кривых

Глава VIII. Общая теория делимости 1. Простые и неприводимые элементы области целостности 1. Основные понятия теории делимости в областях целостности. Напомним, что областью целостности называется коммутативное

РАЗДЕЛ 1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА 1.1. Требования к студентам: требуются базовые знания по математическому анализу, алгебре: ОК-8 ПК-3 Способность и постоянной готовностью совершенствовать и углублять свои

Муниципальное бюджетное общеобразовательное учреждение «Добринская основная общеобразовательная школа имени Спиридонова Николая Семеновича» РАБОЧАЯ ПРОГРАММА по математике для обучающихся 6Б класса с задержкой

По математике, 6 класс (УМК А.Г. Мерзляк) 2016-2017 учебный год Примерное тематическое планирование. Математика. 6 класс (I вариант. 5 часов в неделю, всего 175 часов; II вариант. 6 часов в неделю,

Приложение 5 к образовательной программе МБОУ CШ 2, утвержденной приказом директора от 27.06.2013 275П (в редакции приказа от 04.03.2016 69П) Рабочая программа учебного предмета «АЛГЕБРА» ФКГОС: 8-9 классы

«Согласовано» Заместитель директора по УВР МОУ СОШ с.пады /_Захарова М.В./ от «1»сентября 2016г. «Утверждаю» Директор МОУ СОШ с.пады /Почтарев А.Г./ Приказ 95 от «1»сентября2016г. РАБОЧАЯ ПРОГРАММА по

Множество натуральных и множество целых чисел. П.8. Пересечение и объединение множеств. П.10. Натуральные Целые МАТЕРИАЛЫ для сайта по математике 8 класс Учитель: (Субач М.В.) ТЕМА Знать Уметь Знать определение

Номер урока Тема урока КАЛЕНДАРНО - ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ 6 класс Кол-во часов Глава 1. Обыкновенные дроби. 1. Делимость чисел 24 ч 1-3 Делители и кратные 3 Делитель, кратное, наименьшее кратное натурального

8.3 класс, Математика (учебник Макарычев) 2016-2017 уч.год Тема модуля 5 «Квадратный корень. Степень с целым показателем» В тесте проверяются теоретическая и практическая части. ТЕМА Знать Уметь Знать

Тема 4. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ -1- Тема 4. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 4.0. Постановка задачи Задача нахождения корней нелинейного уравнения вида y=f() часто встречается в научных

2 3 5 7 11 13 17 19 23 29 31… $250.000…

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

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
# Листинг 1 # вводим N n = input("n=") # создаем пустой список для хранения простых чисел lst = # в k будем хранить количество делителей k = 0 # пробегаем все числа от 2 до N for i in xrange(2, n+1): # пробегаем все числа от 2 до текущего for j in xrange(2, i): # ищем количество делителей if i % j == 0: k = k + 1 # если делителей нет, добавляем число в список if k == 0: lst.append(i) else: k = 0 # выводим на экран список print lst
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
# Листинг 2 n = input("n=") lst = for i in xrange(2, n+1): for j in xrange(2, i): if i % j == 0: # если делитель найден, число не простое. break else: lst.append(i) print lst
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
# Листинг 3 n = input("n=") lst= for i in xrange(2, n+1): # пробегаем по списку (lst) простых чисел for j in lst: if i % j == 0: break else: lst.append(i) print lst
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим - это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
# Листинг 4 from math import sqrt n = input("n=") lst= for i in xrange(2, n+1): for j in lst: if j >
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
# Листинг 5 from math import sqrt n = input("n=") lst= for i in xrange(2, n+1): if (i > 10): if (i%2==0) or (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
# Листинг 6 from math import sqrt n = input("n=") lst= for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:
# Листинг 7 n = input("n=") lst= for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j*j-1 > i: lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst

При N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Решето Эратосфена:
# Листинг 8 n = input("n=") a = range(n+1) a = 0 lst = i = 2 while i <= n: if a[i] != 0: lst.append(a[i]) for j in xrange(i, n+1, i): a[j] = 0 i += 1 print lst

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Лекция_4_часть_2.

Арифметические алгоритмы и их применение в криптографии.

Натуральное число p, больше единицы называется простым, если оно делится нацело только на 1 и на себя.

Теорема (Эвклид). Множество простых чисел бесконечно.

Обозначим через p(x) функцию, которая равна числу простых чисел p в интервале 1 < x

x / ln x < p(x) < 1,106 x / ln x .

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

Простые числа встречаются довольно часто.

Заметим, что существует около 10151 простых чисел длиной от 1 до 512 бит включительно , а количество простых чисел меньших 2512 приблизительно равно 2503/ Для чисел близких n вероятность произвольно выбранному числу оказаться простым числом, равна 1/ln(n). При случайном выборе двух простых чисел в диапазоне от 1 до 151 бита вероятность совпадения этих чисел ничтожно мала. Простые числа играют

важную роль в современной криптографии. Многие современные криптографические системы с открытыми (или не симметричными) ключами формируются с применением простых чисел.

Для простых чисел будем рассматривать три задачи:

· построение простых чисел;

· проверка чисел на простоту;

· факторизация (разложения) чисел на простые множители.

На самом деле все эти три задачи фактически дают ответ на один вопрос: является ли рассматриваемое число простым. Но для каждой из этих задач применяются свои методы. Для первой задачи, используя необходимые условия простоты, можно давать ответы типа:

· заданное число n не простое;

· вероятность того, что заданное число n не простое, меньше заданного числа e.

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

Приведем некоторые определения, теоремы, алгоритмы, которые связаны с вопросами решения

поставленных задач

Определение 1. Числа Fk = 2a + 1, a = 2k, k = 0, 1, 2, …, называются числами Ферма.

Теорема 1. Число Ферма n = Fk при k > 0 является

простым тогда и только тогда, когда

Определение 2. Пусть p – простое число. Числа вида Mp = называются числами Мерсенна.

Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами - числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое число p имеет вид Mp , то число p(p+1)/2 является совершенным. Например,

3 = 2 2 – 1, 7 = 2 3 – 1

простые числа, и соответственно

Где Mp является числом Мерсенна. Напомним, совершенным числом называется число, которое равносумме всех своих делителей, меньших, чем оно само.

Числа Мерсенна редки. В 2001году было найдено тридцать девятое число Мерсенна для p = 1 3466 917.

Для проверки простоты чисел Мерсенна применяется следующая теорема .

Теорема 2. Пусть p – простое число, p > 2, Mp =

1. Рассмотрим последовательность L0, L1, …, которая

определяется соотношениями

L0 = 4, mod p, 0 ≤ j < p.

Число Mn – простое тогда и только тогда, когда Lq-2 =0 mod p.

ПРОВЕРКА НА ПРОСТОТУ

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

Теоретический материал к вопросу построения больших простых чисел можно найти в и . Здесь будут сформулированы только некоторые практические

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

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

проверяется, являются ли они простыми.

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

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

формирования простого числа.

Пробное деление

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

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

разделить число p на эти числа нацело нельзя, то число p – простое. Данный метод называется пробным делением. Этот метод трудоемок по числу арифметических операций, и он используется в основном для проверки небольших простых чисел.

Решето Эратосфена

Если мы хотим составить таблицу всех простых чисел среди чисел

2, 3,…, N, то надо последовательно вычеркнуть все числа, которые делятся

· на 2, кроме 2;

· на 3, кроме 3;

· на 5 кроме 5;

· на следующее число, которое не вычеркнуто,

кроме этого числа;

и т. д.В итоге среди чисел от 1 до N останутся лишь простые числа. Для реализации метода нужен большой объем памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим . Более того, разрабатываются специальные процессоры, на которых операции «просеивания» выполняются очень эффективно .

Замечание. Пробное деление и решето Эратосфена можно применять при решении задачи разложения целого числа на множители.

Решето Эратосфена.

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

Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

Пусть переменная p изначально равна двум - первому простому числу.

Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)

Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.

Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

Все не вычеркнутые числа в списке - простые числа.

На практике, алгоритм можно немного улучшить следующим образом. На шаге №3, числа можно вычеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p 2 станет больше, чем n .

Пример для n = 20

Запишем натуральные числа начиная от 2 до 20 в ряд:

Первое число в списке 2 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2 (каждое второе, начиная с 2^2 = 4):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Следующее невычеркнутое число 3 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 3^2 = 9):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Следующее невычеркнутое число 5 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 5 (каждое пятое, начиная с 5^2 = 25). И т. д.

Необходимо провести вычёркивания кратных для всех простых чисел p, для которых . В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Дляn = 20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.

Теорема Вильсона

Для любого P эквивалентны следующие условия:

1). P –простое;

2). (P-1)!=-1 (mod P)

Неэффективен из-за большой трудоемкости.

Малая теорема Ферма утверждает, что если n простое, то выполняется условие: при всех a из {1, 2, …, n −1} имеет место сравнение

an −1 ≡ 1 (mod n ) (1)

Из этой теоремы следует, что если сравнение (1) не выполнено хотя бы для одного числа a в интервале {1, 2, …, n −1}, то n - составное. Поэтому можно предложить следующий вероятностный тест простоты:

выбираем случайное число a из {1, 2, …, n a , n ) = 1;

n - составное»;

проверяем выполнимость сравнения (1);

если сравнение не выполнено, то ответ «n - составное»;

если сравнение выполнено, то ответ неизвестен, но можно повторить тест еще раз.

Числа Кармайкла (Carmichael Numbers)

Особо плохими для теста Ферма являются так называемые числа Кармайкла. Они обладают следующим свойством: для любого a такого, что (a , n ) = 1 верно

Первые три числа Кармайкла таковы: 561, 1105, 1729. Среди первых 100000000 чисел их всего 255. Лишь недавно (1994 г.) было доказано, что таких чисел бесконечно много.

Вероятностный тест Миллера-Рабина

Пусть n - нечетное и n − 1 = 2st , t - нечетное.

Если число n является простым, то при всех a > 1 выполняется сравнение

an −1 ≡ 1 (mod n )

Поэтому, рассматривая элементы {at , a 2t , …, a 2s −1t } можно заметить, что либо среди них найдется равный −1 (mod n ), либо at ≡ 1 (mod n ).

На этом замечании основан следующий вероятностный тест простоты:

выбираем случайное число a из интервала {1, 2, …, n −1} и проверяем с помощью алгоритма Евклида условие (a , n ) = 1;

если оно не выполняется, то ответ «n - составное»;

вычисляем at (mod n );

если at ≡ ±1 (mod n ), то переходим к п. 1;

вычисляем a 2t , …, a 2s −1t до тех пор, пока не появится −1;

если ни одно из этих чисел не равно −1, то ответ «n - составное»;

если мы достигли −1, то ответ неизвестен (и тест можно повторить еще раз).

Составное число не будет определено как составное с вероятностью 1 ⁄ 4. (см. ).

Теорема

Если верна расширенная гипотеза Римана, то достаточно проверять все a из {2, 3, …, +1} (см. ).

Построение больших простых чисел.

Тест на основе малой теоремы Ферма

Малая теорема Ферма утверждает, что если n простое число, то выполняется условие: при всех a Î {2,3, …, n – 1} имеет место сравнение An - 1 º 1 mod n.

На основании этой теоремы можно построить вероятностный алгоритм проверки на простоту числа n.

Если для некоторого целого a из интервала соотношение an - 1 º 1 mod n не выполняется, то число n – составное. Если же теорема выполняется, то вывод, что число n простое, сделать нельзя, так как теорема дает лишь необходимое условие. Поэтому, если

для некоторого a имеет место соотношение an - 1 º 1 mod n, то говорят, что число n является псевдопростым по основанию a . Существует бесконечно много пар чисел a и n, где n – составное и псевдопростое. Вообще для любого a > 1 существуют бесконечно много псевдопростых чисел по основанию a . Вообще, справедливы следующие два утверждения. Если пара (2, n) удовлетворяют сравнению an-1 º 1 mod n, то и пара чисел (2, 2n - 1) также ему удовлетворяют.

· Для любого простого числа n и любого a > 2 такого, что (a2 - 1, n) = 1, число (a2n - 1)/(a2 - 1) является псевдопростым по основанию a.

Определение. Составные числа n, для которых при всех основаниях выполняется сравнение an - 1 º 1 mod n, называются числами Кармайкла.

Дано число n и параметр g = 1 для идентификации

результата проверки.

1) делается случайный выбор целого числа a из интервала ;

2) используя алгоритм Эвклида, вычисляется НОД для чисел a и n;

3) если НОД больше 1, то выполняется шаг 7;

4) для числа a проверяется сравнение an - 1 º 1 mod n;

5) если сравнение не выполняется, то определяется параметр g = 0 (число составное) переход на шаг 7.

6) если сравнение выполнено, то можно повторить тест;

7) выдать результат проверки (g = 0 – число составное).

При завершении работы алгоритма возможны следующие выводы:

· число n – составное (g = 0);

· если g = 1, то число n является либо простым, либо составным и числом Кармайкла.

Здесь уместно заметить , что числа Кармайкла достаточно редки. Так существуют всего 2 163 чисел Кармайкла, которые не превосходят 25 000 000 000, и всего 16 чисел, которые не превосходят числа 100 000.

Схема алгоритма на базе малой теоремы Ферма

Пусть дано нечетное число p. Надо проверить является ли число p простым.

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

2. Если НОД (a, p) ¹ 1, то p – составное число.

3. Вычисляется сравнение L(a, p) º a(p - 1)/2 mod p.

4. Вычисляется символ Якоби J(a, p).

5. Если L(a, p) ¹ J(a, p), то число p – составное.

6. Если L(a, p) = J(a, p), то вероятность того, что

число p – составное не превышает 50 %.

Если проверка повторяется k раз, то вероятность

того, что число p – составное, не превышает 1/2k.

Тест Рабина - Миллера

Обоснование алгоритма Рабина - Миллера можно

найти в . Здесь дадим только самые общие

соображения. Известно, что если число p – простое, то

уравнение x2 º 1 mod p имеет лишь два решения: x º ±1

mod p. Итак, пусть p – нечетное целое число, которое

надо проверить на простоту. Если p – простое, то по

теореме Ферма для любого целого a взаимно простого с

p выполняется сравнение am - 1 º 1 mod p. Так как p - 1 –

четно, то получаем a(m - 1)/2 º ±1 mod p. Если оказывается,

что (m - 1)/2 – четно, то можно повторить рассуждение,

при котором получим, что a(m - 1)/4 º ±1 mod p, и т. д.

Поэтому, чтобы проверить на простоту нечетное

число p, выбираем случайным образом число a из

интервала и вычисляем a t (mod p), a 2 t (mod p0, …, a bt (mod p), где t – нечетное и число b = 2s. Если одно из этих чисел не совпадает с +1 или -1, то можно сделать вывод, что число p является числом составным. Если значения чисел совпадают с +1 или -1, то повторяем этот тест k раз. После повторения этого теста k раз вероятность того, что составное число p не будет выявлено, не превосходит 1/4k. После высказанных соображений перейдем к формулировке алгоритма Рабина - Миллера.

Схема алгоритма Рабина - Миллера

Пусть дано нечетное число p. Надо проверить является ли число p простым. Далее предположим, что p - 1 = 2st.

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

определяем k = 0.

2. Вычисляем с помощью алгоритма Эвклида НОД двух чисел a и p. Если НОД (a, p) ¹ 1, то p – составное число.

3. Вычисляем b º at mod p. Если b = 1 или b = p - 1, то число p вероятно простое.

4. Если b¹ 1 и b ¹ p - 1, то вычисляем b º b2 mod p и k= k + 1.

5. Если число b = p - 1, то число p вероятно простое.

Перейти на шаг 7.

6. Пока k < s выполнять пункт 4.

7. Завершить работу алгоритма.

Рассмотрим примеры.

Пример.

Пусть p = 181. Имеем p - 1 = 45 ´ 22. По

представленному разложению определяем значение

параметра t = 45.

1. Выбираем случайное число a = 52 < p, и

определяем k = 0.

2. Используем алгоритм Эвклида для вычисления

НОД двух чисел 52 и 181:

делим число 181 на число 52, получаем 181 = 52 ·

делим число 52 на число 25, получаем 52 = 25 · 2

делим число 25 на число 2, получаем 25 = 12 · 2 +

делим число 2 на число 1, получаем 2 = 1 · 2 + 0; получаем, что НОД двух чисел 181 и 52 равен 1.

Так как НОД не позволяет установить является ли число 181 составным, то продолжаем выполнять алгоритм Рабина - Миллера.

3. Последовательно вычисляем

b º 52t mod 181 º 5245 mod 181:

522 mod 181 º 2704 mod 181 º 170 mod 181,

524 mod 181 º 1702 mod 181 º 28900 mod 181 º

528 mod 181 º 1212 mod 181 º 14641 mod 181 º

5216 mod 181 º 1612 mod 181 º 25921 mod 181 º

5232 mod 181 º 382` mod 181 º 1444 mod 181 º

5240 mod 181 º (5232 mod 181)(528 mod 181) º

º (177 ´ 161) mod 181 º 28497 mod 181 º 80 mod

5241 mod 181º (5240 mod 181)(52 mod 181) º (80 ´

º 4160 mod 181 º 178 mod 181,

5245 mod 181 º (5241 mod 181)(524 mod 181) º (178 ´

º 21538 mod 181 = 180 mod 181.

Итак, получили b = 180 = p - 1. Откуда следует, что

число p = 181 вероятно простое.

Замечание.

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

чисел на простоту надо делать при помощи программ на компьютере.

В дается некоторое руководство при генерации простых чисел для практических приложений. Это руководство сводится к реализации нескольких этапов

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

2. Установите старший и младший биты равными 1.

Старший бит в этом случае гарантирует требуемую длину простого числа, а младший –

его нечетность.

3. Убедитесь, что число p не делится на малые простые числа 3, 5, 7, 11 и т. д. Наиболее

надежна проверка делимости на все простые числа, меньше 2000.

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

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

данное руководство снова.

Другое число p, если оно оказалось не простым, можно получить не генерируя новое, а последовательно перебирая все целые, начиная от p + 1, p + 2, и т. д., пока не найдется простое число.

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

Построение больших простых чисел и детерминированные алгоритмы проверки чисел на

Простоту/

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

Такой подход применяется, например, в стандарте

электронной цифровой подписи (ЭЦП) ГОСТ Р 34.10–94 и

основывается на следующей теореме .

Теорема 5.

Пусть p = qN + 1, где q – нечетное

простое число, N – четное число и p < (2q + 1)2. Число p

является простым, если выполняются два условия:

1) 2qN = 1 mod p;

2) 2N ≠ 1 mod p.

Генерация простого числа с использованием теоремы 5 осуществляется по несколько упрощенной в принятом стандарте схеме . Пусть требуется

сформировать простое число p длины t ≥ 17 бит. С этой целью строится убывающая последовательность чисел {ti}, где i = 0, 1, …, s, для которых t0 = t, ti = .

формулы pi - 1 = piN + 1, где число N удовлетворяет следующим условиям :

· N – четное;

· N – такое, что длина числа pi - 1 = piN + 1 в

точности должна быть равна ti - 1.

В стандарте ГОСТ дается некоторый алгоритм вычисления числа N. Для учебного варианта N –

случайное четное число, которое получают с помощью датчика случайных чисел (если N – нечетно, то N = N + 1).

Число pi - 1 считается полученным, если одновременно выполнены следующие два условия:

1) 2b = 1 mod pi, b = pi - 1N;

2) 2N ≠ 1 mod pi.

Если хотя бы одно из условий не выполняется, то значение числа N увеличивается на 2, и вычисляется

новое значение pi - 1, которое снова проверяется на простоту по двум условиям. Данный процесс продолжается до тех пор, пока не будет получено простое число pi - 1 (т. е. условия 1 и 2 алгоритма генерации простого числа будут выполнены).

Заметим, что с 2002 года вышеупомянутый отечественный стандарт ЭЦП заменен на новый ГОСТ Р 34.10–2001 .

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

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

Требования к алгоритму и его реализации

Требования к алгоритмам генерации случайных простых чисел сводятся к следующим двум:

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

Типовые алгоритмы генерации случайных простых чисел

Везде далее предполагается использование криптографически стойкого ГПСЧ , проинициализированного с помощью секретного ключа (детали зависят от используемого ГПСЧ и способа получения и представления ключа).

Тестирование простоты

Проверить (вероятную) простоту числа p , содержащего k битов, можно так:

Убедиться, что p не делится на небольшие простые числа 3, 5, 7, 11, и т.д. до некоторого небольшого предела (например, 256). Такая проверка позволяет эффективно отсечь множество заведомо составных чисел, прежде чем проверять их посредством более трудоёмких алгоритмов. Так, проверка делимости p на простые числа 2, 3, 5 и 7 отсеивает все четные числа и 54% нечетных чисел, проверка делимости p на все простые числа до 100 отсеивает 76% нечетных чисел, а проверка делимости p на все простые числа до 256 отсеивает 80% нечетных чисел.
Выполнить тест Миллера - Рабина с количеством раундов не меньше k .

Если число p не проходит хотя бы одной проверки - оно не является простым. В противном случае с большой вероятностью (зависящей от количества раундов) число p является простым.