Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Для новичков > 1 mod 2 =1????

Автор: JustInTime 27.11.2007, 17:29

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

Автор: Snowy 27.11.2007, 17:37

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

Автор: JustInTime 27.11.2007, 17:56

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

Автор: Lexicss 27.11.2007, 17:59

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

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

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

Автор: JustInTime 27.11.2007, 18:28

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

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

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

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

Автор: Lexicss 27.11.2007, 21:14

Цитата(JustInTime @ 27.11.2007, 18:28)

Если 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 ?

Автор: Imple 27.11.2007, 21:19

JustInTime, не так.

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

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

Автор: Snowy 27.11.2007, 21:23

Переведу в дельфи код.
Операцию mod можно представить, как

Код

result := x - x div a * a;

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

Автор: Lexicss 27.11.2007, 21:35

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

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

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

Автор: JustInTime 28.11.2007, 17:15

2 Lexicss,Snowy,Imple

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

Автор: PsiMagistr 13.6.2010, 09:05

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

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

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

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

Автор: bems 13.6.2010, 09:09

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

Автор: PsiMagistr 13.6.2010, 09:25

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

Автор: bems 13.6.2010, 10:49

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

Автор: PsiMagistr 13.6.2010, 11:03

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

Автор: Сisa 19.3.2013, 15:05

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

e * d = 1 mod Ф(n)

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

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

источник:
http://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0

Автор: bems 19.3.2013, 21:20

Цитата(Сisa @ 19.3.2013, 15:05

)

e * d = 1 mod Ф(n)

заглядываем сюда http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%B5%D0%BB%29 и видим что "Частным случаем теоремы Эйлера является малая теорема Ферма (при простом m)"
тогда идем сюда http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D0%BB%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0 и читаем формулировку в рамочке

Автор: Сisa 19.3.2013, 22:30

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

a^p-1 = 1 (mod p)

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

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

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

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

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

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

Автор: Сisa 19.3.2013, 23:53

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 не позволяет сделать вычисления с числами больше выбранных в этом примере)

Автор: northener 20.3.2013, 00:10

Цитата(Сisa @ 19.3.2013, 22:30

)

т.е. тот значок из трех горизонтальных полосок и означает вот то лишнее что записано справа от 1

Значок из трех горизонтальных полосок в математике означает http://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D0%B6%D0%B4%D0%B5%D1%81%D1%82%D0%B2%D0%BE_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%29

Автор: Сisa 20.3.2013, 10:06

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

Еще момент RSA

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

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

Автор: Сisa 2.4.2013, 19:29

И снова три полоски ((
Описание:
Абонент 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 Тождествами просто беда, что то не поддаются.

Автор: northener 3.4.2013, 01:35

Цитата(Сisa @ 2.4.2013, 19:29

)

И снова три полоски ((

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

Автор: Сisa 3.4.2013, 10:21

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

Автор: northener 4.4.2013, 02:24

Цитата(Сisa @ 3.4.2013, 10:21

)

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

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

Автор: LeonidPr 4.4.2013, 07:16

в свое время учился по этим книжкам:
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.

Автор: Сisa 4.4.2013, 13:07

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