Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Група:
ІБ-44
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ЗВІТ
про виконання лабораторної роботи №2
з курсу:
«Алгоритмічні основи криптології»
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері.
Завдання:
Скласти програму для реалізації операцій множення довгих чисел з використанням перетворення Фур’є.
Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах та їх пояснення
max – константа що вказує на максимальну довжину масиву;
оsn – константа що вказує на основу;
vvid() – ввід довгого числа з клавіатури;
vyvid()- вивід довгого числа на екран;
shpf() – знаходження ШПФ від числа;
dpf() – знаходження ДПФ від числа;
transf() – здійснює перенесення;
scal_mult() – здійснює скалярне множення двох векторів;
mult() – множення двох довгих чисел;
ch – елемент типу CHAR;
masCh – масив елементів типу CHAR;
a[], b[],c[] – масиви, що представляють довгі числа;
y[][], y1[][],y2[][] – двовимірні масиви, що представляють довгі числа;
i, j, k – цілі змінні, що використовуються в циклі;
N, NN, p, k, tt – проміжні змінні, що використовуються у підпрограмах.
Блок-схема алгоритму програми
Головна програма
функція vvid
функція vyvid
функція shpf
функція roun
функція dpf
функція mult
функція scal_mult
функція transf
Текст програми
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <math.h>
#define max 100
#define osn 10000
#define Pi 3.141592653589793
long roun(double x);
void vvid(long a[max]);
void vyvid(long a[max]);
void shpf(long a[max], double y[max][2], int N);
void mult(long a[max], long b[max], long c[max]);
void scal_mult(double y1[max][2], double y2[max][2], double y[max][2]);
void transf(long c[max]);
void dpf(double y[max][2], long c[max], int N);
long int*vvid( char masCh[])
{
long int *a;
char ch;
a = (long int*)malloc(max*sizeof(int));
int i = 0;
int j = 0;
for(i = 0; i < max; i++)
{
a[i] = 0;
}
for(j = 0; masCh[j] !=0; 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 vyvid(long 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;
}
}
long int* mult (long int a[], long int b[])
{
long int *tt, *c; int j = 0, i = 0, k = 0;
tt = new long int[max]; c = new long int[max];
for(i = 0; i < max; 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;
}
void shpf(long a[max], double y[max][2], int N)
{
int i,j,k;
for(i=0;i<max;i++)
for(j=0;j<2;j++)
y[i][j]=0;
for(j=0;j<N;j++)
{
for(i=0;i<a[0];i++)
{
y[j][0]=y[j][0]+a[a[0]-i]*cos(2*Pi*i*j/N);
y[j][1]=y[j][1]+a[a[0]-i]*sin(2*Pi*i*j/N);
}
}
}
long roun(double x)
{
if(x>=0)
return ((long)(x+0.5));
else
return ((long)(x-0.5));
}
void dpf(double y[max][2], long c[max], int N)
{
int i,j;
double t=0;
for(i=0;i<max;i++)
c[i]=0;
for(j=0;j<N;j++)
{
for(i=0;i<N;i++)
{
t=t+(y[i][0]*cos(2*Pi*i*j/N)-y[i][1]*sin(-2*Pi*i*j/N));
}
c[j]=roun(t/N);
t=0;
}
}
void mult(long a[max], long b[max], long c[max])
{
double y1[max][2];
double y2[max][2];
double y[max][2];
int i;
int N;
i=1;
do
{
N=pow(2,i);
i++;
}
while((a[0]+b[0])>N);
shpf(a,y1,N);
shpf(b,y2,N);
scal_mult(y1,y2,y);
dpf(y,c,N);
for(i=0;i<max;i++)
printf("%ld ",c[i]);
printf("\n");
transf(c);
}
void scal_mult(double y1[max][2], double y2[max][2], double y[max][2])
{
int i,j;
long t;
for(i=0;i<max;i++)
for(j=0;j<2;j++)
y[i][j]=0;
for(i=0;i<max;i++)
{
y[i][0]=y1[i][0]*y2[i][0]-y1[i][1]*y2[i][1];
y[i][1]=y1[i][0]*y2[i][1]+y1[i][1]*y2[i][0];
}
}
void transf(long c[max])
{
int i,j;
long t,Osn;
Osn=pow(10,Osn);
for(i=0;i<max-1;i++)
{
t=c[i]/Osn;
c[i+1]=c[i+1]+t;
c[i]=c[i]-t*Osn;
}
j=0;
for(i=max-1;(i>=0)&&(c[i]==0);i--) j++;
j=max-j;
for(i=j;i>=roun(j*1.0/2);i--)
{
t=c[i];
c[i]=c[j-i];
c[j-i]=t;
}
c[0]=j;
}
int main()
{
long int *a = 0, *b =0, *c = 0;
char masCh1[100] , masCh2[100];
printf("Vvedit pershe chyslo: a=");
gets(masCh1);
a = vvid(masCh1);
printf("Vvedit druge chyslo: b=");
gets(masCh2);
b = vvid(masCh2);
c = mult(a,b);
printf("a*b=");
vyvid(c);
printf("\n");
system("PAUSE");
getch();
return 0;
}
Результат роботи програми
Висновок: на даній лабораторній роботі я вивчив алгоритм множення довгих чисел та навчитися розробляти програмне забезпечення для його реалізації на комп’ютері.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора