Разработка методического пособия на тему "Генерация простых чисел"

дипломная работа

1.2. Теоретическое наполнение раздела «Вероятностные тесты на простоту»

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

В данной главе выделены следующие разделы: асимптотический закон распределения простых чисел, тест Ферма на простоту, тест Соловея-Штрассена, тест Миллера-Рабина.

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

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

Для иллюстрации использования приведенных теорем рассмотрен пример. В примере для множества целых положительных 32-битных чисел (таких, что старший бит равен 1) с использованием асимптотического закона вычислена вероятность того, что наугад выбранное из этого множества число окажется простым. Такая вероятность приняла следующее значение:

p

Если сузить поиск до нечетных чисел, то вероятность возрастет в 2 раза и составит p.

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

Тест Ферма. В данном разделе рассмотрен алгоритм теста Ферма на простоту. Данный тест позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа.

В основе теста Ферма лежит теорема Ферма. Ее формулировка приведена в тексте пособия (без доказательства)

Теорема Ферма (малая)

Если р - простое, и p не делит a ap-1 ? 1 (mod p)

Таким образом, если n-простое число, то для любого основания a будет выполняться сравнение an-1 ? 1 (mod n). Если n - составное число, то такое сравнение будет выполняться лишь для некоторых a в силу случайного совпадения. На этом факте основан тест Ферма, который проверяет данное сравнение для случайным образом выбранных оснований a.

Также в пособии отмечено тот факт что, для данного теста существуют такие составные числа, для которых сравнение an-1 ? 1 (mod n) выполняются при любом основании a. Поэтому, каково бы ни было значение параметра надежности (то есть количество перебранных оснований a), тест Ферма будет принимать такое составное число за простое. Такие числа называются числами Кармайкла.

Следует отметить, что вид чисел Кармайкла определяется теоремой Кармайкла.

Теорема Кармайкла:

n - число Кармайкла 1) n свободно от квадратов (т.е. n = p1•p2•…•pk);

2) (pi - 1)(n - 1), i = 1,…,k ;

3) k .

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

Для данного теста приводится оценка вероятности ошибки, равная еt, где е , где - функция Эйлера, n - испытуемое число , t - параметр надежности.

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

Если тест показал, что испытуемое число является простым, то подразумевается, что данное число является простым с вероятностью 1- еt.

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

В качестве примера иллюстрирующего работу теста были приведены расчеты, в качестве испытуемого числа было выбрано простое число 43, параметр надежности был выбран равный 2, основания, по которым проводилась проверка, были равны 35 и 13. При этом сравнение * выполнилось по основанию 35 и по основанию 13. Тест, таким образом, выдал ответ «43 - простое число».

Тест Соловея-Штрассена. В данном разделе рассмотрен алгоритм теста на простоту Соловея-Штрассена. Так же как и тест Ферма, данный тест позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа.

Этот тест основан на различии между символами Якоби и Лежандра.

Символом Лежандра называется символ , где p - простое число, Q(p) - множество квадратичных вычетов по модулю p, - множество квадратичных не вычетов по модулю p , а называется числителем, р - знаменателем символа Лежандра.

Символ Якоби определяется равенством:, где n - составное число, каноническое разложение которого есть . Знаменатель символа Лежандра - простое число, а символа Якоби - составное.

Свойства символа Лежандра и символа Якоби совпадают, за исключением критерия Эйлера. Критерий Эйлера выполняется для символа Лежандра, и не выполняется для символа Якоби.

Критерий Эйлера: Для символа Лежандра

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

В алгоритме теста встречается вычисление символа Якоби (). В пособии приведен алгоритм вычисления данного символа, без свойств, на которых основано вычисление данного символа. Студенту разъясняется роль данного символа в алгоритме.

Для данного теста приводится оценка вероятности ошибки, равная еt, где t - число итераций теста, параметр надежности, а < .

Из данной оценки надежности теста сделан вывод о том, что оценка надежности для теста Соловея-Штрассена гораздо лучше, чем для теста Ферма, даже в том случае, когда ц(n) ненамного меньше n. Если на одной итерации вероятность ошибочного решения теста не превышает Ѕ, то уже на двух итерациях - ј, на трех - 1/8, и т. д. Уже на 14 итерациях вероятность ошибочного решения на превышает 0, 0001.

Также студенту представлен пример, иллюстрирующий вычисление символа Якоби . В заключении данного раздела студенту представлен пример работы алгоритма со следующими параметрами: испытуемое (простое) число равно 43, параметр надежности равен 2.

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

Данный тест основан на теореме ферма, которая гласит если n - простое число, то для любого a: 0<a<n выполняется an--1?1(mod n).

В пособии приведена оценка вероятности ошибки е ? , то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза - для теста Ферма. Если на одной итерации вероятность ошибочного решения в тесте не превышает ј, то на двух итерациях - 1/16, на трех - 1/64. Для того, чтобы вероятность ошибки не превышала 0, 0001, требуется всего 7 итераций, что в 2 раза меньше, чем для теста Соловея-Штрассена. На практике рекомендуется использовать не менее пяти итераций теста, что обеспечивает вероятность вынесения ошибочного решении не более 0,001.

Студенту разъяснятся метод построения последовательности b0, b1,…,bs , а именно то, что каждый последующий член данной последовательности является квадратом предыдущего по модулю n, а последний член есть ни что иное как an--1 mod n. То есть на одном из шагов теста строиться последовательность квадратов по модулю n.

В качестве примера, иллюстрирующего работу теста, были приведены расчеты. В качестве испытуемого числа было выбрано составное число 65, параметр надежности был выбран равный 5.

Делись добром ;)