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

метки: Генерация, Простой, Число, Теорема, Таблица, Квадрат, Надежность, Реализация

Теоретическое наполнение раздела «Операции с большими числами»

Большинство современных алгоритмов такие как ГОСТ Р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-битных операциях сложения, умножения и возведения в квадрат. Данный метод является более вычислительно быстрым, чем возведение в квадрат через умножение, так как в данном методе доминирует операция возведения в квадрат, которая в свою очередь более быстрая, чем операция умножения.

Возведение зданий методом надвижки из блочных элементов

... блока, поступающего на нее уже запертым на ключ. При возведении зданий из объемных элементов до 80% всех трудовых затрат переносится ... шахматном порядке, что значительно облегчает архитектурно-планировочные решения здания. Блочная схема зданий наиболее индустриальная, так как на стройплощадку завозят ... Эти зазоры облегчают выполнение монтажных операций и создают замкнутые воздушные прослойки, ...

Возведение в степень. В пособии предлагается дихотомический алгоритм. Рассматриваются два варианта этого метода — «слева направо» и «справа налево». В данном алгоритме используются операции умножения и возведения в квадрат для 256-, 512- или 1024-битных целых чисел.

Изложение каждого из методов сопровождается примерами.

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

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

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

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

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

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

p

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

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

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

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

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

Если р — простое, и p не делит a a ^p —¹ ? 1 (mod p)

Таким образом, если n-простое число, то для любого основания a будет выполняться сравнение a ⁿ —¹ ? 1 (mod n).

Если n — составное число, то такое сравнение будет выполняться лишь для некоторых a в силу случайного совпадения. На этом факте основан тест Ферма, который проверяет данное сравнение для случайным образом выбранных оснований a.

Разработка методического пособия «Генерация простых чисел» (2)

... алгоритмы генерации простых чисел с примерами. Целью данной работы является: Разработать методическое пособие на тему «Генерация простых чисел» для специальности « ... чисел; асимптотический закон распределения простых чисел; вероятностные тесты на простоту и генерация простых чисел случайным поиском; доказуемо простые числа и их построение. 2. Определить структуру и содержание методического пособия. ...

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

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

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

n — число Кармайкла 1) n свободно от квадратов (т.е. n = p ₁ •p₂ •…•p_k );

2) (p _i — 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 — составное число, каноническое разложение которого есть . Знаменатель символа Лежандра — простое число, а символа Якоби — составное.

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

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

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

В алгоритме теста встречается вычисление символа Якоби ().

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

Приготовление изделий из теста

... большая полость; допускаются небольшие трещины на поверхности. Влажность 23 %. Технология приготовления полуфабрикатов Технология приготовления песочного полуфабриката В тестомесильную машину загружают все сырье, за исключением ... выпечки, неравномерно раскатан пласт Песочный полуфабрикат бледный Низкая температура выпечки Приготовление теста состоит из двух стадий: 1. заварка муки в кипящей воде с ...

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

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

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

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

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

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

Студенту разъяснятся метод построения последовательности b ₀ , b₁ ,…,b_s , а именно то, что каждый последующий член данной последовательности является квадратом предыдущего по модулю n, а последний член есть ни что иное как aⁿ —¹ mod n. То есть на одном из шагов теста строиться последовательность квадратов по модулю n.

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

1.3. Теоретическое наполнение раздела «Доказуемо простые числа», В данном разделе рассмотрены алгоритмы которые позволяют строить числа

Данная тема редко и недостаточно полно затрагивается в учебно-методической литературе, несмотря на достаточно большую ее практическую значимость.

Подход к получению доказуемо простых чисел отличается от подхода, рассмотренного ранее. Для построения таких чисел не используется случайный поиск. С использованием таблицы простых чисел небольшого размера, построенной заранее, строится число m (равное произведению нескольких простых чисел либо произведению простых чисел и случайного числа), затем число n=2m+1 проверяется на простоту одним из нижеприведенных тестов.

Тест Миллера. Данный тест, основанный на теореме Сэлфриджа, пригоден для доказательства простоты любого нечетного числа, если известно разложение на простые сомножители числа, ему предстоящего. Однако этот тест достаточно трудоемок. Для некоторых чисел особого вида построены специальные доказательства простоты.

Теорема Сэлфриджа.

Пусть n—1=. n — простое, a: 1) a ^n—1 ?1(mod n);

2) 1(mod n).

Данная теорема приведена в пособии без доказательства.

Теорема Сэлфриджа дает удобный критерий для доказательства простоты числа. На основании этой теоремы построен алгоритм Миллера проверки чисел на простоту, который требуют полной факторизации числа n—1.

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

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

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

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

4. Построенное число n испытывается тестом Миллера с заданным параметром надежности.

Тест Миллера, приведенный в пособии, осуществляет проверку сравнений (1) и (2) теоремы Сэлфриджа для всех q _i по нескольким случайным основаниям a. Если для какого-то основания данные сравнения не выполняются, число отвергается (как, возможно, составное).

Количество оснований, по которым производится проверка, есть параметр надежности.

Следует заметить, что проверка условия (2) теоремы Сэлфриджа возможна благодаря тому, что проверяющему известны все простые числа из разложения числа n-1, а именно числа 2 и q _i . Для случайно выбранного (а не построенного) числа n проверка тестом Миллера была бы невозможна.

Числа q _i из разложения числа m не должны быть известны никому кроме лица, построившего данное число, иначе крипосистемы, построенные с использованием такого числа, станут уязвимыми для атак.

Тест, основанный на Теореме Поклингтона. Теорема Сэлфриджа дает четкий критерий для проверки простоты числа n, однако требует знания полного разложения числа (n—1) на простые сомножители. Следующая теорема позволяет ограничиться частичной факторизацией (n—1).

Теорема Поклингтона.

Пусть n=RF+1, F= — каноническое разложение.

Если a: 1) a ^n—1 ?1(mod n);

2) 1(mod n) .

p?1(mod F) для любого простого pn.

Итак, если разложить n—1 на два сомножителя n—1=RF, где F>—1, то, если для некоторого a будут выполнены условия Теоремы Поклингтона (1) и (2), то n — простое.

Таким образом, можно значительно сократить количество проверок по сравнению с тестом Миллера.

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

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

2. Строится число F=(где q _i —случайные простые числа из таблицы, б_i — случайные целые числа), размер которого на 1 бит больше половины требуемого размера для простого числа;

3. Вычисляется значение n=RF+1, где R — случайное четное число, размер которого на 1 бит меньше размера F;

4. Построенное число n испытывается тестом на основании теоремы Поклингтона с заданным параметром надежности.

Такой тест, приведенный в пособии, осуществляет проверку сравнений (1) и (2) теоремы Поклингтона для всех q _i из разложения числа F по нескольким случайным основаниям a. Если для какого-то основания данные сравнения не выполняются, число отвергается (как, возможно, составное).

Количество оснований, по которым производится проверка, есть параметр надежности.

Заметим, что число, построенное с помощью данного теста, более предпочтительно для использования в качестве модуля криптосистем, поскольку никто, даже его создатель, не знает полного разложения числа n—1.

Для иллюстрации алгоритма в пособии приведен пример расчета алгоритма со следующими параметрами: испытуемое число(n = RF+1) равно 4021, разложение n-1 — 2 ² ·3·5·67 , R=67 , F=2² ·3·5=60. Студенту разъясняется, что в данном примере вероятность того, что наугад выбранное a будет удовлетворять условиям теоремы Поклингтона для данного примера, есть (1—1/67)?0,985.

Процедура генерации простых чисел заданной длины ГОСТ Р 34.10-94. Данный процедура позволяет строить доказуемо простые числа большего размера на основе простых чисел меньшего размера. Основана она на теореме Диемитко, которая гласит что для n=qR+1( где q — простое число, R — четное, R<4(q+1)) если найдется a<n: 1) a ⁿ —¹ ?1(mod n); 2) 1(mod n), то n — простое число.

1.4. Разработка заданий для лабораторных и самостоятельных работ

Для закрепления материала лекционных занятий нами были разработаны задания для лабораторных и самостоятельных работ. Всего разработано три комплекта заданий, соответствующие трем темам: «Операции с большими числами», «Вероятностные тесты на простоту» и «Доказуемо простые числа». Предполагается последовательное выполнение этих заданий, в порядке, изложенном в методическом пособии. На изучения каждой из тем, соответствующих разделам пособия, отводится по 2 часа лабораторных занятий и по 2 часа самостоятельной работы. Программная реализация алгоритмов осуществляется студентами в компьютерном классе под руководством преподавателя, отладка программы и оформление результата — в часы, отведенные для самостоятельной работы.

Программные модули разработанные в рамках перечисленных тем, описанные в них классы и функции, используются студентами в дальнейшем курсе предмета «Криптографические методы защиты информации» для выполнения лабораторных работ по реализации и использованию асимметричных алгоритмов шифрования, алгоритмов цифровой подписи, криптографических протоколов, а также для выполнения курсовой работы по предмету.

Задание к первому разделу — «Операции с большими числами» не разделено на варианты, так как результат данной лабораторной работы подразумевает разработку класса для работы с большими числами, который используется при выполнении лабораторных работ ко второй и третьей главам. Выполнение задания к первому разделу, таким образом, является базовым элементом программ, которые разрабатываются студентами в дальнейшем, на протяжении всего курса предмета «КМЗИ».

Задания к разделу «Операции с большими числами» включают в себя создание класса больших чисел, в котором заданы следующие операции: сложение, вычисление остатка от деления, умножения двух чисел (методом Карацубы), возведение в квадрат, возведение в степень (дихотомический алгоритм).

Используя данные операции можно получить практически любую арифметическую операцию.

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

Операции умножения и возведения в квадрат используются при реализации операции возведение в степень и.т.д. Исходя из вышеупомянутых критериев, мы сформулировали задания в порядке возрастания сложности, а именно первой операцией, которую предстоит реализовать студенту, является операция сложения, как уже было описано выше, она является базовой операцией, использующейся при реализации других операций. Далее студенту предстоит реализовать операцию умножения. При реализации данной операции используется операция сложения. Следующим заданием является реализация операции возведения в квадрат, в которой используются реализованные ранние операции сложения и умножения. Наконец, студенту предстоит реализовать операцию возведения в степень, для которой используются все ранее реализованные операции.

Существует большое количество различных вероятностных тестов на простоту. Из большинства тестов было выбрано три «основных», которые и стали предметом изучения в рамках лабораторной работы к главе «Вероятностные тесты на простоту». Данные тесты были выбраны нами исходя из следующего: другие тесты либо гораздо сложнее, либо не имеют принципиальных отличий от выбранных нами тестов. Мы разработали три варианта лабораторной работы, в каждом из вариантов студенту предлагается реализовать один из тестов, в зависимости от варианта, и закрепить свои знания, выполняя задания на использование Асимптотического закона распределения простых чисел. Результат лабораторной работы предлагается оформить в виде таблицы, что позволило бы преподавателю сократить время, затрачиваемое на проверку данной лабораторной работы (это связано с тем, что в данной лабораторной работе используются алгоритмы, компьютерный расчет которых на больших числах занимает достаточно много времени (на персональном компьютере)).

№	1	2	…	10
p
n

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

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

В задании к главе «Доказуемо простые числа» студенту предлагается реализовать три теста основанных на трех различных принципах (Данные тесты описаны в разделе 1.3).

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

№	1	2	3	4	5	6	7	8	9	10
p
Результат проверки вероятностным тестом
k

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

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

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

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

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

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

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

  1.5.

Тесты для самопроверки

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

Тесты для самопроверки для раздела «Операции с большими числами» представляет собой две таблицы (в первой таблице длина чисел не превышает 64 бит, во второй длина чисел не превышает 128бит), в столбцы которой занесены числа a и b, название операции и результат.

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

1. сложение, так как это базовая операция, использующаяся при реализации всех остальных;

2. умножение, так как при реализации данной операции используется только сложение, то для студента не составит труда найти ошибку в алгоритме, зная, что операция сложения работает верно;

3. вычисление остатка от деления, так как при реализации данной операции используется битовый сдвиг, сложение и вычитание;

4. возведение в квадрат, так как при реализации данной операции используются операции сложения и умножения;

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

Пример тестовых данных приведен в следующей таблице.

a	b	a+b	a*b	a mod b	a 2	a b
0 51	0 7	0 58	0 357	0 2	0 2601	0 897410677851
0 78	0 5	0 83	0 390	0 3	0 6084	0 2887174368
0 36	0 4	0 40	0 144	0 0	0 1296	0 1679616
0 21	0 10	0 31	0 210	0 1	0 441	0 16679880978201
0 5	0 12	0 18	0 60	0 5	0 25	0 244140625

Числа a и b подаются в программу, реализованную студентом, на вход, а данные в колонках «a+b», «a*b», «a mod b», «a ² », «a^b » это результаты которые должна вернуть программа при данных операциях (т.е. на основе этих данных студент делает вывод о корректности, реализованной им операции).

Следует отметить, что в таблице числа записаны «0 210» это следует понимать как старшую и младшую часть числа.

Также следует реализованные операции проверять сначала на данных из таблицы с малыми значениями (64 бита), при успешном результате следует проверить на данных из второй таблицы(128 бит).

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

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

Поэтому если мы будем проверять составные числа тестом, то иногда результат будет «простое» но чаще «составное». Стоит отметить, что для теста Ферма существует класс чисел Кармайкла, которые являются составными, но всегда принимаются за «простые». Такие числа также внесены в таблицу для самопроверки.

	Числа для проверки	Результат теста
Простые числа	0 9781	Всегда «простое»
Числа Кармайкла	0 2465	для тестов Миллера-Рабина и Соловея-Штрассена- чаще «составное»,чем «простое»
Составные, нечетные, не Кармайкла	0 3871	Чаще «составное»,чем «простое»

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

p	(p-1)	Вероятность ошибки (вероятность того, что число будет принято за составное)
13	2 2 *3	0,66666
29	2*2*7	0,57142
61	2*2*3*5	0,73333
97	2 5 *3	0,66666

p	Разложение F	R	Вероятность ошибки (вероятность того, что число будет принято за составное)
13	2*2	3	0,5
29	7	4	0,14285
61	3*5	4	0,46666
97	3*2 2	8	0,66666
157	13	8	0,125

< ………..