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

Цель работы:

· Ознакомиться с генератором простых чисел на основе алгоритма «Решето Эратосфена» библиотеки “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.

Пример реализации «Решета Эратосфена» и теста Миллера-Рабина

#include <FLINT.h>

#include <stdio.h>

#include <conio.h>

#include <math.h>

#define ClintToStr xclint2str_l // Переопределение функции xclint2str_l

int main(int argc, char* argv[ ])

{

CLINT a; // Обьявление объекта CLINT

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

char *sa =new char;sa="445";

str2clint_l (a,sa,10);//Инициализация строкой

printf("a= %s",ClintToStr(a,10,0));

ULONG N=1445;

int Test= prime_l ( a, N, 1000); // тест

if(Test==1)printf(" -> Yes ");

else printf(" -> No ") ;

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

ULONG M=3445;

ULONG * k= genprimes ( M);// Генератор

int m= k[0];

printf("\n Search = %d\n",m);

for(int i=1;i<=m;i++) printf(" %d ",*(k+i));

getch(); return 0

Теоретико-числовые функции

Наибольший общий делитель

Наибольшим общим делителем (НОД) целых чисел а и b называется положительный делитель чисел а и b, делящийся на любой другой общий делитель этих чисел. Числа а и b называются взаимно-простыми, если НОД(a,b)=1. Классический алгоритм Евклида для вычисления наибольшего общего делителя, «дедушка» всех алгоритмов [Knut], использует повторное деление с остатком: вычисляется вычет a mod b, затем b mod (a mod b) и так далее, пока остаток не будет равен нулю. Например: НОД(21,12) =Н0Д(21 (mod 12), 12) = НОД (9,12) = НОД(12 (mod 9), 9) = НОД (3,9) = НОД (9 (mod3),3) = НОД (0,3) = 3.

Модифицированный, т.н. бинарный алгоритм Евклида вычисления НОД(а,b) для a, b >0 реализован в виде следующей функции

Наибольший общий делитель (НОД)

Синтаксис: void gcd_l (CLINT a, CLINT b, CLINT c);

Вход: a, b (операнды)

Выход: c (наибольший общий делитель)

Таким образом, получаем представление наибольшего общего делителя g=НОД(a, b)=u×a+v×b ввиде линейной комбинации чисел а и b с целыми коэффициентами и и v, причем u по модулю ag и v по модулю bg определены однозначно. Если же для элемента выполняется условие НОД(а, n)= 1 = и× а + v×п, то отсюда сразу же следует и× a mod п или, что то же самое. В этом случае вычет и mod n определен однозначно.

Расширенный алгоритм Евклида вычисления линейного представления НОД(а, b) = u • а + v • b для натуральных чисел a, b

Синтаксис void xgcd_l (CLINT a, CLINT b, CLINT g,CLINT u, int *sign_u, CLINT v, int *sign_v);

Вход: a , b (операнды)

Выход: g (наибольший общий делитель чисел а и b)

u, v (коэффициенты при а и b )

sign_u (знак коэффициента u)

sign_v (знак коэффициента v)

Наименьшее общее кратное

Наименьшее общее кратное (НОК) двух целых чисел a и b есть наименьшее целое число, которое делится на m и n. Обычно обозначается [a,b], а иногда НОК(a,b).

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

НОК(a,b) НОД(a,b) =|ab|. Это соотношением используется для вычисления НОК в следующей функции