Методы и задачи криптографической защиты информации. Мартынов А.И. - 83 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

кроме чисел, кратных данному простому числу. Одним из способов вычислить
наибольший общий делитель двух чисел является алгоритм Эвклида.
На языке Си, алгоритм выглядит так:
int gcd (int x, int y) {
int g;
if (x < 0)
x = -x;
if (y < 0)
y = -y;
if (x + y == 0 )
ERROR ;
g = y;
while (x > 0) {
g = x;
x = y % x;
y = g;
}
return g;
В общем случае у уравнения a
–1
≡ x (mod n) существует единственное
решение, если a и n взаимно просты. Если a и n не являются взаимно простыми,
то a
–1
≡ x (mod n) не имеет решений. Если n является простым числом, то любое
число от 1 до n–1 взаимно просто с n и имеет в точности одно обратное
значение по модулю n.
Обратное значение a по модулю n можно вычислить с помощью
алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.
Вот этот алгоритм на языке Cи:
//--------------------------------------------------------
#include <stdio.h>
#pragma hdrstop
//--------------------------------------------------------
#pragma argsused
void swap(unsigned long &x, unsigned long &y)
{
unsigned long t;
t = x;
x = y;
y = t;
}
int even(unsigned long x)
{
return ((x & 0x01) == 0);
}

Страницы