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

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2012

Тип роботи:

Звіт про виконання лабораторної роботи

Предмет:

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

Завантажити

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

Міністерство освіти і науки України Національний університет ″Львівська політехніка″ Звіт про виконання лабораторної роботи №2 з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ” на тему: “ ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ ” Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел. Завдання: Домашня підготовка до роботи 1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами. 2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача. 3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати. № з/п Операції з довгими числами 2 Швидке множення Робота в лабораторії 1) Ввести в комп'ютер програми згідно з отриманим завданням. 2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками. 3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи. 4) Здати звіт з лабораторної роботи. Блок -схема головної програми Блок-схема алгоритму швидкого множення Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах , та їх пояснення MaxDigit – константа що вказує на максимальну довжину масиву; Osn – константа що вказує на основу; Input() ввід довгого числа з клавіатури; Output() вивід довгого числа на екран; Quick()швидке множення двох довгих чисел ; ch – елемент типу CHAR; masCh – массив елементів типу CHAR; a[] – массив, що представляє довге число; b[]– массив, що представляє довге число; c[]– массив, що представляє довге число; i, j, k – цілі змінні, що використовуються в циклі. Остаточна версія програми #include <iostream> #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <ctype.h> #define MaxDig 100 #define Osn 10000 using namespace std; long int *Input( char masivCh[]) { long int *a,a22; char ch; a = (long int*)malloc(MaxDig*sizeof(int)); int i=0, j=0; for(i=0; i<MaxDig; i++) { a[i]=0; } a[0]=1; for(j=0; masivCh[j] != NULL; j++) {ch=masivCh[j]; if (isdigit(ch)) { for (i=a[0]; i>=1; i--) { a[i+1]=a[i+1]+(a[i]*10)/Osn; a[i]=a[i]*10%Osn; } a22=atoi(&ch); a[1]=a[i+1]+a22; if (a[a[0]+1]>0) a[0]++; } } return a; } void Output(long int *b) { long int result; int k=0, r=1,p,b_Osn=b[0],i=0; for(i=b[0]; i>=1; i--) { k=b[i]; if (k==0) r=0; for (p=1; k>0; p=p*10) { k=k/10; } while (Osn-p!=0) { if (b[0]==i) break; printf("%c",'0'); p=p*10; } if (r==1) { result=b[i]; printf("%d",result); } r=1; k=0; } } bool parne(long int* b) { bool c; if(b[b[0]]%2==0) c=true; else c=false; return c; } long int* dil(long int*b) { long int Ost,B; int i; Ost=0; for(i=1; i<MaxDig;i++) {B=Ost*10+b[i]; b[i]=B/2; Ost=B%2; }return b; } bool more(long int* a,long int* b) {int i; if(a[0]<b[0]) return false; else if (a[0]>b[0])return true; else {i=a[0]; while(i>0 && a[i]==b[i]) i--; if (i==0)return false; else if (a[i]>b[i])return true; else return false; } } int chekEquality(long int* a, long int* b) { int e; if (a[0]==b[0]) {e=1; } else {e=0; } for (long i=a[0]; i>=1; i--) {if (a[i]==b[i]) {continue; } else if (a[i]==b[i]) {e=1; } else {e=0; } } return e; } long int* Sub(long int a[MaxDig],int sp=0) {int i,j,e; int minus=0; long int* ta,*tb,*c,*b; c=(long int*)malloc(MaxDig*sizeof(int)); b=(long int*)malloc(MaxDig*sizeof(int)); for (i=0; i<MaxDig;i++) b[i]=0; b[0]=1; b[1]=1; if(more(a,b)==0) { minus=0;ta=a; tb=b; } else {e=chekEquality(a,b); if (e) {for(i=0;i<MaxDig;i++) c[i]=0; } Else { minus=1; ta=b; tb=a; } } for(i=0;i<MaxDig;i++) c[i]=a[i]; for (i=1;i<=b[0];i++) c[i+sp]-=b[i]; j=i; while(c[j+sp]<0 && j<=c[0]) { c[j+sp]+=Osn; c[j+sp+1]--; j++; } if(minus==1) cout<<"-"; i=c[0]; while (i>1 && c[i]==0)i--; c[0]=i; return c; } long int *Sum(long int a[], long int b[]) { int k,i; long int *c; c=(long int*)malloc(MaxDig*sizeof(int)); for( i=0; i<MaxDig; i++) {c[i]=0; } if(a[0]>b[0]) {k=a[0]; } else {k=b[0]; } for(i=1; i<=k; i++) {c[i+1]=(c[i]+a[i]+b[i])/Osn; c[i]=(c[i]+a[i]+b[i])%Osn; } if (c[k+1]==1) {c[0]=k+1; } Else { c[0]=k; } return c; } long int* Quick(long int* a,long int* b) { int i; long int *s; s=(long int*)malloc(sizeof(int)*MaxDig); for(i=0;i<MaxDig;i++) s[i]=0; s[0]=1; if(b[0]>0 && b[0]!=1) {if(parne(b)) {a=Sum(a,a); b=dil(b); } else {s=Sum(s,a); b=Sub(b); } } else return s; } int main() { long int *a=0,*c=0,*b=0; for(;;) {do { print(); s = getch(); printf("\n"); } while(!isdigit(s)); switch(s) case '1': printf("multiplication\n\n"); char masivCh1[100];char masivCh2[100]; cout<<"enter first long number :"; cin>>masivCh1; a = Input(masivCh1); cout<<"\n enter second long number :"; cin>>masivCh2; b = Input(masivCh2); c=Quick(a,b); Output(c); break; case '0': exit(0); break; } printf("\n\n"); } return 0; } } Результати виконання програми:

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

18.07.2012 22:54

Коментарі

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

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

поділитись