Министерство образования Республики Беларусь
Учреждение образования
«Брестский государственный технический университет»
Кафедра ИИТ
Лабораторная работа №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. Структура системы счисления Китая. Одна из древнейших систем счисления была создана в Китае, а также в Японии. Эта система возникла как результат оперирования с палочками, выкладываемыми для счета на стол или доску. Числа от единицы до пяти обозначались, соответственно, одной, двумя и т.д. палочками, выкладываемыми вертикально, а одна, две, три или четыре вертикальные палочки, над которыми помещалась одна поперечная палочка, означали числа шесть, семь, восемь и девять. (Смотреть таблицу обозначений чисел.)
Доказательство Великой теоремы Ферма 6
Файл: FERMA-ЛАРЧИК © Н. М. Козий, 2009 Авторские права защищены свидетельством Украины 28607 Доказательство Великой теоремы Ферма Великая теорема Ферма формулируется следующим образом: диофантово уравнение:
Свойства чисел Периодическая система чисел
© Автор Бутарева Людмила 29 декабря 2006 г. СВОЙСТВА ЧИСЕЛ ПЕРИОДИЧЕСКАЯ СИСТЕМА ЧИСЕЛ. Свойства чисел натурального ряда, а также производных от них находятся в различной периодической зависимости от порядковых номеров чисел.
Краткое доказательство гипотезы Биля
Гипотеза Биля как неопределенное уравнение, не имеющее решения в целых положительных числах. Использование метода замены переменных. Запись уравнения в соответствии с известной зависимостью для разности квадратов двух чисел. Наличие дробных чисел.
Краткое доказательство гипотезы Билля
Формулировка гипотезы Билля и методика ее краткого доказательства. Анализ составляющих гипотезу алгебраических выражений. Использование метода замены переменных при доказательстве гипотезы Билля, не имеющей решения при целых положительных числах.
Алгебраическое доказательство теоремы Пифагора
Доказательство теоремы Пифагора методами элементарной алгебры: методом решения параметрических уравнений в сочетании с методом замены переменных. Существование бесконечного количества троек пифагоровых чисел и, соответственно, прямоугольных треугольников.
Закономерность распределения простых чисел (дополнение)
Я написал предыдущий ряд разностей по принципу личной симпатии. Подстраховался от критики, ежели бы у кого-то не получилось составить систему уравнений, например, с разностью d = 7, ибо для нетренированных рук могут возникнуть трудности.
Доказательство сильной гипотезы Гольдбаха-Эйлера
Н.М. Козий, 2008, [UA] Свидетельство Украины № 25256 о регистрации авторского права ДОКАЗАТЕЛЬСТВО СИЛЬНОЙ ГИПОТЕЗЫ ГОЛЬДБАХА-ЭЙЛЕРА Сильная гипотеза Гольдбаха-Эйлера формулируется следующим образом: любое четное число, большее двух, равно сумме двух простых чисел:
Краткое доказательство гипотезы Билля
Гипотеза Билля формулируется следующим образом: неопределенное уравнение: не имеет решения в целых положительных числах А, В, С, при условии, что больше 2.
Тест числа на простоту
Алгоритм Миллера-Рабина и малая теорема Ферма. Псевдопростые числа, тест на простоту. Криптографический алгоритм шифрования с открытым ключом и цифровой подписью. Создание открытого и секретного ключей. Режим подписи сообщения и способы ее проверки.
Проверка больших чисел на простоту
Изучение основных подгрупп алгоритмов проверки простоты больших чисел: детерминированные и вероятностные проверки. Исследование методов генерации и проверки на простоту больших чисел с помощью метода Ферма (малая теорема Ферма), составление программы.
Решение головоломки Ж. Арсака
Работа посвящена решению головоломки, условие которой находится в книге Ж.Арсака «Программирование игр и головоломок».
Работа с файлами (лабораторная работа)
Лабораторная работа №2 Т е м а: Р а б о т а с ф а й л а м и. Задание: 1)Создание каталога 1-го уровня; провести проверку. 2)Создание каталога 2-го уровня в каталоге 1-го уровня; установка этого каталога.
Лаба по информатике
Министерство общего и профессионального образования РФ Владимирский Государственный Университет Кафедра УИТЭС Лабораторная работа 1 СИСТЕМЫ СЧИСЛЕНИЯ
Динамические структуры данных: очереди
Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой.
Работа с файлами лабораторная работа
Лабораторная работа №2 Т е м а: Р а б о т а с ф а й л а м и. Задание: 1)Создание каталога 1-го уровня; провести проверку. 2)Создание каталога 2-го уровня в каталоге 1-го уровня; установка этого каталога.
Выполнение арифметических операций над числами с фиксированной запятой
Цель: ознакомиться с командами арифметических операций, вводом данных с клавиатуры и выводом данных на экран. Задание: написать программу ввода с клавиатуры двух чисел в 9-ричной системе счисления размером с слово, выполнения над ними деления и вывода результата в исходной системе счисления. Программа должна предусматривать контроль вводимой информации, контроль диапазона чисел и результата операции (переполнение, невозможность деления).
Численные методы Программа-калькулятор на Pascal
Задание Разработать программу-калькулятор CalcKurs на языке программирования Pascal, реализующую следующие функции: 1. формирование заданного подмножества натурального ряда с помощью общего делителя;
Цузе Конрад
Автор модели механической вычислительной машины, в которой использовались двоичная система счисления , форма представления чисел с плавающей запятой , трехадресная система программирования и перфокарты .
Адамар Жак
В теории чисел Адамар доказал асимптотический закон распределения простых чисел (высказанный П. Л. Чебышевым). В теории дифференциальных уравнений занимался задачей О. Коши для гиперболических уравнений.
Ариабхата I
Ариабхата I (476— ок. 550) — индийский астроном и математик.В сочинении “Ариабхатиам” (499), посвященном астрономии и математике, изложены математические сведения, необходимые для астрономических наблюдений.
Послідовності
План Числова послідовність. Означення границі числової послідовності. Основні теореми про границі. Обчислення деяких границь. Монотонні послідовності.