1 mod 2=1 
ПОчему,,,? Не могу понять........

Это математика.
Остаток от деления на 2 какой?
Возьми учебник по математике для средней школы, повтори...

2 Snowy
Остаток равен 0,5 ? Так или нет?

Ещё для более лучше запоминания могу объяснить для этого частого случая так :
если дано выражение  x mod 2
то оно будет равно 1 тогда и только тогда, когда x - нечётно,
и  равно 0, если x - чётно.

И напомню, что выражение mod возвращает остаток от деления, а не само частное. 
А частное из этого выражения как раз таки будет равно 0.

Добавлено через 2 минуты и 22 секунды
JustInTime, парень, ты уже конкретно запутался. Остаток  -  это всегда целое число.
такое выражение как "x mod y " всегда вернёт остаток в пределах от [0 .. y-1].

2 Lexicss 
Вы правы, запутался я конкретно... 

Но вот смотрите. К примеру

2 mod 5=2
3 mod 5=3
4 mod 5=4

Представим формулу(x mod y)
Если х<y то на выходе будет х
Если x>=y то  на выходе будет 1 или 0

 

Вот это утверждение уже не верно. 
возвращать это выражение будет 1 или 0 только тогда когда y = 2, т.е. [0 .. y-1]

Остаток будет всегда нулевым, если выражение делится нацело, например 6 mod 3, 10 mod 2,  24 mod 3
Если же нацело не делится, то тогда остаток ненулевой. 
Вот полный пример, я думаю что станет понятнее:
x div y = a      //целочисленное деление с остатком
x mod y = b   //взятие остатка от деления (или деление по модулю)

из этой системы уравнений справедливо равенство: x = y*a + b
Частный случай: пускай x = 25, y = 4
тогда имеем
25 div 4 = 6
25 mod 4 = 1

в итоге получаем справедливое равенство: 25 = 4*6 + 1

Надеюсь, это хоть понятно почему 25 div 4 = 6 ?

JustInTime, не так.

Происходит целочисленное деление, остаток от которого возвращает оператор mod.

К примеру:
4 mod 2, результат деления 2, остаток 0
11 mod 3, результат деления 3, остаток 2
17 mod 5, результат 3 остаток 2
1 mod 2, результат 0 остаток 1

Переведу в дельфи код.
Операцию mod можно представить, какгде х - число, а - модуль.
То есть mod возрачает то, что было отброшено при делении div-ом.
То есть 13 div 5 = 2.
То есть 10 разделилось, остальное целоцисленно не делится - выкинули.
А что выкинули? Правильно - 3.
Вот 3 это и есть остаток от деления.
15 div 5 = 3
Разделилось полностью. Остатка нет.
16 div 5 = 3
15 разделилось, а остаток - 1. 

Можно ещё вот так на пальцах объяснить, доходчевее придумать, уже и не знаю как.

Нас 4 человека и у нас есть 25 яблок. Нам надо поделить по-ровну между собой эти яблоки, при условии что разрезать эти яблоки нельзя. В итоге каждый из нас получит по 6 яблок(25 div 4 = 6), однако 6*4 = 24, т.е. раздав каждому из 25-ти яблок по 6 у нас 1 яблоко осталось лишним(25 mod 4 = 1).

Вот эта описанная ситуация с яблоками и объясняет принцип целочисленного деления и остаток от него.

2 Lexicss,Snowy,Imple

Спасибо Вам огромное. Теперь все ясно.
Объяснили лучше чем в учебниках!!!.

Вопрос конечно интересный, но...

Что возвращает mod при делении меньшего числа на большее?

5 mod 3 = 2 в остатке. Здесь все правильно.

3 mod 5 а так? Мне возвращает 3, но почему не могу понять.


Это сообщение отредактировал(а) PsiMagistr - 13.6.2010, 09:06

потому что 0 раз по 5 и 3 в остатке

bems, хм, довольно забавно. Всегда полагал что при делении меньшего на большее остаток вообще не образуется. Ведь остаток это то, что не разделилось.

ну так и есть. В данном случае вообще ничего не разделилось

Спасибо, bems. Я тут откопал математическую модель шифратора Цезаря, где этот самый mod используют. Так что перепишу под него проектик и поставю сюда к нам. 

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

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