Математические основы системы остаточных классов (стр. 18 из 19)
var i,n,b,c,d,v,x,f,f1:longint;
w:real;
a,p:mas;
r:string;
{Оформлениеэкрана}
procedure visitka;
begin
writeln(‘ Министерство образования Российской Федерации ‘);
writeln(‘ Ставропольский государственный университет ‘);
writeln(‘ Кафедра алгебры ‘);
writeln(‘ ‘);
writeln(‘Дипломнаяработа‘);
writeln(‘ ‘);
writeln(‘ Методы перевода чисел из системы остаточных классов‘);
writeln(‘ в позиционную систему счисления ‘);
writeln(‘ ‘);
writeln(‘ Выполнила: Пивоварова Елена Николаевна, ‘);
writeln(‘ФМФ, 5 курс, гр. Б ‘);
writeln(‘Научный руководитель:‘);
writeln(‘заведующая кафедрой алгебры‘);
writeln(‘Копыткова Людмила Борисовна ‘);
writeln(‘‘);
writeln(‘ Нажмитеклавишу <Enter> ‘);
writeln(‘ ‘);
writeln(‘Теоретические сведения‘);
writeln(‘ Программа позволяет производить перевод числа‘);
writeln(‘ А=(а1, а2, …,аn), представленного в СОК с основаниями ‘);
writeln(‘ р1, p2 ,…,pnтакими, что р1< p2 <…<pn и p(i) – простые ‘);
writeln(‘числа, в позиционную систему счисления методом, ‘);
writeln(‘основанным на применении функции Эйлера. Данный метод‘);
writeln(‘заключается в следующем: для нахождения числа A в‘);
writeln(‘позиционной системе счисления берутся 2 модуля:p(i) и p(i+1),‘);
writeln(‘причем p(i) > p(i+1), и соответствующие им остатки а(i) и а(i+1). ‘);
writeln(‘Находится наименьший неотрицательный вычет по модулю ‘);
writeln(‘p(i) * p(i+1). Применяя эту операцию многократно и переходя ‘);
writeln(‘к составным модулям, осуществляют перевод чисел. ‘)
writeln;writeln;writeln;
writeln ('Нажмитеклавишу <Enter>...');
readln;
clrscr;
end; {visitka}
{Вычислениенаименьшегонеотрицательноговычета}
procedure vich (var v:longint; a,m:longint);
begin if a<0 then v:=a+m else v:=a mod m
end;{vich}
{Тест простого числа}
function test (ch:longint):boolean;
var i:longint;
begin i:=2;
while (i<=ch) and ((ch mod i)<>0) do
i:=i+1+(i mod 2);
if i=ch then test:=true else test:=false;
end;{test}
{Вводданных}
procedure DataEnter;
var i:longint;
begin
write('Введитечисломодулей:');
readln(n);
writeln('Вводзначениямодулей (p(i)<=30, p(i)-простые,');
writeln('p(i)<p(i+1)):');
for i:=1 to n do
begin
while true do begin
write('Модуль p',i ,'= ');
readln(p[i]);
if (p[i]<=30) and Test(p[i]) then
begin if i<>1 then begin
if p[i]>p[i-1] then break;
end
else break;
end;
end;{while}
end;{for}
writeln('ВводчиславСОК (a(i)>=0 и a(i)<p(i)):');
for i:=1 to n do
begin
while true do begin
write('a[',i,']=');
readln(a[i]);
if (a[i]>=0) and (a[i]<p[i]) then break;
end;{while}
end;{for}
end;{DataEnter}
{ПереводчиславПСС}
procedure Calcx(var x:longint;p,a:mas);
var i,b,c,f1:longint;
begin
f1:=p[2];
for i:=2 to n do
begin
{ВычислениефункцииЭйлера}
if p[1]<p[i] then f:=p[i]-1;{f-значениефункцииЭйлера, если}
{p[i]-простое число}
f1:=f1*(p[i]-1);
if p[1]>p[i] then
begin b:=p[1];p[1]:=p[i];p[i]:=b;
c:=a[1];a[1]:=a[i];a[i]:=c;
f:=f1 {f - значениефункцииЭйлера, если}
{f - составное число}
end;
{Перевод числа }
w:=exp((f-1)*ln(p[i]-p[1]));
vich(d,round(w),p[i]);
vich(v,a[1]-a[i],p[i]);
vich(v,d*v,p[i]);
x:=v*p[1]+a[1];
p[1]:=p[1]*p[i];
a[1]:=x;
end
end;{Calcx}
begin
repeat
clrscr;
visitka;
dataenter;
calcx(x,p,a);
writeln('A= ',x);
writeln('Повторить? (y/n): ');
readln(r);
until (r= 'n')
end.
Министерство образования Российской Федерации
Ставропольский государственный университет
Кафедра алгебры
Дипломная работа
Методы перевода чисел из системы остаточных классов
в позиционную систему счисления
Выполнила:Пивоварова Елена Николаевна,
ФМФ, 5 курс, гр. Б
Научный руководитель:
заведующая кафедрой алгебры
Копыткова Людмила Борисовна
Нажмите клавишу <Enter>
Теоретические сведения
Программа позволяет производить перевод числа
А=(а1, а2, …,аn), представленного в СОК с основаниями
р1, p2 ,…,pnтакими, что р1< p2 <…<pn и p(i) – простые
числа, в позиционную систему счисления методом,
основанным на применении функции Эйлера.
Данный метод заключается в следующем:
для нахождения числа A в
позиционной системе счисления берутся 2 модуля:
p(i) и p(i+1), причем p(i) > p(i+1), и
соответствующие им остатки а(i) и а(i+1).
Находится наименьший неотрицательный
вычет по модулю p(i) * p(i+1).
Применяя эту операцию многократно и переходя
к составным модулям, осуществляют перевод чисел.
Результаты работы программы
Нажмите клавишу <Enter>…
Введите число модулей:2
Ввод значения модулей (p(i)< =30, p(i)-простые,
p(i)< p(i+1)):
Модуль р1=17
Модуль р2=19
Ввод числа в СОК (а(i)>=0 и (а(i)<p(i)):
a[1]=2
a[2]=3
A=155
Повторить? (у/n):
y
Введите число модулей:3
Ввод значения модулей (p(i)< =30, p(i)-простые,
p(i)< p(i+1)):
Модуль р1=2
Модуль р2=3
Модуль р3=5
Ввод числа в СОК (а(i)>=0 и (а(i)<p(i)):
a[1]=1
a[2]=2
a[3]=4
A=29
Повторить? (у/n):
n
Программа №2
program COK_Poliandr;
type mas1=array [1..10] of integer;
mas2= array [1..10,1..10] of integer;
var p, a, o: mas1;
t: mas2;
Aonc, PP, i, j, y, k, n, f : integer;
begin
writeln ('Перевод чисел из СОК в обобщенную систему счисления ');
write ('Введите размер системы оснований = ');
readln (n);
writeln ('Введите каждое основание ');
PP:=1;{Присвоение начального значения объему диапазона}
for i:=1 to n do begin {Ввод системы оснований и вычисление объёма
диапазона}
write ('p[',i,']= ');
readln (p[i]);
PP:=PP*p[i];
end;
writeln ('ОбъемдиапазонаР =',PP);
writeln ('Введите число в СОК по цифрам: ');
for i:=1 to n do begin{Ввод исходного числа в СОК}
write (i,' цифра= ');
readln (a[i]);
end;
write('Переведём число А = ( '); {Вывод на экран исходного числа}
for i:=1 to n do write (a[i],',');
writeln(') в ОПС.');
writeln ('На первом этапе получим матрицу констант ');
for k:=1 to n do
for J:=k to n do{Вычисление матрицы обратных элементов по
умножению для чисел pk по модулю pj}
begini:=0; f:=0;
repeat if (1+i*p[j]) mod p[k] =0 then begin
t[k,j]:=(1+i*p[j]) div p[k];f:=1;{Флаг поднят, если произошло вычисление константы}
end;
i:=i+1;
until (i>n) or (f=1);{Выход из цикла, если поднят флаг или превышено значение параметра}
end;
for k:=1 to n do begin{Вывод полученной матрицы}
for J:=1 to n do write(t[k,j],' ');
writeln;
end;
write ('ЗатемполучимцифрыОПС: ');
for j:=1 to n do begin o[j]:=a[j];{Получение очередной цифры}
for i:=j to n do begin
if a[i]>=o[j] then a[i]:=a[i]-o[j] {Первое действие}
else a[i]:=a[i]+p[i]-o[j];
a[i]:=a[i]*t[j,i]; {Второе действие}
if a[i]>p[i] then a[i]:=a[i] mod p[i];
end;
write(o[j],' ');{Вывод очередной цифры ОПС}
end;
writeln;
write ('В итоге, получим число: ');
Aonc:=0; y:=1;{Обнуление результата}
for i:=1 to n do begin{Получение числа в позиционной системе счисления по его цифрам }
Aonc:= Aonc+y*o[i];
y:=y*p[i];
end;
writeln (Aonc);{Вывод полученного результата}
readln;{Задержка результата на экране
до нажатия клавиши ENTER}
end.
Результаты работы программы
Перевод чисел из СОК в обобщенную систему счисленияВведите размер системы оснований = 5
Введите каждое основание
p[1]=2
p[2]=3
p[3]=5
p[4]=7
p[5]=11
Объем диапазона Р =2310
Введите число в СОК по цифрам: 1 цифра = 1
2 цифра = 2
3 цифра = 1
4 цифра = 4
5 цифра = 7Переведём число А = ( 1, 2, 1, 4, 7,) в ОПС.
На первом этапе получим матрицу констант 0 0 2 3 4 5
0 0 0 2 5 4
0 0 0 0 3 9
0 0 0 0 0 8
0 0 0 0 0 0
Затем получим цифры ОПС: 1 2 1 0 7
В итоге, получим число: 1481
Применение СОК не ограничивается только переводом чисел из СОК в ПСС и обратно. Например, ещё СОК можно использовать для шифровки сообщений.
Программа №3
В данной программе реализуется шифрование и расшифрование сообщения методом RSA.
Блок-схема алгоритма нахождения А-1modN
Блок-схема алгоритма вычисления ad (modN)
Блок-схема алгоритма нахождения простых чисел не превышающих N
Блок-схема реализации алгоритма RSA
Листинг программы
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include <math.h>
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;
TForm1 *Form1;
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Close();
}
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Log->Lines->Clear();
srand( GetTickCount() );
// Ввод P и Q
int p = StrToInt( Edit1->Text );
int q = StrToInt( Edit2->Text );
Log->Lines->Add( "p = " + IntToStr( p ) );
Log->Lines->Add( "q = " + IntToStr( q ) );
// Вычисление N
intN = p * q;
Log->Lines->Add( "N = p*q = " + IntToStr( N ) );
// Вычисление f(N)
int f = (p-1)*(q-1);
Log->Lines->Add( "f(n)=(p-1)(q-1) = " + IntToStr( f ) );
// Вводоткрытогоключа K1
int k1 = StrToInt( edtOK->Text );
Log->Lines->Add( "k1 = " + IntToStr( k1 ) );
// Проверка условий существования открытого ключа
if( NOD( k1, f ) != 1 )
{
Log->Lines->Add( "открытый ключ и f(n) не взаимно простые. введите новые параметры" );
return;
}
// Нахождение секретного ключа
intk = ObrElem( k1, f );
Log->Lines->Add( "k = k1^(-1) mod f(n) = " + IntToStr( k ) );
AnsiString clear = Edit3->Text;
AnsiString coded;
// Шифрование и расшифрование сообщения
coded = "";
int *clear_c = new int[clear.Length()];
int *coded_c = new int[clear.Length()];
int *clr_c = new int[clear.Length()];
for( int i = 1; i <= clear.Length(); i++ )
{
clear_c[i-1] = (int)clear[i];
coded_c[i-1] = ModStep( clear_c[i-1], k1, N );
clr_c[i-1] = ModStep( coded_c[i-1], k, N );
char temp[256];
wsprintf( temp, "%c = %c = %c", clear[i], (char)coded_c[i-1], (char)clr_c[i-1] );
Log->Lines->Add( temp );
wsprintf( temp, "%c", (char)coded_c[i-1] );
coded += temp;
}
delete[] clr_c;
delete[] coded_c;
delete[] clear_c;
// Вывод полученных результатов
Log->Lines->Add( "cleartext = " + clear );
Log->Lines->Add( "coded text = " + coded );
Log->Lines->Add( "" );
}
// МодульнохожденияНОД (a, b)