Что значит сложение по модулю

Сложение по модулю

Важной операцией в информатике является сложение по модулю. Это операция арифметического сложения, при котором единица переноса в старший разряд, если таковая образуется при поразрядном сложении, отбрасывается. Обычно при выполнении этой операции конкретизируют, о каком модуле идет речь, например, по модулю 10, или по модулю 2, или по модулю 16. Обозначается эта операция ⊕.

Таблица сложения двоичных чисел по модулю 2 приведена ниже (обозначения строк и столбцов соответствуют слагаемым):

Пример 7. Сложить по модулю 2 двоичные числа 10 и 11.

Сложение выполним поразрядно:

1) разряд единиц: 0⊕1 = 1;

2) разряд десятков: 1⊕1 = 0.

Таким образом, 10₂⊕11₂ = 01₂. Чтобы подчеркнуть, что в сложении участвовали двухразрядные слагаемые, в результате оставляются обе цифры.

Таблица сложения десятичных чисел по модулю 10 приведена ниже (обозначения строк и столбцов соответствуют слагаемым):

Пример 8. Сложить по модулю 10 десятичные числа 59 и 152.

Источник

Сложение по модулю 2, что это такое?

).
То есть имеем два бинарных числа, например 1010 и 101. Сложим их по модулю два:
1010 XOR 101 = 1111

То есть согласно этому определению, нужно сложить 1010 и 101 и разделить их по модулю на 2. Понятное дело, что результатом будет 1, а никак не 1111

Так как же всё-таки сложить два числа по модулю 2? Спасибо, ко откликнется. Garry Galler не беспокоиться.

Что такое монитор и что такое мьютекс? Это же разные вещи?
Здравствуйте. В разных айти-статьях по-разному используют эти термины, причём часто их путают друг.

Как такое может быть и что это такое?
в маленьком превью одна картинка, открываешь совершенно другая (какая и должна быть) с чем это.

Что это такое и как это создается?
Здравствуйте! Как создать эти жирные ссылки, показанные на картинке?

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

Добавлено через 2 минуты
Кстати, для поразрядного сложения операнды правильнее записывать с одинаковой длиной, то есть

ну и плюсик в кружок помещают, как в этой формуле. Но это не обязательно.

Не знаю, меня вроде так всю жизнь учили:

1 \oplus 1 = 0;
0 \oplus 1 = 1;
1 \oplus 0 = 1;» />

других операций по модулю 2 я не знаю

Добавлено через 1 час 9 минут

Источник

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

Для любой системы взаимно простых чисел 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.

Источник

Сложение по модулю 2

Сложе́ние по модулю 2 («сумма по модулю 2», «не равно», исключа́ющее «ИЛИ» (ИЛИ с исключением из правила четвёртой комбинации «1,1»), XOR,) — ло­ги­чес­кая опе­ра­ция (функция), по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жён­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …» или «если операнды не равны, то истинно (1)».

a \oplus b, a \oplus_2 b, a +_2 b, a ≠ b, a\ne b, (a,b)\oplus_2, a

Содержание

Булева алгебра

\ <0, 1\>. Результат также принадлежит множеству

\ <0, 1\>. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений

0, 1 может использоваться любая другая пара подходящих символов, например

F, T или «ложь», «истина».

Таблицы истинности:
для бинарного сложения по модулю 2
Правило (только для бинарного сложения по модулю 2): результат равен

для тернарного сложения по модулю 2

Программирование

00101001_2тоa ^ b =

Выполнение операции XOR для значений логического типа (true, false) производится в разных языках программирования по-разному. Например в Delphi используется встроенный оператор XOR (пример: condition1 xor condition2). В языке C, начиная со стандарта C99, оператор «^» над операндами логического типа возвращает результат применения операции XOR. В С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение. Перегрузка для стандартных типов невозможна, но операцию XOR над ними можно реализовать, исходя из принципа «исключающего ИЛИ». Выглядит это так:

(при этом нет разницы, применяются ли побитовые операторы & и |, или же логические && и ||)

Связь с естественным языком

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:

Операция \oplus исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция \lor включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

См. также

Источник

Операции по модулю

Математические термины

Во всём последующем материале никак не фигурирует понятие “модуль числа” в привычном смысле (\(\lvert x \rvert\)). Речь идёт о “сравнении по модулю”. Если вы не знакомы с этим понятием, вкратце сравнение по модулю выглядит следующим образом:

Это читается “\(a\) сравнимо с \(b\) по модулю \(m\)”, и в привычных для информатики терминах обозначает следующее:

\[a \bmod m = b \bmod m,\]

Поле по модулю

Можно сказать, что в таких задачах мы оперируем не числами, а их остатками от деления на 1000000007. Это возможно благодаря следующим свойствам вычислений с остатком:

Доказательство возможности сложения, вычитания и умножения по модулю

Для начала докажем достаточно очевидное утверждение:

\[\forall n \in \mathbb: x \bmod m = (x + nm) \bmod m.\]

Значит, по определению сравнимости, \(\forall n \in \mathbb: x \equiv x + nm \pmod\), что и требовалось доказать.

\[(a + b) \bmod m = \\ = (xm + a \bmod m + ym + b \bmod m) \bmod m = \\ = (a \bmod m + b \bmod m + m(x + y)) \bmod m, = \\ = (a \bmod m + b \bmod m) \bmod m,\]

что и требовалось доказать.

Вычитание и умножение доказываются похожим образом:

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

В качестве примера, вычислим значение \(10^8!\) по модулю \(10^9 + 7\):

Как видите, на практике вычисления в поле по модулю отличаются от обычных лишь наличием взятия всех промежуточных результатов по модулю (строка 8). Однако существует два момента, которые нужно всегда учитывать для избежания ошибок:

Возведение в степень по модулю. Бинарное возведение в степень

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

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

Таким образом засчёт одной операции умножения можно уменьшить степень вдвое. Если же текущая степень нечётная, то можно просто уменьшить её на единицу простым умножением, и получить чётную.

Простой рекурсивный вариант на C++:

Можно заметить, что в худшем случае на каждом втором вызове функции степень будет уменьшаться вдвое. Значит, время работы алгоритма можно оценить как \(O(\log p)\).

Разумеется, бинарное возведение в степень можно использовать и без модуля, но степени в таких случаях слишком малы, чтобы заметить разницу в скорости.

Деление в поле по модулю

К сожалению, деление не так легко адаптируется к полю по модулю, как другие арифметические операции. В этом разделе описывается один из способов деления по модулю, но не приводится его доказательство, так как оно значительно усложнило бы эту лекцию.

Деление по модулю определяется через умножение следующим образом:

Ключевую роль играет значение \(b^<-1>\), называющееся обратный элемент в поле по модулю. Оно никак не связано с классическим понятием обратного числа, хотя бы тем, что всегда является целым (так как в поле по модулю существуют только целые числа). Для обратного элемента должно выполняться следующее условие:

Например, обратным элементов в поле по модулю \(1000000007\) для числа \(2\) является число \(500000004\), так как \((2 * 500000004) \bmod 1000000007 = 1\). Следовательно, в поле по модулю \(1000000007\) делению на \(2\) соответствует умножение на \(500000004\)

Алгоритм нахождения обратного элемента в поле по простому модулю достаточно прост (в реализации) и выражается следующей формулой:

Как можно заметить, число \(x\) возводится в достаточно большую степень, и линейный алгоритм в этой ситуации не подойдёт. Вот и пример необходимости использования бинарного возведения в степень по модулю.

Стоит заметить что из-за использования бинарного возведения в степень, деление по модулю имеет сложность \(O(\log m)\), тогда как все остальные арифметические операции по модулю работают за \(O(1)\).

Источник