Что такое mod в математике
Перейти к содержимому

Что такое mod в математике

  • автор:

[математикам]что такое mod?

в методичке по криптографии постоянно встречаются формулы вида этой:

Что такое mod? Простой остаток от деления e^-1 на p-1?

Судя по всему нет, т.к. вот пример из той же методички:

d = e^-1 (mod p-1) = 42239^-1 (mod(52631-1) = 32229

Как это считается?

p.s. Да, математика в институте была >5 лет назад, и она вовсе не мой конек.

Turbid ★★★★★
22.06.09 02:40:55 MSD

а вроде всегда это был остаток от деления. число, не превосходящее делитель.

gunja ★
( 22.06.09 04:12:36 MSD )

если по простому, то это как будто «зацикленное» отнимание. т.е. какое останется число k, если от числа n отнять число m максимум полных раз.
например. 11 mod 3 = 2. число 11 это 3+3+3+2. результат — 2. 61 mod 26 = 9. 61 это 26+26+9.

//читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю

val-amart ★★★★★
( 22.06.09 05:07:04 MSD )

про (mod p-1) уже сказали, но

> d = e^-1 (mod p-1) = 42239^-1 (mod(52631-1) = 32229

либо очепятка, либо ошибка:

a^=b(mod c) если a*b=1(mod c), но у тут

pupok ★★
( 22.06.09 05:22:44 MSD )

кури теорию чисел

irq ★
( 22.06.09 06:03:22 MSD )

Ужас. Закрывай методичку, открывай теорию чисел. А то что будет, когда дискретные логарифмы (ЕМНИП, ГОСТовское шифрование на них основано, но тут могу ошибаться, лет 10 криптографию не трогал) встретишь и т.д.

redgremlin ★★★★★
( 22.06.09 07:07:07 MSD )
Ответ на: комментарий от val-amart 22.06.09 05:07:04 MSD

ОМГ, так это ты подпускаешь людей без знания математики к криптографии?

spunky ★★
( 22.06.09 07:31:05 MSD )
Ответ на: комментарий от val-amart 22.06.09 05:07:04 MSD

> //читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю

Объясните на пальцах БПФ. Не что он делает, а КАК.

Ну мля, я хочу понять, как всё-таки эти формулы с интегралами в циклы расписать чтобы ему на вход массив с PCM, на выходе массив с частотами.

tx
( 22.06.09 08:54:55 MSD )

Здесь либо порядок операций нужно смотреть, либо ограничение представления машинного числа в памяти компа. Положительное integer принимает значения от 0 до 32767. Ну, типа тогда 0-1=32767.

the_mozart
( 22.06.09 08:54:55 MSD )
Ответ на: комментарий от val-amart 22.06.09 05:07:04 MSD

Ну что такое остаток я понимаю, но как его найти в данном примере? Ведь e^ явно меньше чем (p-1)?

p.s. эта формула из «трехподходного протокола Шамира»

Turbid ★★★★★
( 22.06.09 08:55:21 MSD ) автор топика

>Как это считается?

Самое простое объяснение: в методичке опечатка, пропущена какая-то буква перед «-1».

DonkeyHot ★★★★★
( 22.06.09 09:46:58 MSD )

Второе объяснение — вопрос в том, что такое e^-1 в смысле (mod n), и как его вычислить.

DonkeyHot ★★★★★
( 22.06.09 10:06:17 MSD )

Это таки точно опечатка. У меня получается 34229, что слишком похоже на 32229, чтобы быть случайным.

DonkeyHot ★★★★★
( 22.06.09 10:09:53 MSD )
Ответ на: комментарий от DonkeyHot 22.06.09 10:09:53 MSD

Т.е. получается: d = e^ (mod p-1) = 42239^ (mod(52631-1) = 34229

Еще раз, для малограмотных, объясните как взять остаток от деления 42239^ = 2.36748029073e-05 на 52630?

Turbid ★★★★★
( 22.06.09 10:22:07 MSD ) автор топика
Ответ на: комментарий от Turbid 22.06.09 10:22:07 MSD

>как взять остаток от деления 42239^

На самом деле mod(n), означает не остаток от деления(это только метод вычисления) а выполнение операций в соотв. кольце (или какой другой структуре — я основательно позабыл) — в котором не-целых чисел вообще нет, т.ч. e-05 там получить никак нельзя. Т.о. из определения ^-1: A^-1 (mod N) = B, такое, что A * B (mod n) = 1, следует немножко другое число. Как его вычислить и правда не знаю (:for i in range() помог:). Опыт показывает, что это 34229, т.к. *42239 mod (52630) == 1.

Что такое mod в математике

Оператор div и оператор mod

Оператор div и оператор mod

В этой статье речь пойдет о целочисленном делении и делении с остатком.

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

То есть например 20 / 5 = 4, 55 / 6 = 9, 100 / 3 = 33 и т.д.

Согласитесь, что в некоторых случаях это очень удобно и практично. Теперь поговорим о реализации этого метода в Паскале. Тут все достаточно просто, открывать Америку не придется. В паскале за целочисленное деление отвечает оператор div. Теперь как это записывается в Pascal’e

x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — результат целочисленного деления (целочисленное частное)

Таким образом, вот такая запись (55 / 6) нацело = 9 в результате использования оператора div будет выглядеть так

z будет равно 9. Запомните! При использовании оператора div дробная часть будет отброшена!

А сейчас поговорим о делении с остатком. Оно не особо отличается и главным здесь является то, что в результате отбрасывается как раз целая часть. То есть (40 / 6) с остатком = 4, (10 / 3) с остатком =1, (22 /5) с остатком = 2 и т.д. В паскале для этого есть оператор mod. Записывается он точно так же.

x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — остаток

Например (40 / 6) с остатком = 4 с оператором mod будет такой

И как результат получим z=1 .

Кстати оператор mod часто используют, для определения кратности чисел (кратность — это делимость на какое-нибудь число нацело. То есть например говорят, что числа 3, 6, 9, 12, 21 кратны трем. Или числа 5,10,15,20 кратны 5). В статье нахождение четных элементов массива я упоминал о числах кратных двум (четных). Итак как эту кратность определить в паскале. Обратите внимание, что если число кратное, то у него есть остаток (точнее оно имеет в остатке ноль). Этим и стоит воспользоваться.

Сейчас я привел пример условия, которое проверяет кратность, где v — это число, проверяемое на кратность по числу m. Например чтобы проверить,
является ли 40 кратным 4, используем оператор mod с условием и получим

Оператор mod — остаток от деления. Что такое mod?

Оператор mod обозначается символом % и является оператором деления по модулю. Он возвращает остаток от деления 1-го операнда на 2-й и широко используется в разных языках программирования для решения ряда задач.

Оператор mod в Java

В Java operator mod может работать как с целыми числами (byte/int/short/long), так и с плавающей точкой (byte/int/short/long). Давайте приведём пример работы оператора mod при делении:

 
class Modulus  public static void main (String args [])  int x = 42; double у = 42.3; System.out.print("x mod 10 = " + x % 10); System.out.println("y mod 10 = " + у % 10); > > 

После выполнения этой программы вы получите результат следующего вида:

 
х mod 10 = 2 у mod 10 = 2.3

Как видим, оператор mod — это прекрасный способ найти остаток от деления. Зачем это может понадобиться на практике? Например, при нахождении кратности числа и определении, является ли некоторое число, введённое с клавиатуры, чётным. Также с помощью оператора mod можно узнать, делится ли одно число на другое без остатка или определить последнюю цифру числа. В общем, оператор mod очень полезен при решении различных задач по программированию.

Оператор mod в SQL

Не менее интересно использование mod в базах данных. Аналогично, mod находит остаток от деления. При этом вместо mod можно задействовать операцию %, делающую то же самое. Синтаксис в SQL следующий:

 
SELECT MOD(что_делить, на_что_делить) FROM имя_таблицы WHERE условие

Но можно написать и иначе, используя % :

 
SELECT что_делить % на_что_делить FROM имя_таблицы WHERE условие

Давайте приведём пример использования mod в базах данных. Вот, например, таблица numbers:

1-20219-4b024d.jpg

Найдём остаток от деления столбца number на три:

 
SELECT *, MOD(number, 3) as mod FROM numbers

В результате запрос SQL выберет следующие строки:

2-20219-a72b72.jpg

Но, как мы уже говорили выше, этот же запрос можно без проблем переписать:

 
SELECT id, number % 3 as mod FROM numbers

Идём дальше. Теперь возьмём таблицу посложнее:

3-20219-15db22.jpg

Здесь найдём остаток от деления столбца number1 на number2:

 
SELECT *, MOD(number1, number2) as mod FROM numbers

Получим следующие строки:

4-20219-3e08f5.jpg

Опять же, этот же самый запрос можно оформить иначе:

 
SELECT *, number1 % number2 as mod FROM numbers

А где вы используете mod? Пишите в комментариях!

Mod и остаток — не одно и то же

Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!

Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре RSA для SSH, который, очевидно, является самым загружаемым фрагментом кода в истории IT.

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

В любом случае: на прошлой неделе я узнал что-то странное и хочу поделиться: оказывается, mod и остаток от деления — не одно и то же. Действительно забавно то, что некоторые читатели при этих словах выпрыгивают со своих кресел и орут: «А ведь именно это я всегда пытался сказать вам и всем остальным!»

Позовите ребят из секты «mod не остаток»! Это для вас.

Что такое mod?

Я должен был изучить это, как и в прошлый раз, когда всплыла такая тема. Это одна из тех вещей, которые ты знаешь, но не запоминаешь. Когда вы применяете mod, то делите одно число на другое и берёте остаток. Итак: 5 mod 2 будет 1, потому что 5/2=2 с остатком 1.

Термин mod означает операцию modulo, с модулем 2 в данном случае. Большинство языков программирования используют % для обозначения такой операции: 5 % 2 = 1 .

Вот где мы попадаем в странную серую область.

Математика циферблата

Помню, как учил это в школе, а потом забыл. Существует тип математики, называемый «модульной арифметикой», которая имеет дело с циклическими структурами. Самый простой способ представить это — циферблат с циклом 12. Для математика циферблат — это mod 12 . Если хотите понять, можно ли равномерно разделить 253 часа на дни, то можете применить операцию 253 mod 24 , результатом будет 13, поэтому ответ «нет»! Мы можем ответить «да» только если результат 0.

Другой вопрос, который вы можете задать: «Если я выеду в 6 вечера, сколько времени будет по приезду через 16 часов?». Это будет 6 + 16 mod 12 , то есть 10.

Криптографы любят mod , потому что при использовании с действительно большими числами можно создать нечто, известное как «односторонние функции». Это специальные функции, которые позволяют легко вычислить что-то в одном направлении, но не в обратном.

Если я скажу вам, что 9 является результатом возведения в квадрат, вы можете легко определить, что на входе было 3. Перед вами весь процесс от начала до конца. Если я скажу, что 9 является результатом mod 29 , то будет сложнее понять, что на входе.

Криптографам нравится эта идея, потому что они могут использовать деление с остатком с гигантскими простыми числами для генерации криптографических ключей. Это совсем другая история: если хотите прочитать об этом, то можете купить книгу или, ещё лучше, поддержать мои усилия написать её.

Впрочем, не будем отклоняться от темы.

Остатки и математика циферблата

Теперь переходим к сути: modulo и простой остаток одинаковы, когда числа положительны, но отличаются в случае отрицательных чисел.

Рассмотрим такую задачу:

const x = 19 % 12; console.log(x);

Каково значение x ? Делим числа и получаем 7 как остаток от 12. Это верный ответ. Как насчет такого:

const y = 19 % -12; console.log(y);

Используя обычную математику, мы можем умножить -12 на -1, что даёт 12, и у нас по-прежнему остаётся 7, поэтому наш ответ снова 7.

JavaScript с этим согласен:

C# тоже согласен:

Google согласен с первым утверждением, но не согласен со вторым:

Ruby согласен с Google:

Во имя Дейкстры, что здесь происходит?

Вращение часов назад

Чтобы ответить на вопрос, следует понять разницу между остатком и modulo. Программисты объединяют эти операции, но не должны этого делать, потому что они дают одинаковый результат только в случае, если делитель (в нашем случае 12) положителен. Вы можете легко отправить баги в продакшн, если делитель отрицательный.

Но почему существует разница? Рассмотрим положительный делитель 19 mod 12 на часах:

Конечный результат 7. Мы это знаем и мы можем доказать математически. Но что насчёт 19 mod -12 ? Здесь нужно использовать другие часы:

Модуль равен -12, и мы не можем игнорировать или изменить его, умножив на -1, поскольку модульная арифметика так не работает. Единственный способ правильно рассчитать результат — переставить метки на часах так, чтобы мы двигались от -12 или вращали часы против часовой стрелки, что даёт тот же результат.

Почему не начать метки с -1, двигаясь к -2, и т.д.? Потому что в таком случае мы будем двигаться назад и постоянно уменьшать результат, пока не достигнем -12, и в этот момент сделаем прыжок +12, а modulo так не работает.

Это известная вещь

Прежде чем назвать меня сумасшедшим и начать гуглить тему: это известный факт. На самом деле MDN (Mozilla Developer Network) даже дошла до того, чтобы назвать % операцией «остатка» (remainder), а не modulo:

Оператор remainder возвращает остаток от деления одного операнда на другой. Он всегда принимает знак делимого.

Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:

Однако это совсем не то, что оператор % реально делает в C#. Оператор % не является каноническим оператором modulus, это оператор остатка.

А как на вашем языке?

Ну и что?

Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:

  1. Я представляю, как этот вопрос займёт меня врасплох на собеседовании.
  2. Я представляю, как этот попадёт в продакшн, а разработчики будут несколько часов выяснять, почему математика не работает.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *