ВУЗ:
Составители:
9
Общие сведения. Для многих криптографических систем актуален так
называемый обобщенный алгоритм Евклида.
Теорема. Пусть
a
и
b
– два целых положительных числа. Тогда существуют
целые (не обязательно положительные) числа
x
и
y
, такие, что
),( baНОДybxa
. (1)
Обобщенный алгоритм Евклида служит для отыскания наибольшего общего
делителя целых чисел
a
,
b
(
),( baНОД
) и
x
,
y
, удовлетворяющих (1).
Введем три строки
),,(
321
uuuU
,
),,(
321
vvvV
и
),,(
321
tttT
.
Запишем обобщенный алгоритм Евклида.
Вход: Положительные целые числа
a
,
b
,
ba
.
Выход:
),( baНОД
,
x
,
y
, удовлетворяющие (1).
1
11
1 1 2 2 3 3
( ,1, 0) , ( , 0,1).
WHILE 0 DO
div ;
( mod , , );
,.
RETURN ( ( , ), , ).
U a V b
v
q u v
T u v u qv u qv
U V V T
U НОД a b x y
В алгоритме операция div– это целочисленное деление, mod – остаток от
деления.
Пример. Пусть
24a
,
15b
. Найдем
),( baНОД
,
x
,
y
.
Выход
U
V
4 шаг
U
V
T
2q
3 шаг
U
V
T
1q
2 шаг
U
V
T
1q
1 шаг
U
V
T
1q
Значения
элементов
строк
24
15
9
6
3
0
1
0
1
– 1
2
– 5
0
1
– 1
2
– 3
8
Вначале в строку
U
записываются числа
)0,1,24(
, а в строку
V
– числа
)1,0,15(
. Вычисляется строка
T
. После этого в строку
U
заносятся данные строки
V
, а в
V
– данные строки
T
. Таким образом, на втором шаге цикла WHILE
