Проверка больших чисел на простоту
Министерство образования Республики Беларусь
Учреждение образования
Лабораторная работа №4
По дисциплине «Криптография»
По теме «Проверка больших чисел на простоту»
Группы ИИ-5 Олехник Е. В.
Проверил Хацкевич М. В.
Брест 2010
Тема: Проверка больших чисел на простоту. Метод Ферма.
Цель: Изучить методы генерации и проверки на простоту больших чисел.
Ход работы:
Листинг программы:
Program
.
cs
using System;
using System. Collections. Generic;
using System. Linq;
using System. Text;
{
classProgram
{
staticvoid Main()
{
BigInteger bigInteger;
do
{
SelfDecimatedGenerator generator = newSelfDecimatedGenerator(98); // в конструкторе задаёт длину числав битах
bigInteger = newBigInteger(generator. Generate(), 2); // создаём боооольшое число передаём как первый параметр сроку второй 2-это значит двоичная система
}
while (!Ferma. FermatLittleTest(50, bigInteger));
}
}
}
Ferma. cs
using System;
namespace TaniaKMZILab3
{
staticclassFerma
{
{
if ((thisVal % 2) == 0)
int bits = thisVal. bitCount();
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;
}
}
}
}
}
SelfDecimatedGenerator. cs
using System;
using System. Linq;
using System. Collections;
namespace TaniaKMZILab3
{
classSelfDecimatedGenerator
{
privateLFSR lfsr;
privateint k = 10;
privateint d = 23;
public SelfDecimatedGenerator(int length
{
lfsr = newLFSR(length);
}
{
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)
"1";
else
bitString += "0";
}
return bitString;
}
}
}
LFSR. cs
using System;
using System. Collections. Generic;
using System. Linq;
namespace TaniaKMZILab3
{
classLFSR
{
{
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()
{
{
returnfalse;
}
}
}
}
Работа программы:
True
True
34503197996314167362452631497
True
Вывод:
Изучили методы генераций больших простых чисел, а так же способы их проверки на простоту.
| 
