МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» ІКТА З В І Т до лабораторної роботи №4 з курсу: «Алгоритмічні основи криптології» на тему: «Алгоритми факторизації складених чисел» Варіант № 9 Львів – 2013р. Мета роботи – вивчитити основні алгоритми факторизації складених чисел. Завдання 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. Варіант Алгоритм факторизації Доповнення  9 Метод ρ -Поларда 
  Блок-схеми алгоритму програми
Список ідентифікаторів констант, змінних, функцій, використаних у блок-схемі алгоритму і програмі, та їх пояснення 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]); } } } Результати роботи програми