2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



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


16/10/09
160
Всем доброго времени суток

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

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

$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 
Супермодератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Остаток от деления (алгоритм RSA)
Сообщение12.10.2013, 16:38 
Заслуженный участник


08/04/08
8560
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 


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


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

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

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

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

 Профиль  
                  
 
 Re: Остаток от деления (алгоритм RSA)
Сообщение12.10.2013, 17:22 
Заслуженный участник


08/04/08
8560
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