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