МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІКТА кафедра БІТ
Звіт до лабораторної роботи № 2 з дисципліни "Алгоритмічні основи криптології" по темі : " ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ" Львів – 2016 Мета роботи - вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забеспечення для реалізації цих алгоритмів на ком'ютері; дослідити швиткодію алгоритмів множення довгих чисел. 1. Завданння 1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами 2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур'є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи № 1. Дані для роботи беруться за вказівкою викладача. 3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 200 до 500. Накреслити графіки відповідних залежностей і порівняти одержані результати. Алгоритм швидкого множення. 2. Блок-схеми алгоритмів Main() FastMult() HowZeros() Show() DivTwo() AplusA() SplusA() ElvestR() MinusOne() InputZ() CounterZeros() OzerZeros() MoreOneZeros() isPair() MoreZeros() 3. Текст програми using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace Crypto_Lab2 { class FastMult { StreamWriter sw = new StreamWriter("results.txt"); int[] a; int[] sa; int[] b; int[] s; int[] so; int n = 0, m = 0; int index = 0; public FastMult(string str1, string str2) { n = str1.Length; m = str2.Length; a = new int[n]; sa = new int[n]; b = new int[m]; s = new int[n + m]; so = new int[n + m]; foreach (char ca in str1) { a[index] = Converter.ToIntDigit(ca); index++; } index = 0; foreach (char cb in str2) { b[index] = Converter.ToIntDigit(cb); index++; } int hz = 0; for (int i = 0; i < s.Length; i++) s[i] = 0; while (MoreZeros(b)) { if (isPair(b)) { // A = A + A Array.Copy(a, sa, a.Length); if ((a[0] + a[0]) >= 10) { a = new int[a.Length + 1]; a[0] = 0; for (int j = 1; j < a.Length; j++) a[j] = sa[j - 1]; sa = new int[a.Length]; Array.Copy(a, sa, a.Length); } a = AplusA(a); // B = B / 2 b = DivTwo(ref b); } else { so = new int[s.Length]; Array.Copy(s, so, s.Length); // S = S + A Array.Copy(s, so, s.Length); if (EldestR(s, a)) { s = new int[s.Length + 1]; s[0] = 0; for (int j = 1; j < s.Length; j++) s[j] = so[j - 1]; so = new int[s.Length]; Array.Copy(s, so, s.Length); } s = SplusA(ref s, a); if (HowZeros(s) > 0) { so = new int[s.Length]; ...