antibotan.com

ВСЕУКРАЇНСЬКИЙ СТУДЕНТСЬКИЙ АРХІВ

Алгоритми факторизації складених чисел




Тип роботи:
Лабораторна робота
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
ЗІ
Предмет:
Алгоритмічні основи криптології
Група:
БІ 21
Вартість:
2 бала

Посилання на дану роботу:

http://antibotan.com/file.html?work_id=528213


Опублікувати посилання:

Завантажень:

4


Частина тексту файла:

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІКТА
З В І Т до лабораторної роботи 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;iif ((n % prosti[i]) == 0)
{
a[gg] = prosti[i]; gg++; n = n / prosti[i]; i = -1;
}
Console.WriteLine("nПрості множники:");
for (i = 0; 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("nnnВведiть число, яке потрiбно розкласти на множники(методом ро-поларда)n N=");
N = Convert.ToInt64(Console.ReadLine());
for (int ggg = 0; ggg
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]);
}
} } Результати роботи програми



Коментарі

Залишити коментар »

 

Ви не можете залишити коментар.

Для цього, будь ласка, увійдіть або зареєструйтесь.