Здравствуйте. Начал разбираться в RSA-кодировании, конструкцию шиврования/дешифрования в целом понял, НО... возникла одна неясность:
учу я это кодирование по книге Брюса Шнайера "Прикладная криптография" и воспрос заключаеться в том, что в описании этого алгоритма в данной книге в разделе 19.3 есть пример зашивровки с помощью RSA, там есть такая строка

d = 79^(-1) mod 3220 = 1019

Как можеть получиться так, что остаток от деления <79 в минус первой степени> на <3220> будет равным <1019> ???
Еще написанно, что при вычислении этого числа был использован расширенный алгоритм Эвклида (раздел 11.3 этой же книги), я и этот раздел прочитал, но каким образом получилось значени 1019 при выподнении этой операции неизвестно, там только описываеться что такое вообще остаток от деления и зачем он нужен.
Если кто-то сталкивался с RSA-кодированием и понимает как получился данный момент, подскажите пожалуйста...
Спасибо.

LLX>d = 79^(-1) mod 3220 = 1019

LLX>Как можеть получиться так, что остаток от деления <79 в минус первой степени> на <3220> будет равным <1019> ???

Это просто: -1 степень имеется ввиду по модулю, то есть, по определению 79^(-1) mod 3220 это такое число x, что
x*79 mod 3220 = 1
проверяем: 79*1019 = 80501 = 25*3220 + 1

О! Спасибо огромнейшее... теперь ясно хоть что-то...
А как же получить в данном случае число 1019 зная только 79 и 3220 ?

Здравствуйте, LexusLX470, Вы писали:

LLX>О! Спасибо огромнейшее... теперь ясно хоть что-то...
LLX>А как же получить в данном случае число 1019 зная только 79 и 3220 ?

Надо решить Диафантово уравнение:
79*x-3220*n=1
с целыми x и n

Алгоритм Эвклида здесь подходит таким боком. Пусть дана пара чисел
(a,b). Он выдаёт цепочку равенств
a = b*q_1+r_1
b = r_1*q_2 + r_2
r_1 = r_2*q_2 + r_2
.
.
.
r_{n-2} = r_{n-1} q_n + r_n
r_{n-1} = r_n * q_{n+1} + 0
С убывающими остатками b > r_1 > r_2 > ... > r_n > 0
То есть каждый раз из пары чисел (a,b) делаем следующую пару (b,r) где r -- остаток от деления a на b
Последнее r_n и есть наибольший общий делитель. (=1 в нашем случае)
Теперь используя эту последовательность можно найти решение уравнения.
a*x+b*y=d
А именно, из первого равенства выражаем r_1 через a и b: r_1 = a — b*q_1
Из 2-ого r_2 через b и r_1, а потом последнее через a и b r_2 = b — r_1 * q_2 = b-(a-b*q_1)*q_2 = b*(1+q_1*q_2)-a*q_2
и так далее. В конце концов выражаем r_n=q(=1 в нашем случае) через a и b