Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
АЛГОРИТМИ ФАКТОРИЗАЦІЇ СКЛАДЕНИХ ЧИСЕЛ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет ″Львівська політехніка″
Кафедра БІТ
Звіт
про виконання лабораторної роботи №4
з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ”
на тему: “ АЛГОРИТМИ ФАКТОРИЗАЦІЇ СКЛАДЕНИХ ЧИСЕЛ”
Варіант № 1
Львів 2013
Мета роботи: вивчитити основні алгоритми факторизації складених чисел
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Для криптографічного зламування алгоритму шифрування RSA достатньо розкласти частину відкритого ключа на прості множники, тому завдання факторизації складеного числа є актуальним. Дане завдання зворотне до завдання визначення простоти конкретного числа, але набагато складніше. Далі наведено найбільш прості методи факторизації складеного числа.
1.3. Метод ρ - Полларда.
Алгоритм:
1. Вибираємо випадковим чином xi з множини {0,1,…,n-1}; yx1; k2.
2. ii+1 і обчислюємо наступний елемент послідовності
xif(xi-1)mod n.
3. Якщо dHСД(y- xi, n): d1 і dn то d дільник n, цикл завершений.
4. Якщо i дорівнює k, то y xi, k2k.
Можливо, що кількість значень за модулем n виявиться більшим ніж . Метод має евристичну оцінку складності O(n1/4) арифметичних операцій. Він використовується для відділення невеликих простих дільників факторизованого числа n.
Основна ідея даного методу така. Якщо період послідовності xi mod n може бути порядку n, то період послідовності xi mod p для простого дільника p числа n не перевищує p. Це означає, що y і xi можуть бути різними за модулем n, але збігатися за модулем p.
Існує константа c, така, що для будь-якого >0 ймовірність не знайти нетривіальний дільник n за clog3n бітових операцій буде меншою, ніж e.
2. ЗАВДАННЯ
1. Реалізувати програму, що дозволяє знаходити розклад на множники заданого числа n:
a) методом пробних ділень;
б) згідно заданого варіанту в таблиці 1;
в) комбінованим методом: на першому етапі методом пробних ділень перевіряється розкладність n; якщо n пройшло цей тест, то на другому етапі застосовуйте заданий у варіанті алгоритм.
Слід зважати на те, що всі представлені методи шукають тільки один дільник n. Таким чином, необхідно застосовувати метод кілька разів, поки не вийде повний розклад числа на множники.
2. Приступаючи до факторизації числа, потрібно спочатку переконатися, що воно не просте за допомогою тестів на простоту. Ці тести простоти, як правило, потребують значно менше часу, ніж алгоритми факторизації. Парне число також не потрібно факторизувати.
3. Порівняти два реалізовані методи за часом розкладу досить великого n (наприклад, з 15-ма десятковими розрядами).
4. У методі пробних ділень обмежитися діленням на такі прості числа:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,19,193,197,199,211,223,227,229,233,239,241,251.
5. У звіті обов'язково повинні бути присутніми тести, підтверджуючі правильність розроблених програм.
Варіант
Алгоритм факторизації
Доповнення
1
Метод ρ-Поларда
3. Блок-схема алгоритму
randomNumber(int n)
factorise(int n)
check(int secondDiv)
SCD(int firstNumber, int secondNumber)
button1_Click(object sender, EventArgs e)
4. Cписок ідентифікаторів констант, змінних, функцій, використаних у блок-схемі алгоритму і програмі, та їх пояснення.
massDiv – масив типу int, що приймає значення дільників;
j, x, oldx, d – змінні типу int, що використовуються у методі р-Полларда;
n — змінна, що факторизується;
correction — змінна, що відповідає за точність результату;
randomNumber()– метод, що генерує випадкове число;
check()– метод логічного типу, що повертає відповідне значеня в залежності від числа;
factorise ()– метод р-Полларда факторизації складного числа;
SCD ()– метод, що повертає найменше спільне кратне двох чисел;
Form1_Load ()– метод, що виконується безпосередньо післа завантаження програми;
button1_Click () – метод, який виконує моделацію натиску на програмну кнопку;
5. Текст програми
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace k2_s2_lab4
{
public partial class Form1 : Form
{
public static List<int> massDiv = new List<int>();
public static int massDivLength;
public static int j, x, oldx, d, n;
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
int temp;
textBox2.Text = "";
try { n = Convert.ToInt32(textBox1.Text); }
catch (Exception) { textBox2.Text = " Avaible range 3<number<2147000598; "; return; }
if (n < 3) { textBox2.Text = " Avaible range 3<number<2147000598; "; return; }
factorise(n);
int secondDiv = n / d;
textBox2.Text += d;
while (true)
{
if (check(secondDiv) == true)
{
textBox2.Text += " * " + SCD(secondDiv, secondDiv);
temp = secondDiv / SCD(secondDiv, secondDiv);
if (check(temp) == false) { textBox2.Text += " * " + temp; break; }
else { secondDiv = temp; }
}
else { textBox2.Text += " * " + secondDiv; break; }
}
}
private bool check(int secondDiv)
{
for (int i = 0; i < massDivLength; i++)
{
if (secondDiv == massDiv[i]) break;
if (secondDiv % massDiv[i] == 0) { return true; }
}
return false;
}
private int factorise(int n)
{
d = 1;
j = 1;
if (check(n) == false) { textBox2.Text = "Number " + n + " is prime -> "; return 0; }
x = RandomNumber(n-1);
while (true)
{
oldx = x;
for (int i = 1; i < j; i++)
{
x = ((x * x) + 1) % n;
d = SCD(Math.Abs(x - oldx), n);
if (d > 1 && d < n) { return d; }
}
j *= 2;
}
}
private int SCD(int firstNumber, int secondNumber)
{
//e.g. 3,18;
int scd;
int sdfn=1;
for (int i = 0; i < massDivLength; i++)
{
if (firstNumber % massDiv[i] == 0)
{
sdfn = massDiv[i];
if (secondNumber % sdfn == 0) { scd = sdfn; return scd; }
}
}
return 1;
}
private int RandomNumber(int n)
{
Random rNum = new Random();
return rNum.Next(1, n);
}
private void Form1_Load(object sender, EventArgs e)
{
for (int i = 2; i < 256; i++) { massDiv.Add(i); }
massDivLength = massDiv.Count;
}
}
}
6. Результат роботи
31.05.2014 15:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора