Министерствообразования Республики Беларусь
Учреждение образования
«Брестскийгосударственный технический университет»
Кафедра ИИТ
Лабораторная работа №4/>
По дисциплине «Криптография»
По теме «Проверкабольших чисел на простоту»
Выполнила Студентка IIIкурса
Группы ИИ-5 Олехник Е.В.
Проверил Хацкевич М.В.
Брест 2010
Тема:Проверка больших чисел на простоту. Метод Ферма.
Цель:Изучить методы генерации и проверки на простоту больших чисел.
Ходработы:
Листингпрограммы:
Program.cs
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceTania_KMZILab3
{
classProgram
{
staticvoidMain()
{
BigIntegerbigInteger;
do
{
SelfDecimatedGeneratorgenerator = 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
usingSystem;
namespaceTania_KMZILab3
{
staticclassFerma
{
staticpublicboolFermatLittleTest(int confidence, BigInteger thisVal)
{
if((thisVal % 2) == 0)
returnfalse;
intbits = thisVal.bitCount();
BigIntegera = newBigInteger();
Randomrand = newRandom();
for(intround = 0; round
{
SelfDecimatedGeneratorgenerator = newSelfDecimatedGenerator(40); // в конструкторе задаёт длинучислав битах
a= newBigInteger(generator.Generate(), 2);
BigIntegerexpResult = a.modPow(thisVal — 1, thisVal);
if(expResult!= 1)
{
returnfalse;
}
}
returntrue;
}
}
}
SelfDecimatedGenerator.cs
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.Collections;
namespaceTania_KMZILab3
{
classSelfDecimatedGenerator
{
privateLFSRlfsr;
privateintk = 10;
privateintd = 23;
publicSelfDecimatedGenerator(int length
{
lfsr= newLFSR(length);
lfsr.UseRegister();
}
publicstringGenerate()
{
if(lfsr.Quantity())
{
for(int i = 0; i
lfsr.UseRegister();
}
else
{
for(int i = 0; i
lfsr.UseRegister();
}
stringbitString = "";
for(int i = 0; i
{
if(lfsr.GetBits()[i] == true)
bitString+= «1»;
else
bitString+= «0»;
}
returnbitString;
}
}
}
LFSR.cs
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.Collections;
namespaceTania_KMZILab3
{
classLFSR
{
privateBitArrayArray;
privatebooloutBit;
publicBitArrayGetBits()
{
returnArray;
}
publicLFSR(int lenght)
{
Array= newBitArray(lenght);
Randomrnd = newRandom();
for(int i = 0; i
{
if((rnd.Next(0, 1000) % 2) == 0)
{
Array[i]= true;
}
else
{
Array[i]= false;
}
}
}
publicvoidUseRegister()
{
boolfeedBack;
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.Set(Array.Length- i — 1, Array.Get(Array.Length — i — 2));
}
Array.Set(0,feedBack);
}
publicboolQuantity()
{
if(outBit == false)
{
returnfalse;
}
elsereturntrue;
}
}
}
Работапрограммы:
76852633312072762368612999781
True
62106168008639652108721361597
True
34503197996314167362452631497
True
Вывод:Изучилиметоды генераций больших простых чисел, а так же способы их проверки напростоту.