2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Остаток от деления (алгоритм RSA)
Сообщение12.10.2013, 13:18 
Всем доброго времени суток

У меня возникла проблема с пониманием вычисления остатка от деления

Мне, разумеется, совершенно понятно, что, например, :

$10  \mod  7 = 3$

$20  \mod  7 = 6$

ну и т. д.

Но мне в литературе встретились вот такие вычисления:

Цитата:
$k_B = 7 - 1 (\mod 20)$
Решение дает $k_B = 3$

...
$1(\mod 33) = 1$
...


Как это вычисляется ? Я конечно же прежде чем здесь задавать вопрос погуглил и русскоязычный и англоязычный инет но что то не могу найти

Кроме того мне неясно - в формуле они так пишут что вроде бы $7^{-1}$ а когда число подставляют то $7-1$

Вот источник АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ ШИФРОВАНИЯ

И вот это я тоже не могу понять как считается:
RSA

Цитата:
...$\varphi (n)=9167368$...$e=3...(e^{-1}) \mod \varphi(n)$...


Спасибо

 
 
 
 Posted automatically
Сообщение12.10.2013, 15:57 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

limarodessa, наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Код и куски кода можно оформлять тегами code и tt соответственно.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

 
 
 
 Re: Остаток от деления (алгоритм RSA)
Сообщение12.10.2013, 16:38 
limarodessa в сообщении #774100 писал(а):
Но мне в литературе встретились вот такие вычисления:

Цитата:
$k_B = 7 - 1 (\mod 20)$
Решение дает $k_B = 3$
Как-то странно Вы записали.
Видимо, имелось ввиду, что $k_B\equiv 7^{-1}\equiv 3\pmod {20}$, это действительно верно, поскольку $7\cdot 3=21\equiv 1\pmod{20}$.

limarodessa в сообщении #774100 писал(а):
Кроме того мне неясно - в формуле они так пишут что вроде бы $7^{-1}$ а когда число подставляют то $7-1$
:shock: не, это какой-то баг.

limarodessa в сообщении #774100 писал(а):
И вот это я тоже не могу понять как считается:
RSA
Цитата:
...$\varphi (n)=9167368$...$e=3...(e^{-1}) \mod \varphi(n)$...
Ниасилил, слишком мало буковок :-(
...
Посмотрел статью. Там же есть формула для функции Эйлера: $\varphi(pq)=(p-1)(q-1)$ - по ней и считается. Если Вы это хотели спросить. Если нет это - пишите вопрос нормально.

 
 
 
 Re: Остаток от деления (алгоритм RSA)
Сообщение12.10.2013, 17:05 
Sonic86 в сообщении #774184 писал(а):
...
Посмотрел статью. Там же есть формула для функции Эйлера: $\varphi(pq)=(p-1)(q-1)$ - по ней и считается. Если Вы это хотели спросить. Если нет это - пишите вопрос нормально.


Как вычисляется значение по формуле Эйлера мне понятно. Мне неясно как они вычислили "секретную экспоненту": d=6111579

Там ведь все таки не $\equiv $ а $=$ Не может же в двух разных источниках быть "баг"

Кроме того если как Вы пишите по первой ссылке "баг" то как они там вычисляли ? :

Цитата:
...
$1(\mod 33) = 1$
...

 
 
 
 Re: Остаток от деления (алгоритм RSA)
Сообщение12.10.2013, 17:22 
limarodessa в сообщении #774201 писал(а):
Мне неясно как они вычислили "секретную экспоненту": $d=6111579$
А, ну так просто: $d:d\equiv e^{-1}\pmod{\varphi(n)}$, $e,n$ мы знаем. Обратный элемент в кольце вычетов считаем по алгоритму Евклида. Вы не знаете, как считать обратный элемент? Если не знаете, то так:
Сравнение $de\equiv 1\pmod m$ с известными $e,m$ и неизвестным $d$ переписывается в виде уравнения $de-qm=1$ с неизвестными $q,d$ и далее находим его решение с помощью (расширенного) алгоритма Евклида.

limarodessa в сообщении #774201 писал(а):
Там ведь все таки не $\equiv $ а $=$
Это нормально. В теории работа происходит с отношением сравнения $\equiv$, в программах вместо классов вычетов $x+m\mathbb{Z}$ используют представителей $x$ с $0\leqslant x < m$, и тогда одинаковость классов вычетов (или сравнимость элементов классов вычетов) равносильна равенству таких представителей.

(Оффтоп)

limarodessa в сообщении #774201 писал(а):
если как Вы пишите по первой ссылке "баг"
Я такого не писал. Я по ссылке не ходил.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group