Лабораторная работа №5

Простые числа и простейшие теоретико-числовые функции

Цель работы:

• Ознакомиться с генератором простых чисел на основе алгоритма «Решето Эратосфена» библиотеки “FLINT\C”.

• Изучить один из вероятностных тестов на простоту – тест Миллера-Рабина.

• Изучить теоретико-числовые функции, такие как НОД, НОК, вычисление мультипликативного обратного, извлечение квадратного корня из а по модулю M, извлечение квадратного корня из а по модулю p*q.

• Ознакомиться с представлением теоретико-числовых функций в библиотеки “FLINT\C”.

Задание

1. Программно реализовать алгоритм «Решето Эратосфена» (верхняя граница поиска берется согласно варианта в таблице 1).

2. Несколько чисел подвергнуть вероятностному тесту простоты Миллера-Рабина.

3. Для чисел, которые прошли тест Миллера-Рабина (являются простыми) программно реализовать некоторые из теоретико-числовых функций согласно варианта (таб.1).

4. Сделать выводы на основе результатов, полученных, после тестирования.

Методические указания к работе

Простые числа

Простое число — это натуральное число, большее единицы, имеющее ровно два натуральных делителя: 1 и само себя.

Натуральное число, имеющее больше двух делителей, называют составным.

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

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

Алгоритм «Решето Эратосфена» и его представление в FLINT\C

Алгоритм “Решето Эратосфена” является самым простым способом нахождения списка простых чисел до некоторого значения. Если необходимо составить таблицу всех простых чисел среди чисел 2, 3, ..., N, то нужно вначале вычеркнуть все числа, делящиеся на 2, кроме 2. Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на 3. Затем взять следующее невычеркнутое число (т. е. 5) и вычеркнуть все последующие делящиеся на него числа, и так далее. В итоге останутся лишь простые числа.

Генератор простых чисел (решето Эратосфена)

Синтаксис: ULONG * genprimes (ULONG N);

Вход: N (верхняя граница поиска)

Возврат: Указатель на вектор значений типа ULONG. содержащий простые числа, меньшие либо равные N. (На нулевой позиции - число най­денных простых чисел) или

NULL ,при ошибке процедуры выделения динамической памяти.

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

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

Алгоритмы такого рода называются тестами простоты. Существует множество полиномиальных тестов простоты. Большинство таких алгоритмов являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии.

Вероятностный тест на простоту про­водится следующим образом. Выбирается случайное a є N, 1 ≤ a <n, и для него проверяется выполнение некоторых условий. Если какое-то из условий не выполнено, то число п — составное, поскольку для простых чисел эти условия являются необходимыми. Если же все усло­вия выполнены, то из этого еще не следует простота п. Однако можно будет считать, что «п — простое число с некоторой вероятностью». Чем больше значений a протестировано, тем ближе эта вероятность к единице.

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

Синтаксис: int prime_l (CLINT n, unsigned int a, unsigned int iter);

Вход: n (тестируемое число)

a >2 ( (число простых чисел, на которое проверяется число n )

iter (число итераций теста)

Возврат: 1, если тестируемое число «вероятно» простое или

0, если тестируемое число составное или равно 1.