Проверка больших чисел на простоту
Министерство образования Республики Беларусь
Учреждение образования
«Брестский государственный технический университет»
Кафедра ИИТ
Лабораторная работа №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
Вывод: Изучили методы генераций больших простых чисел, а так же способы их проверки на простоту.