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

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

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

Кафедра ИИТ

Лабораторная работа №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;

}

}

}

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

True

True

True

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