Разработка методического пособия на тему "Генерация простых чисел" (стр. 3 из 7)
Символ Якоби определяется равенством:
, где n – составное число, каноническое разложение которого есть 
. Знаменатель символа Лежандра – простое число, а символа Якоби – составное.Свойства символа Лежандра и символа Якоби совпадают, за исключением критерия Эйлера. Критерий Эйлера выполняется для символа Лежандра, и не выполняется для символа Якоби.
Критерий Эйлера: Для символа Лежандра
Алгоритм вычисления этих двух символов одинаков, так как он основан на использовании свойств символов Якоби и Лежандра.
В алгоритме теста встречается вычисление символа Якоби (
). В пособии приведен алгоритм вычисления данного символа, без свойств, на которых основано вычисление данного символа. Студенту разъясняется роль данного символа в алгоритме.Для данного теста приводится оценка вероятности ошибки, равная εt, где t – число итераций теста, параметр надежности, а
< 
.Из данной оценки надежности теста сделан вывод о том, что оценка надежности для теста Соловея–Штрассена гораздо лучше, чем для теста Ферма, даже в том случае, когда φ(n) ненамного меньше n. Если на одной итерации вероятность ошибочного решения теста не превышает ½, то уже на двух итерациях – ¼, на трех – 1/8, и т. д. Уже на 14 итерациях вероятность ошибочного решения на превышает 0, 0001.
Также студенту представлен пример, иллюстрирующий вычисление символа Якоби
. В заключении данного раздела студенту представлен пример работы алгоритма со следующими параметрами: испытуемое (простое) число равно 43, параметр надежности равен 2.Тест Миллера-Рабина. Тест Миллера-Рабина, как и тесты Ферма и Соловея-Штрассена, строит вероятно простые числа, то есть число, опознанное этим тестом как простое, может с некоторой малой вероятностью оказаться составным, однако вероятность ошибки у теста Миллера-Рабина гораздо ниже, чем у первых двух тестов. Как правило, для опознания простого числа достаточно одной итерации теста, но все же студенту рекомендуется использовать не менее пяти итераций.
Данный тест основан на теореме ферма, которая гласит если n – простое число, то для любого a: 0<a<n выполняется an—1≡1(modn).
В пособии приведена оценка вероятности ошибки ε ≤
, то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма. Если на одной итерации вероятность ошибочного решения в тесте не превышает ¼, то на двух итерациях – 1/16, на трех – 1/64. Для того, чтобы вероятность ошибки не превышала 0, 0001, требуется всего 7 итераций, что в 2 раза меньше, чем для теста Соловея-Штрассена. На практике рекомендуется использовать не менее пяти итераций теста, что обеспечивает вероятность вынесения ошибочного решении не более 0,001.Студенту разъяснятся метод построения последовательности b0, b1,…,bs , а именно то, что каждый последующий член данной последовательности является квадратом предыдущего по модулю n, а последний член есть ни что иное как an—1modn. То есть на одном из шагов теста строиться последовательность квадратов по модулю n.
В качестве примера, иллюстрирующего работу теста, были приведены расчеты. В качестве испытуемого числа было выбрано составное число 65, параметр надежности был выбран равный 5.
1.3. Теоретическое наполнение раздела «Доказуемо простые числа»
В данном разделе рассмотрены алгоритмы которые позволяют строить числа, простота которых не вызывает сомнений, а именно тест Миллера на простоту, тест основанный на теореме Поклингтона, Процедура генерации простых чисел заданной длины ГОСТ Р 34.10-94. Последний алгоритм используется в отечественном стандарте шифрования ГОСТ Р 34.10-94.
Данная тема редко и недостаточно полно затрагивается в учебно-методической литературе, несмотря на достаточно большую ее практическую значимость.
Подход к получению доказуемо простых чисел отличается от подхода, рассмотренного ранее. Для построения таких чисел не используется случайный поиск. С использованием таблицы простых чисел небольшого размера, построенной заранее, строится число m (равное произведению нескольких простых чисел либо произведению простых чисел и случайного числа), затем число n=2m+1 проверяется на простоту одним из нижеприведенных тестов.
Тест Миллера. Данный тест, основанный на теореме Сэлфриджа, пригоден для доказательства простоты любого нечетного числа, если известно разложение на простые сомножители числа, ему предстоящего. Однако этот тест достаточно трудоемок. Для некоторых чисел особого вида построены специальные доказательства простоты.
Теорема Сэлфриджа.
Пусть n—1=
. n – простое, 
a: 1) an—1≡1(mod n);2)
1(modn).Данная теорема приведена в пособии без доказательства.
Теорема Сэлфриджа дает удобный критерий для доказательства простоты числа. На основании этой теоремы построен алгоритм Миллера проверки чисел на простоту, который требуют полной факторизации числа n—1.
Алгоритм построения простого числа с помощью теста Миллера следующий:
1. Строится таблица малых простых чисел qi (или используется готовая таблица);
2. Строится число m=
(где qi—случайные простые числа из таблицы, αi – случайные целые числа), размер которого на 1 бит меньше требуемого размера для простого числа;3. Вычисляется значение n=2m+1;
4. Построенное число n испытывается тестом Миллера с заданным параметром надежности.
Тест Миллера, приведенный в пособии, осуществляет проверку сравнений (1) и (2) теоремы Сэлфриджа для всех qi по нескольким случайным основаниям a. Если для какого-то основания данные сравнения не выполняются, число отвергается (как, возможно, составное). Количество оснований, по которым производится проверка, есть параметр надежности.
Следует заметить, что проверка условия (2) теоремы Сэлфриджа возможна благодаря тому, что проверяющему известны все простые числа из разложения числа n-1, а именно числа 2 и qi. Для случайно выбранного (а не построенного) числа n проверка тестом Миллера была бы невозможна.
Числа qi из разложения числа m не должны быть известны никому кроме лица, построившего данное число, иначе крипосистемы, построенные с использованием такого числа, станут уязвимыми для атак.
Тест, основанный на Теореме Поклингтона. Теорема Сэлфриджа дает четкий критерий для проверки простоты числа n, однако требует знания полного разложения числа (n—1) на простые сомножители. Следующая теорема позволяет ограничиться частичной факторизацией (n—1).
Теорема Поклингтона.
Пусть n=RF+1, F=
- каноническое разложение.Если
a: 1) an—1≡1(mod n);2)
1(modn) . 
p≡1(modF) для любого простого p\n.Итак, если разложить n—1 на два сомножителя n—1=RF, где F>
—1, то, если для некоторого a будут выполнены условия Теоремы Поклингтона (1) и (2), то n – простое.Таким образом, можно значительно сократить количество проверок по сравнению с тестом Миллера.
Алгоритм построения простого числа с помощью теста на основании теоремы Поклингтона следующий:
1. Строится таблица малых простых чисел qi (или используется готовая таблица);
2. Строится число F=
(где qi—случайные простые числа из таблицы, αi – случайные целые числа), размер которого на 1 бит больше половины требуемого размера для простого числа;3. Вычисляется значение n=RF+1, где R – случайное четное число, размер которого на 1 бит меньше размера F;
4. Построенное число n испытывается тестом на основании теоремы Поклингтона с заданным параметром надежности.
Такой тест, приведенный в пособии, осуществляет проверку сравнений (1) и (2) теоремы Поклингтона для всех qi из разложения числа F по нескольким случайным основаниям a. Если для какого-то основания данные сравнения не выполняются, число отвергается (как, возможно, составное). Количество оснований, по которым производится проверка, есть параметр надежности.
Заметим, что число, построенное с помощью данного теста, более предпочтительно для использования в качестве модуля криптосистем, поскольку никто, даже его создатель, не знает полного разложения числа n—1.