Реализация упрощённого варианта генерации «сильных» простых чисел с использованием вероятностного теста рабина-миллера(для искусственн

Автор: Пользователь скрыл имя, 25 Апреля 2012 в 01:26, курсовая работа

Краткое описание

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

Оглавление

ВВЕДЕНИЕ…………………………………………………………………………..6
1 ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ………………………………..7
1.1 Общие сведения о простых числах…………………………………………..7
1.2 Способы генерации простых чисел………………………………………...12
1.3 Методы проверки чисел на простоту………………………………………13
1.3.1 Метод пробных делений………………………………………………13
1.3.2 Проверка способом «решето Эратосфена»…………………………..14
1.3.3 Метод на основе теоремы Вильсона………………………………….15
1.3.4 Проверка с помощью вероятностных тестов……………………...…15 1.4 Алгоритм теста Рабина-Миллера и практические соображения программной реализации…………………………………………………………………………..17
2 ОПИСАНИЕ ПРОГРАММЫ…………………………………………………….19
2.1Общие сведения……………………………………………………………...19
2.2Функциональное назначение программы………………………………….19
2.3 Описание логической структуры…………………………………………..20
2.3.1 Блок-схема алгоритма…………………………………………………20
2.3.2 Структура программы с описанием функций………………………..21
2.4 Используемые технические средства ……………………………………..21
2.5 Входные и выходные данные………………………………………………21
ВЫВОДЫ…………………………………………………………………………...23
ПЕРЕЧЕНЬ ССЫЛОК……………………………………………………………...24
ПРИЛОЖЕНИЕ А Код программы……………………………………………….25
ПРИЛОЖЕНИЕ Б Результаты работы программы………………………………31

Файлы: 1 файл

мой курсач 2.docx

— 189.77 Кб (Скачать)

2.3.2 Структура программы с описанием функций

 

В программе используется функция библиотеки C++ stdlib rand(), которая возвращает псевдослучайное 32-х битное число. Кроме того, используются 3 пользовательские функции

bool RabinMiller_Test (unsigned int p,int KolIter)

bool StrongDigit_Test (unsigned int p,int KolIter)

Power(X,Pow,Y,Mod).

Функция Power вычисляет Y как X в степени Pow по модулю Mod.

Функция RabinMiller_Test реализует  тест Рабина-Миллера для случайного числа p при заданном количестве иттераций (число повторений теста) KolIter. При этом она вызывает функцию Power.

Функция StrongDigit_Test реализует проверку на то, что число p является «сильным» простым числом в широком смысле [2, C. 31], при этом эта функция в свою очередь вызывает функцию RabinMiller_Test. С подробным описанием функций можно ознакомится в приложении А.

 

2.4 Используемые технические средства

 

Для реализации поставленной задачи был использован компьютер  следующей конфигурации:

- Процессор Intel® Core™ 2 Duo CPU E6550 2.33 GHz;

- ОЗУ: 2,00 Гб;

- HDD: 500 Гб;

- Операционная система: MS Windows XP Professional Service Pack 3 версия 2002 ;

 

2.5 Входные и выходные данные

 

- Количество итераций (число повторений) теста Рабина-Миллера

- Два «сильных» простых  числа P и Q 

- число N, которое является произведением чисел P и Q

- вероятность ошибки теста  Рабина-Миллера при заданном количестве  итераций 

Например при запуске  программы вводим число 10, которое  является количеством итераций, т.е. сколько раз наши сгенерированные  случайные числа P и Q будут проходить тест, и нажимаем клавишу Enter. После этого программа выводит нам на экран сообщение, о том что P и Q  «сильные» простые числа и их численные значения, а также число N, которое является произведением чисел P и Q и вероятность ошибки теста соответственно с формулой (1.7).

Для более детального ознакомления с программой следует обратиться к приложению Б.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВЫВОДЫ

 

 

При разработке данной программы  были исследованы методы проверки случайных  чисел на простоту с помощью различных  тестов, в частности вероятностных. В результате была получена программа, которая позволяет тестировать  два псевдослучайных числа на простоту с помощью вероятностного теста Рабина-Миллера, и при положительном результате проверяет, являются ли это числа сильными простыми числами и выдаёт вероятность ошибки теста, зависящее от числа итераций.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПЕРЕЧЕНЬ ССЫЛОК

 

  1.  Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Триумф, 2002. — С. 296—300. — 816 с.
  2. Горбенко І.Д., Гріненко Т.О. Захист інформації в інформаційно-телекомунікаційних системах: Навчальний посібник. Частина 1: Криптографічний захист інформації ) – Харків. ХНУРЕ, 2004. – 376 с.
  3. ДСТУ 3008-95 "ЗВІТИ У СФЕРІ НАУКИ І ТЕХНІКИ. Структура та правила оформлення".
  4. . ГОСТ 19.701 - 90. ЕСПД. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.
  5. http://www.wikipedia.org/
  6. http://progrm.ru/

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ A

 

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

 

#include <vcl.h>

#pragma hdrstop

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

#include <stdio.h>

#pragma argsused

using namespace std;

 

// функция вычисляет Y = (X в степени Pow) по модулю Mod

void Power (unsigned int X, unsigned int Pow, unsigned int &Y, unsigned int Mod)

//unsigned int Pow – степень числа Х;

//unsigned int Mod – значение модуля

{

  int i;

unsigned __int64 time;

if (Pow==0)

{

  Y=1;

  return;

}

else if (Pow==1)

{

  Y=X%Mod;

  return;

}

else

  Y=X%Mod;

for (i=31; !(Pow&(1<<i)) && i>=0; i--);

i--;

for ( ;i>=0; i--)

{

  time=Y;

  time*=time;

  Y=time%Mod;

  if (Pow&(1<<i))

  {

   time=Y;

   time*=X;

   Y=time%Mod;

  }

}

}

 

 

bool RabinMiller_Test (unsigned int p,int KolIter)

//unsigned int p- случайное число, которое проходит тест;

//int KolIter – кол-во итераций теста

{

unsigned int z,a,b=0, m(p-1);

// a – случайное число, меньше р;

//b – степень двойки

 bool Flag;

// вычисление b - степени  двойки

 do

{

  m/=2;

  b+=1;

} while (!(m&1));

for (int i=0; i<=KolIter; i++)

 {

  do

  {

   // a - случайное число  , меньше p

   a = ((rand()<<16) | rand());

   a= a % (p-1);

  } while (!a);

  Power(a, m, z, p);

  // если rez=1 или rez=p-1, то p - проходит тест и может быть простым числом

  // и переходим на  следующую иттерацию

  if ((z == 1) || (z == p-1))

   continue;

  Flag=1;

  for (int j=1; j<b; j++)

  {

   Power(z, 2, z, p);

   if(z==1)

    // тест не пройден (z=1 при j>0)

    return 0;

   if(z==(p-1))

   {

    // тест пройден (z=p-1)

    Flag=0;

    // выход из цикла for (int j=0; j<b; j++)

    break;

   }

  }

  if (Flag)

   return 0;

}

// тест пройден при  всех иттерациях

 return 1;

}

 

bool StrongDigit_Test (unsigned int p,int KolIter)

{

bool ret;

unsigned int r;

 // сильное простое число в широком смысле (P = 2R+1)

r = (p-1)/2;

// если r - простое число,  то p - сильное простое число в  широком смысле

 ret =  RabinMiller_Test(r,KolIter);

return ret;

}

 

void main ()

{

unsigned int P,Q,KolVo;

unsigned __int64 N;

double V;

cout << "Vvedite Kol-Vo itteraciy testa Rabina-Millera: ";

cin >> KolVo;

 

srand(time(NULL));

 

do

{

  do {

  // сгенерировать случайное  число (кандидата на простое  число),

  // установить младший  бит в 1 для получения нечетного  числа

  // и установить старший  бит в 1 для получения требуемой  длины

  Q=rand()|1|0x80000000;

  }

  // цикл, пока число  не пройдет проверку на тест  Рабина-Миллера

  while (!RabinMiller_Test(Q,KolVo));

 }

// цикл, пока число не  пройдет проверку на сильное  простое число

while (!StrongDigit_Test(Q,KolVo));

 

// те же действия для  числа P

do

{

  do {

  P=rand()|1|0x80000000;

  }

  while (!RabinMiller_Test(P,KolVo));

}

while (!StrongDigit_Test(P,KolVo));

 

N=(unsigned __int64)P*(unsigned __int64)Q;

V=1;

for (int i=1; i<=KolVo; i++)

V = V * 1/4;

cout<<endl<<"  P i Q - silnie prostie chisla  P= " << P <<" Q= " << Q;

cout << endl<<" s veroyatnosnyu oshibki : " << V;

cout<<endl<<"  N = P * Q -  " << N;

 

cin.get();

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ Б

Результаты работы программы

 

 

Рисунок Б.1 – Результаты для 5-ти итераций

 

 

Рисунок Б.2 – Результаты для 10-ти итераций

 

 

Рисунок Б.3 – Результаты для 100 итераций


Информация о работе Реализация упрощённого варианта генерации «сильных» простых чисел с использованием вероятностного теста рабина-миллера(для искусственн