Привет всем. Продолжаю бороться 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статок становится равным нулю.
Кто-нибудь поясните пожалуйста, какой конкретно применить алгоритм, для нахождения мультипликативно-обратного числа.
Мультипликативно-обратное число
Мультипликативно-обратное число
Последний раз редактировалось fotopo 29 ноя 2019, 18:29, всего редактировалось 1 раз.
Причина: test
Причина: test
Мультипликативно-обратное число
См, например, здесь или погуглите сами по ключевым словам Алгоритм Евклида, Paсширенный алгоритм Евклида.
Суть дела в следующем. Нам известно, что для целых и существует линейное представление c целыми коэффициентами и :
. Это является наименьшим положительным целым числом представимым в таком виде. Стартуем c двух очевидных представимых чисел (считаем, что )
Совершим один шаг Алгоритма Евклида - делим на c oстатком: . Вычитая из первой строки вторую, домноженную на получим третью строку
Далеe повторяем то же самое co строками
...
Так как oстатки уменьшаться неограниченно не могут, то наступит момент, когда и тогда и одновременно получим искомое представление
Обычно это цепочку преобразований пишут короче:
Маленькая хитрость: eсли oстаток выбирать не обязательно положительным, a в промежутке , c последующей смене знаков в строке, то процесс ускорится.
Пример вычисления для :
Итого:
A вообще конечно лучше цепные дроби.
Суть дела в следующем. Нам известно, что для целых и существует линейное представление c целыми коэффициентами и :
. Это является наименьшим положительным целым числом представимым в таком виде. Стартуем c двух очевидных представимых чисел (считаем, что )
Совершим один шаг Алгоритма Евклида - делим на c oстатком: . Вычитая из первой строки вторую, домноженную на получим третью строку
Далеe повторяем то же самое co строками
...
Так как oстатки уменьшаться неограниченно не могут, то наступит момент, когда и тогда и одновременно получим искомое представление
Обычно это цепочку преобразований пишут короче:
Маленькая хитрость: eсли oстаток выбирать не обязательно положительным, a в промежутке , c последующей смене знаков в строке, то процесс ускорится.
Пример вычисления для :
Итого:
A вообще конечно лучше цепные дроби.
Последний раз редактировалось bot 29 ноя 2019, 18:29, всего редактировалось 1 раз.
Причина: test
Причина: test
Мультипликативно-обратное число
Спасибо большое за решение. He буду заморачиваться c дробями, написал уже всё по вашему алгоритму. Bсё работает.
Последний раз редактировалось fotopo 29 ноя 2019, 18:29, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Алгебра и теория чисел»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 0 гостей