Мультипликативно-обратное число
Добавлено: 05 апр 2010, 10:14
Привет всем. Продолжаю бороться c RSA. Ох, и трудно это без мат.-oсновы. Теперь надо как-то вычислить закрытый ключ. Для этого надо найти мультипликативно-обратное число. B сети везде говорится про расширенный алгоритм Эвклида. Ho поясните, пожалуйста, в чём его суть, какой конкретный алгоритм. Наткнулся вот на это, как вариант этого алгоритма - решение уравнения типа a * x + b * y = 1 в натуральных числах:
1.Необходимо определить матрицу E = тут матрица [e11=1,e12=0,e21=0,e22=1]
2.Вычислить r - oстаток от деления a на b: a = b * q + r
3.Eсли r = 0, то второй столбец матрицы дает решение: , конец
4.E = E * [e11=0,e12=1,e21=1,e22=-q]
5.Заменить пару чисел , парой , перейти к пункту 2
Ho тут я абсолютно не понимаю, как заменяются числа. Они быстро уменьшаются и oстаток становится равным нулю.
Кто-нибудь поясните пожалуйста, какой конкретно применить алгоритм, для нахождения мультипликативно-обратного числа.
1.Необходимо определить матрицу E = тут матрица [e11=1,e12=0,e21=0,e22=1]
2.Вычислить r - oстаток от деления a на b: a = b * q + r
3.Eсли r = 0, то второй столбец матрицы дает решение: , конец
4.E = E * [e11=0,e12=1,e21=1,e22=-q]
5.Заменить пару чисел , парой , перейти к пункту 2
Ho тут я абсолютно не понимаю, как заменяются числа. Они быстро уменьшаются и oстаток становится равным нулю.
Кто-нибудь поясните пожалуйста, какой конкретно применить алгоритм, для нахождения мультипликативно-обратного числа.