Что такое mod в алгебре

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

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

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

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

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

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

Что такое mod?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ну и что?

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

Источник

Модуль числа

Определение модуля числа

Алгебра дает четкое определение модуля числа. Модуль числа в математике — это расстояние от начала отсчёта до точки координатной прямой, соответствующей этому числу.

Если мы возьмем некоторое число «a» и изобразим его на координатной прямой точкой A — расстояние от точки A до начала отсчёта (то есть до нуля) длина отрезка OA будет называться модулем числа «a».

Знак модуля: |a| = OA.

Разберем на примере:

Точка В, которая соответствует числу −3, находится на расстоянии 3 единичных отрезков от точки O (то есть от начала отсчёта). Значит, длина отрезка OB равна 3 единицам.

Число 3 (длину отрезка OB) называют модулем числа −3.

Обозначение модуля: |−3| = 3 (читают: «модуль числа минус три равен трём»).

Точка С, которая соответствует числу +4, находится на расстоянии четырех единичных отрезков от начала отсчёта, то есть длина отрезка OС равна четырем единицам.

Число 4 называют модулем числа +4 и обозначают так: |+4| = 4.

Также можно опустить плюс и записать значение, как |4| = 4.

Онлайн-курсы математики для детей помогут подтянуть оценки, подготовиться к контрольным, ВПР и экзаменам.

Свойства модуля числа

Давайте рассмотрим семь основных свойств модуля. Независимо от того, в какой класс перешел ребенок — эти правила пригодятся всегда.

1. Модуль числа — это расстояние, а расстояние не может быть отрицательным. Поэтому и модуль числа не бывает отрицательным:

2. Модуль положительного числа равен самому числу.

3. Модуль отрицательного числа равен противоположному числу.

4. Модуль нуля равен нулю.

5. Противоположные числа имеют равные модули.

6. Модуль произведения равен произведению модулей этих чисел.

Геометрическая интерпретация модуля

Как мы уже знаем, модуль числа — это расстояние от нуля до данного числа. То есть расстояние от точки −5 до нуля равно 5.

Нарисуем числовую прямую и отобразим это на ней.

Эта геометрическая интерпретация используется для решения уравнений и неравенств с модулем. Давайте рассмотрим на примерах.

Решим уравнение: |х| = 5.

Мы видим, что на числовой прямой есть две точки, расстояние от которых до нуля равно 5. Это точки 5 и −5. Значит, уравнение имеет два решения: x = 5 и x = −5.

Решим неравенство: |a + 7|

График функции

График функции равен y = |х|.

Для x > 0 имеем y = x.

Этот график можно использовать при решении уравнений и неравенств.

Корень из квадрата

Оно равно a при а > 0 и −а, при а

Модуль рационального числа

Как найти модуль рационального числа — это расстояние от начала отсчёта до точки координатной прямой, которая соответствует этому числу.

Источник

СОДЕРЖАНИЕ

Конгруэнтность

Отношение конгруэнтности можно переписать как

Примеры

По модулю 12 можно утверждать, что:

Определение конгруэнтности также применимо к отрицательным значениям. Например:

Характеристики

Отношение конгруэнтности удовлетворяет всем условиям отношения эквивалентности :

Для отмены общих условий у нас действуют следующие правила:

Некоторые из наиболее продвинутых свойств отношений конгруэнтности следующие:

Классы конгруэнтности

Системы остатков

Вот некоторые наборы, которые не являются полными системами вычетов по модулю 4:

Системы с пониженным остатком

Целые числа по модулю n

Набор определяется для n > 0 как:

Для проверки правильности этого определения используются свойства, приведенные ранее.

12 ¯ 24 + 21 год ¯ 24 знак равно 33 ¯ 24 знак равно 9 ¯ 24 <\ displaystyle <\ overline <12>> _ <24>+ <\ overline <21>> _ <24>= <\ overline <33>> _ <24>= <\ overline <9>> _ <24>>

как в арифметике для 24-часовых часов.

Приложения

Метод исключения девяток предлагает быструю проверку десятичных арифметических вычислений, выполняемых вручную. Он основан на модульной арифметике по модулю 9 и, в частности, на ключевом свойстве 10 ≡ 1 (mod 9).

Арифметика по модулю 7 используется в алгоритмах, определяющих день недели для заданной даты. В частности, сравнение Зеллера и алгоритм Судного дня широко используют арифметику по модулю 7.

Вычислительная сложность

Примеры реализации

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

Алгоритмический способ вычисления : а ⋅ б ( мод м ) <\ displaystyle a \ cdot b <\ pmod >>

На компьютерных архитектурах, где доступен формат расширенной точности с не менее 64 битами мантиссы (например, тип long double большинства компиляторов C x86), следующая процедура заключается в использовании уловки, которая аппаратно дает результаты умножения с плавающей запятой в наиболее значимых битах продукта, в то время как целочисленное умножение приводит к сохранению наименее значимых битов:

Однако для того, чтобы все вышеперечисленные подпрограммы работали, m не должно превышать 63 бит.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Спасибо, тогда тоже пока напишу скрипт, пусть ищет.

Источник

Введение в модулярную арифметику

Для любой системы взаимно простых чисел p₁, … p_n, любое число X из диапазона [0; M), где M = p₁*p₂*…*p_n взаимооднозначно представимо в виде вектора (a₁, a₂, …, a_n), где a_i = X%p_i (здесь и далее «%» — операция взятия остатка от целочисленного деления X на p_i).
p₁, … p_n – модули системы
a₁, a₂, …, a_n – остатки (вычеты) числа по заданной системе модулей

Прямое преобразование

Прямое преобразование из позиционной системы счисления (обычно в двоичном виде) в систему счисления в остатках заключается в нахождении остатков от деления по каждому из модулей системы.

Пример: Пусть требуется найти представление числа X = 25 по системе модулей (3, 5, 7). X = (25%3, 25%5, 25%7) = (1, 0, 4).

Реализация нахождения вычета в микроэлектронике по заданному модулю строится на следующих свойствах вычетов:
(a+b) % p = (a%p + b%p)%p
(a*b) % p = (a%p * b%p)%p

Любое число X можно записать в виде X%p = (x_n-1*2 n-1 + x_n-2*2 n-2 + x₀*2 0 )%p = ((x_n-1)%p*2 n-1 %p) + ((x_n-2)%p*2 n-2 %p) + … + x₀%p)%p. Поскольку в данном случае x_n-1, … x₀ равны 0 или 1, то фактически нам требуется сложить вычеты вида (2 i %p).

Пример: пусть задано число 25 или в двоичной системе счисления 11001 и требуется найти остаток по модулю 7.
25%7 = (1*2 4 + 1*2 3 + 0*2 2 + 0* 1 + 1*2 0 )%7 = (2 4 %7 + 2 3 %7 + 1%7)%7 = (2 + 1 + 1)%7 = 4

Арифметические операции

Пример: пусть задана система модулей (3, 5, 7), то есть мы можем выполнять операции, результат которых не превышает 3*5*7 = 105. Умножим два числа 8 и 10.
8 = (8%3, 8%5, 8%7) = (2, 3, 1)
10 = (10%3, 10%5, 10%7) = (1, 0, 3)
8*10 = ((2*1)%3, (3*0)%5, (1*3)%7) = (2, 0, 3)
Проверяем
80 = (80%3, 80%5, 80%7) = (2, 0, 3)

Обратное преобразование

Способ, основанный на Китайской теореме об остатках, базируется на следующей идее:
X = (x₁, x₂, … x_n) = (x₁, 0, …, 0) + (0, x₂, …, 0) + … + (0, 0, …., x_n) = x₁*(1, 0, …, 0) + x₂*(0, 1, …, 0) + … + x_n*(0, 0, …, 1).
То есть для обратного преобразования требуется найти систему ортогональных базисов B1 = (1, 0, …, 0), B2 = (0, 1, …, 0), …, BN = (0, 0, …, 1). Эти вектора находятся один раз для заданного базиса, а для их поиска требуется решить уравнение вида: (M_i*b_i)%p_i = 1, где M_i = M/p_i, а b_i – искомое число. В этом случае позиционное представление B_i = M_i*b_i и
X = (x₁*(M₁*b₁) + x₂*(M₂*b₂) + … + x_n*(M_n*b_n))%M

Пример: пусть задана система модулей (3, 5, 7), найдем значения M_i и b_i (0 b₁ = 2
(21*b₂)%5 = 1 => b₂ = 1
(15*b₃)%7 = 1 => b₃ = 1
Теперь преобразуем какое-нибудь число в системе остаточных классов. Положим
X = (2, 3, 1) = (2*35*2 + 3*21*1 + 1*15*1)%105 = (140 + 63 + 15)%105 = 218%105 = 8

Минус этого метода заключается в том, что для обратного преобразования требуется умножение и сложение больших чисел (M₁, …, M_n), а так же операция взятия остатка по модулю большого числа M.

Источник