Рефетека.ру / Математика

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

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

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

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

Кафедра ИИТ


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


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

Похожие работы:

  1. • Применение алгоритма RSA для шифрования потоков данных
  2. • Разработка методического пособия на тему "Генерация ...
  3. • Аудиторская проверка кредитных операций
  4. • Виды услуг, сопутствующих аудиту
  5. • Проверка формирования финансовых результатов и использования ...
  6. • Аудиторская проверка учета кредитов и займов
  7. • Бухгалтерский учет и аудит кредитов и займов
  8. • Тест числа на простоту
  9. • Синтаксический распознаватель арифметического оператора ...
  10. • Перспективы развития и использования асимметричных ...
  11. • Криптографические системы
  12. • Развитие математических представлений у дошкольников
  13. • Представление логических функций от большого числа ...
  14. • Об объективных факторах простоты и сложности языка (к ...
  15. • Формирование жанровой разновидности сатирической комедии На ...
  16. • Исследование посещаемости WEB сайта
  17. • Классификация средств вычислительной техники
  18. • Метод Фолля
  19. • Побудова простих великих чисел
Рефетека ру refoteka@gmail.com