Мультипликативно-обратное число

fotopo · Сообщение **fotopo** » 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статок становится равным нулю.
Кто-нибудь поясните пожалуйста, какой конкретно применить алгоритм, для нахождения мультипликативно-обратного числа.

bot · Сообщение **bot** » 05 апр 2010, 13:10

См, например, здесь или погуглите сами по ключевым словам Алгоритм Евклида, Paсширенный алгоритм Евклида.

Суть дела в следующем. Нам известно, что для целых $$a$$

и

существует линейное представление c целыми коэффициентами $$u$$

и

:

$u\cdot a+ v\cdot b=d$ . Это $$d$$

является наименьшим положительным целым числом представимым в таком виде. Стартуем c двух очевидных представимых чисел (считаем, что $r_0=a\geq b=r_1$ )

$u_0\cdot a + v_0\cdot b = r_0, \ u_0=1,\ v_0=0$
$u_1\cdot a + v_1\cdot b = r_1, \ u_1=0,\ v_1=1$

Совершим один шаг Алгоритма Евклида - делим $$r_0$$

на

c oстатком: $$r_0=q_1r_1+r_2$$

. Вычитая из первой строки вторую, домноженную на $$q_1$$

получим третью строку
$u_2\cdot a + v_2\cdot b = r_2, \ u_2=u_0-q_1u_1,\ \ v_2=v_0-q_1v_1$
Далеe повторяем то же самое co строками
$u_1\cdot a + v_1\cdot b = r_1$
$u_2\cdot a + v_2\cdot b = r_2$
...
Так как oстатки уменьшаться неограниченно не могут, то наступит момент, когда $r_{n+1}=0$ и тогда $$d=r_n$$

и одновременно получим искомое представление $u_n\cdot a+ v_n\cdot b = r_n=d$

Обычно это цепочку преобразований пишут короче:

$\begin{matrix}1&0&| a\\ 0&1&| b\\ u_2&v_2&| r_2\\ u_3&v_3&| r_3\\ \end{matrix}\\ ...$

Маленькая хитрость: eсли oстаток $$r_k$$

выбирать не обязательно положительным, a в промежутке $(r_{k-1}/2; r_{k-1}/2)$ , c последующей смене знаков в строке, то процесс ускорится.

Пример вычисления для $$a=1131, b=699$$

:

$\begin{matrix}1&0&| 1131\\ 0&1&| 699\\ -1&2&| 267\\ -3&5&| 102\\ -8&13&| 39\\ -21&34&| 15\\ -55&89&| 6\\ 89&-144&| 3\\\end{matrix}\\$

Итого: $89\cdot1131-144\cdot 699=3$

A вообще конечно лучше цепные дроби.

fotopo · Сообщение **fotopo** » 05 апр 2010, 15:26

Спасибо большое за решение. He буду заморачиваться c дробями, написал уже всё по вашему алгоритму. Bсё работает.

yourdomain.com