Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми факторизації складених чисел
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Алгоритмічні основи криптології
Група:
БІ 21
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІКТА
З В І Т
до лабораторної роботи №4
з курсу: «Алгоритмічні основи криптології»
на тему: «Алгоритми факторизації складених чисел»
Варіант № 13
Львів – 2016р.
Мета роботи – вивчитити основні алгоритми факторизації складених чисел.
Завдання
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.
Варіант
Алгоритм факторизації
Доповнення
13
Факторизація Поларда
Блок-схеми алгоритму програми
Список ідентифікаторів констант, змінних, функцій,
використаних у блок-схемі алгоритму і програмі,
та їх пояснення
a, b, c, d – одновимірні масиви типу integer.
s – змінна типу string, що використовується для зчитування довгих чисел з файлів;
Resheto()– метод який знаходить всі прості числа, менші за n;
Probne_dilennia()– метод який розкладає число на множники методом пробного ділення;
NSD(Int64 m, Int64 n)- шукає НСК чисел m i n;
faktoryzasiia_polarda()- розкладає число на множники методом Ро-Поларда;
Текст програми
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Факторизація_р_поларда
{
class Program
{
static void Main(string[] args)
{
Resheto_Eratosfena t = new Resheto_Eratosfena();
t.Resheto();
t.Probne_dilennia();
t.faktoryzasiia_polarda();
Console.ReadLine();
}
}
class Resheto_Eratosfena
{
int n, i, j, k, gg = 0, Lenth_prosti;
int[] a, prosti;
public void Resheto()
{
n = 300;
a = new int[n];
for (i = 2; i <= n; a[i - 2] = i, i++) ;
for (i = 0; i <= n - 2; i++)
{
if (a[i] != -1)
{
for (j = i + 1; j <= n - 2; j++)
{
if (a[j] % a[i] == 0)
{ a[j] = -1; }
}
}
}
Console.WriteLine();
j = 1;
k = 1;
for (i = 0; i <= n - 2; i++)
{
if (j % (k * 10) == 0) { Console.WriteLine(); k++; }
if (a[i] != -1)
{
Lenth_prosti++;
}
}
prosti = new int[Lenth_prosti];
for (i = 0; i <= n - 2; i++)
{
if (j % (k * 10) == 0) { k++; }
if (a[i] != -1)
{
prosti[gg] = a[i]; j++; gg++;
}
}
for (i = 0; i < Lenth_prosti; i++) ;
}
public void Probne_dilennia()
{
gg=0;
Console.Write("Введіть число n, яке потрібно розкласти на множники n=");
n=Convert.ToInt16(Console.ReadLine());
for (i=0;i<Lenth_prosti;i++)
if ((n % prosti[i]) == 0)
{
a[gg] = prosti[i]; gg++; n = n / prosti[i]; i = -1;
}
Console.WriteLine("\nПрості множники:");
for (i = 0; i < gg; i++)
Console.Write(" {0}",a[i]);
}
Int64 function(Int64 x)
{
Int64 y=0;
y = x * x +x+ 1;
return y;
}
private Int64 NSD(Int64 m, Int64 n)
{
Int64 nsd = 0;
for (Int64 i = (n * m + 1); i > 1; i--)
{
if (m % i == 0 && n % i == 0)
{
nsd = i;
}
}
return nsd;
}
public void faktoryzasiia_polarda()
{
Int64[] mnoshnyky = new Int64[100];
Int64 N,g=0;
Console.Write("\n\n\nВведiть число, яке потрiбно розкласти на множники(методом ро-поларда)\n N=");
N = Convert.ToInt64(Console.ReadLine());
for (int ggg = 0; ggg < 100;ggg++ )
{
Console.WriteLine("N={0}",N);
Int64[] x = new Int64[300];
Int64 d = 1,i=0,y=0,x_x,k=2;
x[0] = 2;
do
{
i++;
x[i] = function(x[i - 1]);
if (x[i] > N)
{ x[i] %= N; }
if (i < k)
{ y = x[k / 2 - 1]; }
else
if (i == k)
{ k *= 2; y = x[k / 2 - 1]; }
if (x[i] < y)
{ x_x = x[i] - y + N; }
else
x_x = x[i] - y;
d = NSD(x_x, N);
} while ((d <= 1) && (i < 280));
if (d != 0)
{ N = N / d; Console.WriteLine(" d={0}", d); mnoshnyky[g] = d; g++; }
if (d == 0)
{ Console.WriteLine(" d={0}", N); mnoshnyky[g] = N; g++; break; }
}
Console.Write("Розклад на мноожники даного числа:");
for (i = 0; i < g; i++)
Console.Write("{0} ",mnoshnyky[i]);
}
}
}
Результати роботи програми
14.05.2016 10:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора