МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІКТА кафедра захисту інформації З В І Т до лабораторної роботи №4 з курсу: “Алгоритмічні основи криптології ” на тему: “Алгоритми факторизації складених чисел” Варіант № 25 1. Мета роботи. 2. Повний текст завдання. 3. Блок-схема алгоритму. 4. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення. 5. Остаточно відлагоджений текст програми згідно з отриманим завданням . 6. Результати виконання програми. 1. Мета роботи Вивчити основні алгоритми факторизації складних чисел. 2. Завдання Реалізувати програму, що дозволяє знаходити розкладання на множники заданого числа n комбінованим методом: р-Полларда і пробних ділень; 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. Результат роботи /