Міністерство освіти і науки України Національний університет ″Львівська політехніка″ Кафедра захисту інформації
Звіт про виконання лабораторної роботи №2 з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ” на тему: “ Дослідження швидкодії виконання мультиплікативних операцій з довгими числами ” Перевірив: Лагун А.Е. Львів 2009 Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел. Завдання: Домашня підготовка до роботи 1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами. 2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача. 3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати. Робота в лабораторії 1) Ввести в комп'ютер програми згідно з отриманим завданням. 2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками. 3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи. 4) Здати звіт з лабораторної роботи. Блок -схема головної програми Output(c) а*b= b = Input(masivCh2) a = Input(masivCh1) початок Vvedit first chuslo: a= masivCh1 Vvedit first chuslo: b= masivCh2 c = MultiLongLong(a,b) кінець Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах , та їх пояснення MaxDigit – константа що вказує на максимальну довжину масиву; Osn – константа що вказує на основу; Input() ввід довгого числа з клавіатури; Output() вивід довгого числа на екран; MultiLongLong() множення двох довгих чисел способом стовпчика; ch – елемент типу CHAR; masCh – массив елементів типу CHAR; a[] – массив, що представляє довге число; b[]– массив, що представляє довге число; c[]– массив, що представляє довге число; i, j, k – цілі змінні, що використовуються в циклі. Остаточна версія програми #include <stdio.h> #include <stdlib.h> #include <ctype.h> #define MaxDigit 100 #define osn 10000 int*Input( char masCh[]) { int *a; char ch; a = (int*)malloc(MaxDigit*sizeof(int)); int i = 0; int j = 0; for(i = 0; i < MaxDigit; i++) { a[i] = 0; } for(j = 0; masCh[j] != NULL; j++) { if ( isdigit(masCh[j]) ) { for (i = a[0]; i >= 1; i--) { a[i + 1] = a[i + 1] + (a[i] * 10) / osn; a[i] = a[i] * 10 % osn; } ch = masCh[j]; int a22 = atoi(&ch); a[1] = a[i+1] + a22; if (a[a[0] + 1] > 0) a[0]++; } } return a; } void Output(int *b) { int N = 0; int NN = 1; int p; int b_Osn = b[0]; int i = 0; for(i = b[0]; i>=1 ; i--) { N = b[i]; if (N == 0) NN = 0; for (p = 1; N > 0; p = p*10) { N = N / 10; } while (osn - p != 0) { if (b[0] == i) break; printf("%c",'0'); p = p*10; } if (NN == 1) { int result = b[i]; printf("%d",result); } NN = 1; N = 0; } } int* MultiLongLong(int a[], int b[]) { int *tt, *c; int j = 0, i = 0, k = 0; tt = new int[MaxDigit]; c = new int[MaxDigit]; for(i = 0; i < MaxDigit; i++) { tt[i] = 0; } c[0] = a[0]; for(i = 1; i <= b[0]; i = i+1) { for(j = 1; j <= c[0]; j++ ) { c[j] = 0; } for(j = 1, k = i; j <= a[0]; j = j+1, k = k+1) { c[j+1] = (a[j]*b[i] + c[j] + tt[k])/osn; c[j] = (a[j]*b[i] + c[j] + tt[k])%osn; } if(c[j] != 0) c[0] = c[0]+1; for(j = i, k = 1; j <= c[0]; j= j+1, k = k+1) { tt[j] = c[k]; } tt[0] = c[0]; } for(i = 1; i <= c[0]; i = i+1) { c[i] = tt[i]; } return c; } int main() { int *a = 0, *b =0, *c = 0; char masCh1[100] , masCh2[100]; printf("Vvedit first chuslo: a="); gets(masCh1); a = Input(masCh1); printf("Vvedit second chuslo: b="); gets(masCh2); b = Input(masCh2); c = MultiLongLong(a,b); printf("a*b="); Output(c); printf("\n"); system("PAUSE"); return 0; } Результат роботи програми