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

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

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

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

Кафедра ИИТ

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

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