С остатком от деления, тем более с остатком от деления яблок, понятно.
А как понять такую запись:

e * d = 1 mod Ф(n)

Остаток от деления 1 на любое число даст 1, если конечно делить не на 1, 
и если Ф(n)  возвращает целое число. 
Тогда зачем так написано, казалось можно сразу записать e * d = 1

У Эйлера целые числа используются или дроби?

источник:
http://ru.wikipedia.org/wiki/%D0%A4%D1%83%...%B5%D1%80%D0%B0


Это сообщение отредактировал(а) Сisa - 19.3.2013, 15:21

заглядываем сюда http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%...%D0%B5%D0%BB%29 и видим что "Частным случаем теоремы Эйлера является малая теорема Ферма (при простом m)"
тогда идем сюда http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%...%80%D0%BC%D0%B0 и читаем формулировку в рамочке

Если p — простое число, и  a  не делится на p, то

a^p-1 = 1 (mod p)

Другими словами,  a^p-1 при делении нацело на p  даёт в остатке 1.

Вот что значит читать, в смысле правильно, то что в формуле записано. 
т.е. тот значок из трех горизонтальных полосок и означает  вот то лишнее что записано справа от 1
Глядя на формулу я и читал так - 

а в степени ( p минус единица ) равно остатку от деления единицы на p.

bems спасибо!   Ключевое слово ==   читаем формулировку , 
оказывается смотреть на формулу как то недостаточно для некоторых  

Теперь начинает вырисовываться начало примера RSA для самых примитивных чисел:
a=5 ;
p=3 ;
степень=5^(3-1) =>>>>    25 ;
25 mod 3 =>>>> 1 ;

И на этом месте обычно оцифрованные примеры и заканчиваются, и дальше формулы, в которых есть и полоски и значки и масса ссылок на теорию. 
Чтобы дальше не сбиться с курса, не найдется ли у Вас терпения довести пример в малых цифрах до победы?

q=3;
p=5;
n=15;
Fi(n)==Fi(p*q)==(p-1)*(q-1)==>8;
d=7;
e=23;
d*e =  1  mod  Fi(n)    ==>1;
m=3;
С=m^e mod n    ==>12;
m=c^d mod n    ==>3;

Примерно так? 
(excel не позволяет сделать вычисления с числами больше выбранных в этом примере)

Значок из трех горизонтальных полосок в математике означает Тождество

В ру.википедии использован знак равно, и в данной задаче он применим, т.к. d и e выбираются случайные числа и уже конкретно для них проверяется равен ли остаток 1, что не тождество. Например мне легче и логичнее  и понятнее было бы прочесть такую запись 
e * d  mod Ф(n) = 1 
a^p-1  (mod p) = 1
Благодаря northener наконец то разобрался с этими остатками. И с тремя полосками 

Еще момент RSA 

- выбираются случайные числа d и e и проверяется равен ли остаток ... 
что не есть хорошо, а нельзя как нибудь по другому, а именно 
-  выбираются случайное число d и вычисляется e ?

Можно ли как то вычислять d или e?


Присоединённый файл ( Кол-во скачиваний: 3 )
 1239402d6e684616ff35d2cd8051c15c.png 0,73 Kb

И снова три полоски ((
Описание:
Абонент B выбрал простые числа q1=7481 и q2=9539,
их произведение rB=71361259,
функцию Эйлера F(rB)=rB(1-1/q1)(1-1/q2)=71344240.
Затем он выбирает случайное число b=74671 и
находит ответ из решения сравнения:
b*β ≡ 1(mod F(rB))=74671*β ≡ 1(mod 71344240), 0<β<F(rB), т.е. β=33289711.
А вот как он это находит? Что на что умножить разделить чтобы β получить ? 
А плюс Б деленное на C понятно, но c Тождествами просто беда, что то не поддаются.

Это сообщение отредактировал(а) Сisa - 2.4.2013, 19:41

Откуда берёшь эти примеры?
Что изучаешь?
Какой хочешь получить результат?

Perl RSA потребовалось, а все примеры что удалось найти только на C++, или с подключаемыми библиотеками и тоже на С. 

Т.е. Математика побоку. Нужен лишь готовый код для программы на Паскале?

в свое время учился по этим книжкам:
http://www.ozon.ru/context/detail/id/1015732/
http://www.ozon.ru/context/detail/id/1510390/
http://www.ozon.ru/context/detail/id/4803047/
Для начала советую первую, а потом можно и за вторую и третью браться. довольно толково написано и воды немного. Это если вам математика нужна. А вообще так - учите дискретку.
По поводу вопроса, что значит a=b mod m?
Значит, что и a и b дают один и тот же остаток при делении на m.

LeonidPr, спасибо!
Математика - придется знания пополнять (или восполнять), и книги конечно потребуются.
С трудом, но начинаю воспринимать что такое есть китайская теорема об остатках, и т.п.,  опять же форма записи математической мысли сбивает с толку, что математику привычно, то новичку стоп.
Дискретка - слово знакомое, но суть его за семью печатями.
Готовый код для программы естественно намного бы ускорил процесс освоения материала, который можно было бы переделывать под свои нужды, сокращать и дополнять, менять схему, протокол.