Разработка методического пособия на тему "Генерация простых чисел" (стр. 2 из 7)
В каждом разделе выделены теоретическая часть, задания для самостоятельной работы, также было решено включить во второй и третий раздел тестовые данные для программ, разработанных студентами, чтобы каждый студент имел возможность самостоятельно проверить корректность работы своей программы. Упрощенно, тестовые данные представляют собой данные на вход программы и данные, которые должны быть получены на выходе. Также к каждой паре «вход-выход» приложено предположительное определение ошибки алгоритма в случае несовпадения полученного результата с ожидаемым. Более подробно эти тестовые данные описаны в разделе 1.6.
1.1. Теоретическое наполнение раздела «Операции с большими числами»
Большинство современных алгоритмов такие как ГОСТ Р34.11-94, ГОСТ Р 34.11-2001, DSA и EСDSA накладывают условия на длину простого числа, например в ГОСТ Р 34.11-2001 длина простого числа должна быть больше 255 бит, а по стандарту DSA 512≤|p|≤1024. Для реализации данных алгоритмов необходимо умение работать с «большими» числами, а именно знать, как они представляются в памяти компьютера, и выполнять над ними арифметические операции.
Все алгоритмы, описанные в первой части пособия, приведены для случая, когда на основе класса 64-битных целых чисел описывается класс 128-битных целых. Пользуясь принципами, описанными для этого случая, студенту предоставляется самостоятельно построить класс 256- или 512-, 1024-битных целых чисел.
В данной главе описаны алгоритмы, используя которые можно получить практически любую арифметическую операцию, а именно: сложение, умножения двух чисел (методом Карацубы), возведение в квадрат, вычисление остатка от деления, возведение в степень (дихотомический алгоритм). Все операции над большими числами описаны через следующие стандартные операции над 64-битными целыми числами: сложение, вычитание, вычисление остатка от деления, возведение в квадрат, возведение в n-ю степень.
Операция сложения – это первая операция, описываемая в пособии, поэтому она рассмотрена наиболее подробно. Предлагается метод с использованием стандартной операции сложения 64-битных чисел. Результат сложения двух n-битных чисел предлагается помещать в 2n-битное число с тем, чтобы при выполнении криптографических преобразований промежуточный результат не выходил за размеры класса.
Вычисление остатка от деления. В пособии предлагается метод Барретта. В данном методе используются стандартные 64-битные операции сложение, умножение, вычитание, возведение в n-ю степень, вычисление остатка от деления.
Умножение 2х чисел. В пособии предлагается метод Карацубы. В данном методе используются стандартные 64-битные операции сложение, умножение, вычитание, возведение в n-ю степень, вычисление остатка от деления. Данный метод дает преимущество в скорости вычисления, так как позволяет сократить количество операций умножения с 4 до 3 по сравнению с традиционным подходом. Наряду с методом Карацубы, описывается метод умножения «столбиком» (традиционный подход) и производится сравнение этих двух методов.
Возведение в квадрат. В пособии предлагается метод, основанный на стандартных 64-битных операциях сложения, умножения и возведения в квадрат. Данный метод является более вычислительно быстрым, чем возведение в квадрат через умножение, так как в данном методе доминирует операция возведения в квадрат, которая в свою очередь более быстрая, чем операция умножения.
Возведение в степень. В пособии предлагается дихотомический алгоритм. Рассматриваются два варианта этого метода – «слева направо» и «справа налево». В данном алгоритме используются операции умножения и возведения в квадрат для 256-, 512- или 1024-битных целых чисел.
Изложение каждого из методов сопровождается примерами.
1.2. Теоретическое наполнение раздела «Вероятностные тесты на простоту»
В основном, учебники по криптографии упоминают или приводят именно вероятностные тесты на простоту. Простые числа, построенные случайным поиском с проверкой вероятностными тестами, используются в криптосистемах RSA, Рабина (и других криптосистемах, основанных на проблеме факторизации).
В данной главе выделены следующие разделы: асимптотический закон распределения простых чисел, тест Ферма на простоту, тест Соловея-Штрассена, тест Миллера-Рабина.
Асимптотический закон распределения простых чисел. Данный раздел был включен во 2-ю главу для того, чтобы дать студенту представление об эффективности случайного поиска простых чисел, поскольку именно случайный поиск простых чисел используется в алгоритмах построения с использованием вероятностных тестов на простоту.
Вводится теоретико-числовая функция π(x) – количество простых чисел, меньших x. В пособии приводится собственно теорема (асимптотический закон), которая определяет предельные характеристики распределения простых чисел среди целых положительных чисел, а также теорема Чебышева, определяющая границы интервала, на котором расположено π(x) для различных x.
Для иллюстрации использования приведенных теорем рассмотрен пример. В примере для множества целых положительных 32-битных чисел (таких, что старший бит равен 1) с использованием асимптотического закона вычислена вероятность того, что наугад выбранное из этого множества число окажется простым. Такая вероятность приняла следующее значение:
p»
Если сузить поиск до нечетных чисел, то вероятность возрастет в 2 раза и составит p»
.После чего в методическом пособии сделан обоснованный вывод о том, что случайный поиск простых чисел целесообразен.
Тест Ферма. В данном разделе рассмотрен алгоритм теста Ферма на простоту. Данный тест позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа.
В основе теста Ферма лежит теорема Ферма. Ее формулировка приведена в тексте пособия (без доказательства)
Теорема Ферма (малая)
Если р – простое, и p не делит a
ap–1 ≡ 1 (modp)Таким образом, если n-простое число, то для любого основания a будет выполняться сравнение an–1 ≡ 1 (modn). Если n – составное число, то такое сравнение будет выполняться лишь для некоторых a в силу случайного совпадения. На этом факте основан тест Ферма, который проверяет данное сравнение для случайным образом выбранных оснований a.
Также в пособии отмечено тот факт что, для данного теста существуют такие составные числа, для которых сравнение an–1 ≡ 1 (modn) выполняются при любом основании 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, а называется числителем, р – знаменателем символа Лежандра.