Казанский (Приволжский) Федеральный Университет Институт Вычислительной Математики и Информационных Технологий

Казанский (Приволжский) Федеральный Университет

Институт Вычислительной Математики и Информационных Технологий

Кафедра системного анализа и информационных технологий



Отчет

по дисциплине: «Математические основы защиты информации»



Выполнил:

Принял: к.н.



Казань 2017


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

Разработка алгоритма поиска

числа свидетелей для полупростого числа n


Задание:

  1. Разработать программу для поиска числа свидетелей в тесте простоты Миллера-Рабина по алгоритму, предложенному в [1], часть 3, стр.3-4.
  2. Выполнить расчет среднего отношения числа свидетелей к числу n=pq для полупростых чисел меньших 100. Сравнить это отношение с отношением 0,25, полученным в теореме Рабина.
  3. Выполнить тоже для полупростых чисел до 10^6 и оценить время работы алгоритма для этого интервала.
  4. Выполнить, если это возможно те же вычисления для больших интервалов, например, до 10^10 и оценить увеличение времени работы. Чем больший интервал будет охвачен, тем выше итоговая оценка.

Код программы

#define _CRT_SECURE_NO_WARRNINGS

#include<iostream>

#include <math.h>

#include <sstream>

#include <ctime>

#define PATH_MAX 1024

#pragma warning(disable : 4996)

using namespace std;


int Ar[564580];// Массив простых чисел < 9999991=10^7, Ar[0]=1;


long int NOD(long long int a, long long int b) {//Вычисление НОД

 

a = abs(a);

b = abs(b);

while (a != b) {

if (a > b) swap(a, b);

b = b - a;

}

return a;

}

int Bin(int n) {// подсчитывет bin(n)


 int t = 0;

 while (n % 2 == 0) {

 n = n / 2;

 t = t + 1;

 }

 return t;

}

long int FA(long long int n) {//Функция Эйлера

 

long long int t = 0;

long long int k = 2;

long long int j = 0;

while (k*k <= n && j != 1) {

if (n%k == 0) {

j = 1;

k = k + 1;

}

else {

k = k + 1;

}

}

if (j == 1) {

for (long long int i = 1; i <= n; i++) {


if (NOD(i, n) == 1) {

t = t + 1;

}

else {

t = t;

}


}

}

else {

t = n - 1;

}

return t;

}

bool Pr(long long int a) {// определяет, простое число или нет


unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;

if (a == 0 || a == 1)

return 0;

if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)

return 1;

if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0 || a % 7 == 0 || a % 11 == 0 || a % 13 == 0 || a % 17 == 0 || a % 19 == 0 || a % 23 == 0 || a % 29 == 0)

return 0;

bound = sqrt((double)a);

i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;

while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)

{

i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;

}

if (i8 <= bound ||

i1 <= bound && a % i1 == 0 ||

i2 <= bound && a % i2 == 0 ||

i3 <= bound && a % i3 == 0 ||

i4 <= bound && a % i4 == 0 ||

i5 <= bound && a % i5 == 0 ||

i6 <= bound && a % i6 == 0 ||

i7 <= bound && a % i7 == 0)

return 0;

return 1;


}


int main(){

 long int x1, x2;//Вводим границы интервала

 cout << "Vvedite levuy granicu:";

 cin >> x1;

 cout << "Vvedite pravuy granicu:";

 cin >> x2;

 unsigned int start_time = clock();



 FILE* Myf = fopen("G:\\Primes.txt", "r");//Заполняем массив простых чисел из файла

 char t[20] = ""; long i, k = 1; Ar[0] = 1;

 fgets(t, 20, Myf);

 while (!feof(Myf)){

 

 if (t[0] != '\n'){

 i = 0; while (t[i] != '\n')i++;

 t[i] = '\0';  Ar[k] = atoi(t);

 if (Ar[k] >= x2){

 break;

 }

 else{

 k++;

 }

 fgets(t, 20, Myf);

 

 }

 

 }

 fclose(Myf);


 


 long long int p, q;

 long int del[_MAX_PATH];

 long int bin[_MAX_PATH];

 long int s[_MAX_PATH];

 int max = 0;

 long long int l = 0;

 long long int a = 0;


 for (long int n = x1; n <= x2; n++){

 for (int i = 1; i <= k; i++){

 if (Ar[i] == 0){


 }

 else{

 if (n%Ar[i] == 0){//Находим простые делители числа n

 p = Ar[i];

 q = n / p;

 if (p < q && Pr(q) == 1){

 long int t = NOD(p - 1, q - 1);//Определяем НОД


 int j = 0;

 for (int d = 1; d <= t; d++){//Находим общие делители

 if (t%d == 0){

 del[j] = d;

 j++;

 }

 }


 for (int j1 = 0; j1 <= j - 1; j1++){//Вычисляем степени двойки

 bin[j1] = Bin(del[j1]);

 }


 for (int i1 = 0; i1 < j - 1; i1++){//Находим максимум из Bin

 if (bin[i1]>max){

 max = bin[i1];

 }

 }


 for (int k1 = 0; k1 <= max; k1++){

 s[k1] = 0;

 }


 for (int m = 0; m <= max; m++){//Вычисляем кол-во свидетелей простоты

 for (int m1 = 0; m1 <= j - 1; m1++){

 if (bin[m1] == m){

 s[m] = s[m] + FA(del[m1]);

 }

 }

 a += (s[m])*(s[m]);

 }

 l = l + n;//Суммируем числа, которые раскладываются в произведение двух простых чисел

 }

 break;

 }

 }

 

 }

 }


 float w = 1.0*a / l;//Вычисление отношения

 unsigned int end_time = clock();

 //Вывод результатов

 cout << "n:" << l << "\n";

 cout << "a:" << a << "\n";

 cout << "Result:" << w<<"\n";

 cout << "Time:" << (end_time-start_time)/1000.0 << "\n";

 cout << "k:" << k << "\n";


 system("pause");

}


Пример выполнения программы

Анализ полученных результатов

0-100

0,01239

100-1000

0,00649

1000-10000

0,00208

10000-100000

0,000654

100000-1000000

0,000174

1000000-10000000

4.70458e-005




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

Разработка алгоритма поиска числа свидетелей для произвольного числа различных простых сомножителей


Задание:

  1. Разработать программу для поиска числа свидетелей n являющегося произведением произвольного числа различных простых сомножителей, по алгоритму, предложенному в [1], часть 3, стр.5-6.
  2. Выполнить расчет среднего отношения числа свидетелей для чисел вида n=pqr, меньших 100. Сравнить это отношение с отношением 0,25, полученным в теореме Рабина.
  3. Выполнить тоже для чисел n=pqr до 1000000 и оценить время работы алгоритма для этого интервала.
  4. Выполнить, если это возможно те же вычисления для больших интервалов, например, до 10^10 и оценить увеличение времени работы. Чем больший интервал будет охвачен, тем выше итоговая оценка.

Код программы

#define _CRT_SECURE_NO_WARRNINGS

#include<iostream>

#include <math.h>

#include <sstream>

#include <ctime>

#define PATH_MAX 1024

#pragma warning(disable : 4996)


int Ar[564580];


long Nod(long long int a, long long int b)//Находит НОД

{

 while (a && b)

 if (a >= b)

 a %= b;

 else

 b %= a;

 return a | b;


}



int Bin(int n) {// подсчитывет bin(n)

 int t = 0;

 while (n % 2 == 0) {

 n = n / 2;

 t = t + 1;

 }

 return t;

}

long long int FA(long long int n) {//функция Эйлера

 

 long long int t = 0;

 long long int k = 2;

 long long int j = 0;

 while (k*k <= n && j != 1) {

 if (n%k == 0) {

 j = 1;

 k = k + 1;

 }

 else {

 k = k + 1;

 }

 }

 if (j == 1) {

 for (long long int i = 1; i <= n; i++) {


 if (Nod(i, n) == 1) {

 t = t + 1;

 }

 else {

 t = t;

 }


 }

 }

 else {

 t = n - 1;

 }

 return t;


}

int main(){

 long int x1, x2;//Границы интервала

 std::cout << "Vvedite levuy granicu:";

 std::cin >> x1;

 std::cout << "Vvedite pravuy granicu:";

 std::cin >> x2;


 unsigned int start_time = clock();

 long long int del[PATH_MAX];

 long long int bin[PATH_MAX];

 long long int s[PATH_MAX];

 long float w1[PATH_MAX];

 long long int n1;

 long long int a = 0;

 long long int u = 0;

 long long int max = 0;

 long long int p[PATH_MAX];

 long long int t[PATH_MAX];

 long long int j1 = 1;



 FILE* Myf = fopen("G:\\Primes.txt", "r");//Массив заполняется простыми числами из файла

 char t1[20] = ""; long i, k = 1; Ar[0] = 1;

 fgets(t1, 20, Myf);

 while (!feof(Myf)){


 if (t1[0] != '\n'){

 i = 0; while (t1[i] != '\n')i++;

 t1[i] = '\0';  Ar[k] = atoi(t1);

 if (Ar[k] >= x2){

 break;

 }

 else{

 k++;

 }

 fgets(t1, 20, Myf);


 }


 }

 fclose(Myf);



 for (long long int n = x1; n <= x2; n++) {

 j1 = 1;

 n1 = n;

 for (long long int i = 1; i <= k; i++) {

 if (n1%Ar[i] == 0) {//Находим простые делители числа n

 p[j1] = Ar[i];

 n1 = n1 / Ar[i];

 j1 = j1 + 1;

 if (n1 == 1) {

 if (j1-1 >= 2){  

 //if (j1-1>2 && j1-1<4){//Можно указать на сколько множителей должно раскладываться число n

 long long int t=p[1]-1;

 

 for (int i3 = 1; i3 <= j1 - 1; i3++) {//Находим НОД

 t = Nod(t < (p[i3]-1) ? t : (p[i3]-1), t < (p[i3]-1) ? (p[i3]-1) : t);

 }


 long long int l = 0;

 for (long long int d = 1; d <= t; d++) {//Делители НОД

 if (t%d == 0) {

 del[l] = d;

 l += 1;

 }

 }


 for (long long int l1 = 0; l1 <= l - 1; l1++) {//Опредеояем максимум из bin

 bin[l1] = Bin(del[l1]);

 if (bin[l1] > max) {

 max = bin[l1];

 }

 }


 for (long long int k1 = 0; k1 <= max; k1++) {

 s[k1] = 0;

 }


 for (long long int m = 0; m <= max; m++) {//Подсчитываем число свидетелей простоты

 for (long long int m1 = 0; m1 <= l - 1; m1++) {

 if (bin[m1] == m) {

 s[m] = s[m] + FA(del[m1]);

 }

 }

 a += (s[m])*(s[m]);

 }

 u = u + n;//Суммируем подходящие n

 }

 break;

 }

 }

 }

 

 }



 long double w = 1.0*a / u;//Вычисление отношения

 unsigned int end_time = clock();

 //вывод результатов

 std::cout << u << "\n";

 std::cout << a << "\n";

 std::cout << w << "\n";

 std::cout << "Time:" << (end_time - start_time) / 1000.0 << "\n";

 system("pause");


Пример выполнения программы

Анализ полученных результатов

0-100

0,01748

100-1000

0,0022417

1000-10000

0,00028729

10000-100000

3,90124e-005

100000-1000000

3,88683e-005



Анализ результатов

0-100

0,01239

0,01748

100-1000

0,00649

0,0022417

1000-10000

0,00208

0,00028729

10000-100000

0,000654

3,90124e-005

100000-1000000

0,000174

3,88683e-005


Подпишитесь на рассылку:


Вычисление
это получение из входных данных нового знания

Информационные технологии


Смотрите полные списки: Профессии

Профессии: Техника и производство



Проекты по теме:

Приволжск
А
Б
В
Е
Ж
З
И
К
Л
Н
О
П
П
ПамяткиПатриотизмПедагогикаПедиатрияПенсионное обеспечениеПенсионный фондПервенствоПланированиеПлановые проверкиПланы мероприятийПланы развитияПланы социального развитияПланыПовестки дняПовышение ценПодготовка к вступительным экзаменамПодготовкаПодразделенияПодрядное строительствоПожарная охранаПолицияПолное образованиеПоложенияПорядок ипотеки и общего кредитованияПоселенияПоставка оборудованияПоставкиПостановленияПотребительский рынокПояснительные запискиПравила пользованияПравовые актыПравовые нормыПравонарушенияПрактика менеджментаПрактикаПредложенияПредписанияПредпринимательская деятельностьПредпринимательствоПредприятияПрезентацииПресс-релизыПриватизация муниципального имуществаПриватизацияПриговорыПрием в университетыПриказы министерства образованияПриказы о проведении конкурсовПриказы об утверждении положенийПриказы образовательным учреждениямПриказыПриложения к решениям и договорамПриложенияПриоритетыПриродопользованиеПрогнозыПрограммы конкурсовПрограммы мероприятийПрограммы повышения квалификацииПрограммы развитияПрограммы семинаровПрограммыПрогрессПродажаПроектированиеПроектные декларацииПроекты постановленийПроекты правилПроекты самоуправленияПроектыПроизводствоПрокуратураПромышленность строительных материаловПротоколы аукционов на капитальный ремонтПротоколы внеочередных собранийПротоколы вскрытия конвертовПротоколы заседаний партнерствПротоколы заседаний советовПротоколы заседанийПротоколы котировочных заявокПротоколы некоммерческих партнерствПротоколы общих собранийПротоколы оценок котировочных заявокПротоколы проведения котировок ценПротоколы проведения олимпиадПротоколы проведения торговПротоколы рассмотрения заявокПротоколы строительных организацийПротоколыПрофессиональная деятельностьПрофессиональное образованиеПрофсоюзыПроцессыПубликацииПубличные слушания
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
Математика
Основные порталы (построено редакторами)

Домашний очаг

ДомДачаСадоводствоДетиАктивность ребенкаИгрыКрасотаЖенщины(Беременность)СемьяХобби
Здоровье: • АнатомияБолезниВредные привычкиДиагностикаНародная медицинаПервая помощьПитаниеФармацевтика
История: СССРИстория РоссииРоссийская Империя
Окружающий мир: Животный мирДомашние животныеНасекомыеРастенияПриродаКатаклизмыКосмосКлиматСтихийные бедствия

Справочная информация

ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организации
МуниципалитетыРайоныОбразованияПрограммы
Отчеты: • по упоминаниямДокументная базаЦенные бумаги
Положения: • Финансовые документы
Постановления: • Рубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датам
Регламенты
Термины: • Научная терминологияФинансоваяЭкономическая
Время: • Даты2015 год2016 год
Документы в финансовой сферев инвестиционнойФинансовые документы - программы

Техника

АвиацияАвтоВычислительная техникаОборудование(Электрооборудование)РадиоТехнологии(Аудио-видео)(Компьютеры)

Общество

БезопасностьГражданские права и свободыИскусство(Музыка)Культура(Этика)Мировые именаПолитика(Геополитика)(Идеологические конфликты)ВластьЗаговоры и переворотыГражданская позицияМиграцияРелигии и верования(Конфессии)ХристианствоМифологияРазвлеченияМасс МедиаСпорт (Боевые искусства)ТранспортТуризм
Войны и конфликты: АрмияВоенная техникаЗвания и награды

Образование и наука

Наука: Контрольные работыНаучно-технический прогрессПедагогикаРабочие программыФакультетыМетодические рекомендацииШколаПрофессиональное образованиеМотивация учащихся
Предметы: БиологияГеографияГеологияИсторияЛитератураЛитературные жанрыЛитературные героиМатематикаМедицинаМузыкаПравоЖилищное правоЗемельное правоУголовное правоКодексыПсихология (Логика) • Русский языкСоциологияФизикаФилологияФилософияХимияЮриспруденция

Мир

Регионы: АзияАмерикаАфрикаЕвропаПрибалтикаЕвропейская политикаОкеанияГорода мира
Россия: • МоскваКавказ
Регионы РоссииПрограммы регионовЭкономика

Бизнес и финансы

Бизнес: • БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумаги: • УправлениеОткрытые акционерные обществаПроектыДокументыЦенные бумаги - контрольЦенные бумаги - оценкиОблигацииДолгиВалютаНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыСтрахованиеБюджетФинансовые услугиКредитыКомпанииГосударственные предприятияЭкономикаМакроэкономикаМикроэкономикаНалогиАудит
Промышленность: • МеталлургияНефтьСельское хозяйствоЭнергетика
СтроительствоАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьерОрганизация и управление производством

Каталог авторов (частные аккаунты)

Авто

АвтосервисАвтозапчастиТовары для автоАвтотехцентрыАвтоаксессуарыавтозапчасти для иномарокКузовной ремонтАвторемонт и техобслуживаниеРемонт ходовой части автомобиляАвтохимиямаслатехцентрыРемонт бензиновых двигателейремонт автоэлектрикиремонт АКППШиномонтаж

Бизнес

Автоматизация бизнес-процессовИнтернет-магазиныСтроительствоТелефонная связьОптовые компании

Досуг

ДосугРазвлеченияТворчествоОбщественное питаниеРестораныБарыКафеКофейниНочные клубыЛитература

Технологии

Автоматизация производственных процессовИнтернетИнтернет-провайдерыСвязьИнформационные технологииIT-компанииWEB-студииПродвижение web-сайтовПродажа программного обеспеченияКоммутационное оборудованиеIP-телефония

Инфраструктура

ГородВластьАдминистрации районовСудыКоммунальные услугиПодростковые клубыОбщественные организацииГородские информационные сайты

Наука

ПедагогикаОбразованиеШколыОбучениеУчителя

Товары

Торговые компанииТоргово-сервисные компанииМобильные телефоныАксессуары к мобильным телефонамНавигационное оборудование

Услуги

Бытовые услугиТелекоммуникационные компанииДоставка готовых блюдОрганизация и проведение праздниковРемонт мобильных устройствАтелье швейныеХимчистки одеждыСервисные центрыФотоуслугиПраздничные агентства