Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Дисциплины:
2017-05-14 | 535 |
5.00
из
|
Заказать работу |
|
|
Простые числа и простейшие теоретико-числовые функции
Цель работы:
· Ознакомиться с генератором простых чисел на основе алгоритма «Решето Эратосфена» библиотеки “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|. Это соотношением используется для вычисления НОК в следующей функции
Простые числа и простейшие теоретико-числовые функции
Цель работы:
· Ознакомиться с генератором простых чисел на основе алгоритма «Решето Эратосфена» библиотеки “FLINT\C”.
· Изучить один из вероятностных тестов на простоту – тест Миллера-Рабина.
· Изучить теоретико-числовые функции, такие как НОД, НОК, вычисление мультипликативного обратного, извлечение квадратного корня из а по модулю M, извлечение квадратного корня из а по модулю p*q.
· Ознакомиться с представлением теоретико-числовых функций в библиотеки “FLINT\C”.
Задание
1. Программно реализовать алгоритм «Решето Эратосфена» (верхняя граница поиска берется согласно варианта в таблице 1).
2. Несколько чисел подвергнуть вероятностному тесту простоты Миллера-Рабина.
3. Для чисел, которые прошли тест Миллера-Рабина (являются простыми) программно реализовать некоторые из теоретико-числовых функций согласно варианта (таб.1).
4. Сделать выводы на основе результатов, полученных, после тестирования.
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!