Проверка больших чисел на простоту

Проверка больших чисел на простоту

Министерство образования Республики Беларусь

Учреждение образования

«Брестский государственный технический университет»

Кафедра ИИТ

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

По дисциплине «Криптография»

По теме «Проверка больших чисел на простоту»

Выполнила Студентка III курса

Группы ИИ-5 Олехник Е.В.

Проверил Хацкевич М.В.

Брест 2010

Тема: Проверка больших чисел на простоту. Метод Ферма.

Цель: Изучить методы генерации и проверки на простоту больших чисел.

Ход работы:

Листинг программы:

Program.cs

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Tania_KMZILab3

{

classProgram

 {

staticvoid Main()

 {

BigInteger bigInteger;

do

 {

SelfDecimatedGenerator generator = newSelfDecimatedGenerator(98); // в конструкторе задаёт длину числав битах

 bigInteger = newBigInteger(generator.Generate(), 2); // создаём боооольшое число передаём как первый параметр сроку второй 2-это значит двоичная система

 }

while (!Ferma.FermatLittleTest(50, bigInteger));

Console.WriteLine(bigInteger); // вывод на консоль числа

Console.WriteLine(Ferma.FermatLittleTest(50, bigInteger));

Console.ReadKey(); // ожидание нажатия клавиши с консоли

 }

 }

}

Ferma.cs

using System;

namespace Tania_KMZILab3

{

staticclassFerma

 {

staticpublicbool FermatLittleTest(int confidence, BigInteger thisVal)

 {

if ((thisVal % 2) == 0)

returnfalse;

         int bits = thisVal.bitCount();

         BigInteger a = newBigInteger();

         Random rand = newRandom();

         for(int round = 0; round < confidence; round++)

          {

                            SelfDecimatedGenerator generator = newSelfDecimatedGenerator(40); // в конструкторе задаёт длину числав битах

 a = newBigInteger(generator.Generate(), 2);

BigInteger expResult = a.modPow(thisVal - 1, thisVal);

                   if(expResult != 1)

                    {

                            returnfalse;

 }

          }

         returntrue;

 }

 }

}

SelfDecimatedGenerator.cs

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;

namespace Tania_KMZILab3

{

classSelfDecimatedGenerator

 {

privateLFSR lfsr;

privateint k = 10;

privateint d = 23;

public SelfDecimatedGenerator(int length

 {

 lfsr = newLFSR(length);

 lfsr.UseRegister();

 }

publicstring Generate()

 {

if (lfsr.Quantity())

 {

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

 lfsr.UseRegister();

 }

else

 {

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

 lfsr.UseRegister();

 }

string bitString = "";

for (int i = 0; i < lfsr.GetBits().Length; i++)

 {

if (lfsr.GetBits()[i] == true)

 bitString += "1";

else

 bitString += "0";

 }

return bitString;

 }

 }

}

LFSR.cs

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;

namespace Tania_KMZILab3

{

classLFSR

 {

privateBitArray Array;

privatebool outBit;

publicBitArray GetBits()

 {

return Array;

 }

public LFSR(int lenght)

 {

 Array = newBitArray(lenght);

Random rnd = newRandom();

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

 {

if ((rnd.Next(0, 1000) % 2) == 0)

 {

 Array[i] = true;

 }

else

 {

 Array[i] = false;

 }

 }

 }

publicvoid UseRegister()

 {

bool feedBack;

 feedBack = Array.Get(15) ^ Array.Get(10) ^ Array.Get(15) ^ Array.Get(12);

 outBit = Array.Get(Array.Length - 1);

for (int i = 0; i < (Array.Length - 1); i++)

 {

 Array.Set(Array.Length - i - 1, Array.Get(Array.Length - i - 2));

 }

 Array.Set(0, feedBack);

 }

publicbool Quantity()

 {

if (outBit == false)

 {

returnfalse;

 }

elsereturntrue;

 }

 }

}

Работа программы:

76852633312072762368612999781

True

62106168008639652108721361597

True

34503197996314167362452631497

True

Вывод: Изучили методы генераций больших простых чисел, а так же способы их проверки на простоту.