Остаток от деления (алгоритм RSA)

[limarodessa]

Всем доброго времени суток

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

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

$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)$...

Спасибо

[Deggial]

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

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

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

[Sonic86]

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$

не, это какой-то баг.

limarodessa в сообщении #774100 писал(а):

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

Цитата:

...$\varphi (n)=9167368$...$e=3...(e^{-1}) \mod \varphi(n)$...

Ниасилил, слишком мало буковок
...
Посмотрел статью. Там же есть формула для функции Эйлера: $\varphi(pq)=(p-1)(q-1)$ - по ней и считается. Если Вы это хотели спросить. Если нет это - пишите вопрос нормально.

[limarodessa]

Sonic86 в сообщении #774184 писал(а):

...
Посмотрел статью. Там же есть формула для функции Эйлера: $\varphi(pq)=(p-1)(q-1)$ - по ней и считается. Если Вы это хотели спросить. Если нет это - пишите вопрос нормально.

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

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

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

Цитата:

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

[Sonic86]

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 писал(а):

если как Вы пишите по первой ссылке "баг"

Я такого не писал. Я по ссылке не ходил.