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

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 итераций