Название: Проверка больших чисел на простоту
Вид работы: лабораторная работа
Рубрика: Математика
Размер файла: 15.02 Kb
Скачать файл: referat.me-218326.docx
Краткое описание работы: Министерство образования Республики Беларусь Учреждение образования «Брестский государственный технический университет» Кафедра ИИТ Лабораторная работа №4
Проверка больших чисел на простоту
Министерство образования Республики Беларусь
Учреждение образования
«Брестский государственный технический университет»
Кафедра ИИТ
Лабораторная работа №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
Вывод: Изучили методы генераций больших простых чисел, а так же способы их проверки на простоту.
Похожие работы
-
Проверка статистической гипотезы о нормальном законе распределения случайной величины
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО ТОмский ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОЛОГО-ГЕОГРАФИЧЕСКИЙ ФАКУЛЬТЕТ КАФЕДРА КАРТОГРАФИИ И ГИС Лабораторная работа №3
-
Контрольная работа по дисцеплине Прикладная математика
Министерство образования Республики Беларусь Учреждение образования «Витебский государственный технологический университет» Кафедра «Теоретической и прикладной математики»
-
Колебательно движение материальной точки
Министерство образования и науки Российской Федерации Санкт-Петербургский государственный горный институт имени В.Г. Плеханова (технический университет)
-
Решение задачи линейного программирования симплексным методом
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение Высшего профессионального образования «Волгоградский государственный технический университет»
-
Построение линии пересечения 2-х конусов и цилиндра
Министерство общего и профессионального образования РФ Брянский Государственный Технический Университет кафедра «Высшая математика» Расчетно-графическая работа №1
-
Вычисление корней нелинейного уравнения
Министерство образования Российской федерации Южно-Уральский Государственный Университет Аэрокосмический факультет Кафедра летательных аппаратов
-
Решение систем линейных уравнений
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТОРГОВО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ
-
Решения смешанной задачи для уравнения гиперболического типа методом сеток
МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Р.Ф. КУРГАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра прикладной и высшей математики Лабораторная работа № 43
-
Системы эквивалентные системам с известным типом точек покоя
Министерство образования Республики Беларусь Учреждение образования Гомельский государственный университет имени Франциска Скорины Математический факультет
-
Графы Основные понятия
Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 1 Графы. Основные понятия