ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ. Звіт до лабораторної роботи з Алгоритмічні основи криптології. Робота № 526246

ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКТА

Факультет:

ЗІ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2014

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Алгоритмічні основи криптології

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ, МОЛОДІ ТА СПОРТУ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» ІКТА З В І Т до лабораторної роботи №2 з курсу: «Алгоритмічні основи криптології» на тему: «ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ» Варіант № 9 Львів – 2013р. Мета роботи - вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел. Завдання 2.1. Домашня підготовка до роботи 1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами. 2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача. 3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 200 до 500. Накреслити графіки відповідних залежностей і порівняти одержані результати. 2.2. Робота в лабораторії 1) Ввести в комп'ютер програми згідно з отриманим завданням. 2) Відлагодити програми. У випадку необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками. 3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи. 4) Здати звіт з лабораторної роботи. Блок-схеми алгоритму програми Блок-схема алгоритму швидкого множення довгих чисел. Список ідентифікаторів констант, змінних, функцій, використаних у блок-схемі алгоритму і програмі, та їх пояснення a, b, c, d – одновимірні масиви типу integer. s – змінна типу string, що використовується для зчитування довгих чисел з файлів; Vvedennia_Chysla – метод який не має аргументів, забезпечує зчитування довгих чисел з файлів; Vyvedennia_Chysla(int[] d, string st)– метод який реалізовує виведення довгого числа d, а також він виводить на екран значення змінної st; Rivnist(int[] q1, int[] q2)- метод, який перевіряє рівність двох довгих чисел q1 s q2, даний метод повертає значення типу boolean(true або false); Bilshe(int[] q1, int[] q2) - метод, що перевіряє чи число q1 є більшим за q2, повертає значення типу bool; Dodavannia(int[] q1, int[] q2) - метод, що здійснює додавання двох довгих чисел q1 і q2. Текст програми using System; using System.IO; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication3 { class Program { static void Main(string[] args) { dovge_Chyslo t = new dovge_Chyslo(); Console.ReadLine(); } } class dovge_Chyslo { string s; bool flag; int[] a, b, c, d; int i, j, n, g, osn, k, temp, f; public dovge_Chyslo() { flag = true; k = 4; osn = 10000; Zchytuvannia_a_b(); Shvydke_mn(a, b); Vyvedennia_Chysla(d, "a*b: "); } void Vvedennia_Chysla() { FileStream stream = new FileStream(s + ".txt", FileMode.Open); StreamReader reader = new StreamReader(stream); s = reader.ReadToEnd(); stream.Close(); n = s.Length / k; g = s.Length % k; if (g != 0) n++; c = new int[n + 1]; c[0] = n; s.ToCharArray(); for (i = s.Length - 1; i >= g; i -= k) { for (j = 0, temp = 0; j < k; j++) temp += (Convert.ToInt32(s[i - j]) - 48) * Convert.ToInt32(Math.Pow(10, j)); c[n] = temp; n--; } if (g != 0) { for (j = 0, temp = 0; j < g; j++) temp += (Convert.ToInt32(s[g - j - 1]) - 48) * Convert.ToInt32(Math.Pow(10, j)); c[n] = temp; } } void Zchytuvannia_a_b() { s = "a"; Vvedennia_Chysla(); a = new int[c[0] + 1]; for (i = 0; i < c[0] + 1; a[i] = c[i], i++) ; s = "b"; Vvedennia_Chysla(); b = new int[c[0] + 1]; for (i = 0; i < c[0] + 1; b[i] = c[i], i++) ; Vyvedennia_Chysla(a, "a "); Vyvedennia_Chysla(b, "b "); } void Vyvedennia_Chysla(int[] d, string st) { Console.Write("{0}{1}", st, d[1]); for (i = 2; i < d[0] + 1; i++) { n = d[i]; for (j = 4; n != 0; n /= 10, j--) ; for (g = 0; g < j; g++) Console.Write("0"); if (d[i] != 0) Console.Write(d[i]); } Console.WriteLine(); } bool Rivnist(int[] q1, int[] q2) { if (q1[0] != q2[0]) return false; for (i = 1; i < q1[0] + 1; i++) if (q1[i] != q2[i]) return false; return true; } bool Bilshe(int[] q1, int[] q2) { if (q1[0] < q2[0]) return false; else if (q1[0] > q2[0]) return true; for (i = 1; i < q1[0] + 1; i++) if (q1[i] < q2[i]) return false; else if (q1[i] > q2[i]) return true; return false; } void Dodavannia(int[] q1, int[] q2) { if (Bilshe(q1, q2)) n = q1[0] + 1; else n = q2[0] + 1; c = new int[n + 1]; c[0] = n; for (i = 1; i < n + 1; c[i] = 0, i++) ; for (i = c[0], j = q1[0], f = q2[0]; i > 0; i--, j--, f--) { g = 0; if (j > 0) g += q1[j]; if (f > 0) g += q2[f]; c[i] += g % osn; if (i > 1) c[i - 1] = g / osn; } g = 0; if (c[1] == 0) { n--; g += 1; } d = new int[n + 1]; d[0] = n; for (i = 1; i < n + 1; i++) d[i] = c[i + g]; } bool Vidnimannia(int[] q1, int[] q2) { if (Rivnist(q1, q2)) { d = new int[2]; d[0] = 1; d[1] = 0; return true; } else if (Bilshe(q1, q2)) { flag = true; Vidnimannia_2(q1, q2); } else { flag = false; Vidnimannia_2(q2, q1); } return flag; } void Vidnimannia_2(int[] q1, int[] q2) { n = q1[0]; c = new int[n + 1]; c[0] = n; for (i = 1; i < n + 1; c[i] = 0, i++) ; for (i = c[0], j = q1[0], f = q2[0], g = 0; i > 0; i--, j--, f--) { if (j > 0) g += q1[j]; if (f > 0) g -= q2[f]; if (g < 0) { c[i] = osn + g; if (i > 1) g = -1; } else { c[i] = g; g = 0; } } g = 0; if (c[1] == 0) { n--; g += 1; } d = new int[n + 1]; d[0] = n; for (i = 1; i < n + 1; i++) d[i] = c[i + g]; } void Shvydke_mn(int[] q1, int[] q2) { int te1 = 0, te2 = 0; int[] q3 = new int[2]; q3[0] = 1; q3[1] = 0; int[] s = new int[q1[0] + q2[0] + 1]; s[0] = q1[0] + q2[0]; for (i = 1; i < s[0] + 1; s[i] = 0, i++) ; while (Bilshe(q2, q3)) if (q2[q2[0]] % 2 == 0) { Dodavannia(q1, q1); q1 = new int[d[0] + 1]; for (i = 0; i < d[0] + 1; q1[i] = d[i], i++) ; for (i = 1; i < q2[0] + 1; i++) { q2[i] = q2[i] + te2 * osn; te1 = q2[i] / 2; te2 = q2[i] % 2; q2[i] = te1; } } else { Dodavannia(s, q1); for (i = d[0]; i > 0; s[i] = d[i], i--) ; q3[1] = 1; Vidnimannia(q2, q3); q2 = new int[d[0] + 1]; for (i = 0; i < d[0] + 1; q2[i] = d[i], i++) ; q3[1] = 0; } for (j = 1; s[j] == 0; j++) ; d = new int[s[0] - j + 2]; d[0] = s[0] - j + 1; for (i = s[0], f = d[0]; f > 0; i--, f--) d[f] = s[i]; } } } Результати роботи програми

Звіт до лабораторної роботи Алгоритмічні основи криптології

telipalo

31.05.2014 14:40

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись