Что значит вычет по модулю

Арифметика сравнений [ править ]

Свойства сравнений [ править ]

• 1. Два числа, сравнимые с третьим сравнимы между собой. [math]a \equiv c(mod \text< >m) \text <, >b \equiv c(mod \text< >m) \Rightarrow a \equiv b(mod \text< >m)[/math]
  • Легко выводится из пункта «а».

• 2. Сравнения можно почленно складывать. [math] a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text< >m)[/math]
  • Представляем сравнения, как в пункте «а» и складываем.

• 3. Сравнения можно почленно перемножать. [math] a_1a_2a_3 \equiv b_1b_2b_3(mod \text< >m)[/math]
  • Представляем сравнения, как в пункте «а», перемножаем, получим [math] a_1a_2a_3 = b_1b_2b_3+mN[/math] , где N—целое.

• 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
  • Действительно, из [math]a \equiv b(mod \text < >m)[/math] , [math] a = a_1d, b = b_1d, (d,m)=1[/math] следует, что [math] a-b = (a_1 — b_1)d \vdots m [/math] , поэтому [math] a_1 \equiv b_1(mod \text < >m)[/math] .

• 5. Обе части сравнения можно умножить на одно и тоже число.
  • Действительно, из [math]a \equiv b(mod \text < >m)[/math] , следует [math] a = b+mt, ak =bk +mkt [/math] , и, следовательно, [math]ak \equiv bk(mod \text < >mk)[/math] .

• 6. Обе части сравнения и модуль можно разделить на их общий делитель.
  • Действительно, пусть [math]a \equiv b(mod \text < >m), a = a_1d, b=b_1d, m=m_1d[/math] , отсюда [math] a= b+mt, a_1d =b_1d +m_1dt, a_1 =b_1 +m_1t[/math] , и, следовательно, [math]a_1 \equiv b_1(mod \text < >m_1)[/math] .

• 7. Если сравнение [math]a\equiv b[/math] имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
  • В самом деле, из [math] a \equiv b(mod \text< >m_1),\ldots,a \equiv b(mod \text< >m_k)[/math] следует, что разность [math] a-b [/math] делится на все модули [math] m_1,m_2,\ldots,m_k[/math] . Поэтому она должна делиться и на их НОК.

• 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
  • Следует из пункта «б».

• 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
  • Следует из пункта «а».

• 10. Если [math]a \equiv b(mod \text< >m) [/math] , то [math](a,m) = (b,m) [/math] .
  • Следует из пункта «а» по свойству НОДа.

Полная и приведенная система вычетов [ править ]

Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса, если в форме [math]mt + r [/math] заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.

Любое число класса называется вычетом по модулю m. Вычет получаемый при [math] t = 0[/math] , равный самому остатку r, называется наименьшим неотрицательным вычетом.

Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.

Решение линейных систем по модулю [ править ]

Примеры решения [ править ]

Пример 1.
[math] 12x \equiv 6(mod \text< >18)[/math]
Найдем НОД [math](12,18)=6 [/math]
Перейдем к новому сравнению [math] 2x \equiv 1(3) [/math]
Легко находится [math] x_0 = 2 [/math]
Тогда ответом будет [math] x_0 =2, x_1 = x_0 — \frac<(a,m)>=-1, x_2 = -4[/math]

Пример 2.
[math] 111x \equiv 75(mod \text< >321)[/math]
Найдем НОД [math](111,321)=3 [/math] , 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению [math] 37x \equiv 25(107) [/math]
Воспользуемся цепными дробями, в нашем случае [math] n=4, p_ = 26[/math] , значит [math] x_0 \equiv -26\cdot 25 (107) \equiv 99(107) [/math]
Тогда ответом будет [math] x_0 = 99, x_1 = 206, x_2 = 313 [/math] .

Источник

Что такое множество классов вычетов по модулю n?

Что такое сравнимы 2 числа по модулю я знаю, это когда a ≡ b (mod n) если n делит (a — b)

Что такое множество классов вычетов по модулю n?

с источников я понял что обозначаеться как Zn, где n — это и есть модуль.

пример Zn = <[0], [1], [2]>, каждый єлемент называеться классом эквивалентности?

И что такое класс вычетов? это когда в каждом классе єквивалентности есть множество в котором каждые 2 пары элементов сравнимы по модулю? пример: [0] = [. -6,-3,0, 3,6. ] тут модулю n = 3.

И что в теме сравнимости значит этот символ «⊕». это операция с классами эквивалентности?

1 ответ 1

Множество классов вычетов по модулю m — это множество чисел 0 , 1 . m-1 . Обозначается

На множестве Z/mZ определены операции сложения, вычитания, умножения и деления. Я обозначу их [+] , [-] , [*] и [/] , чтобы отличать от обчных операций сложения и умножения целых чисел:

a [+] b = (a+b)%m — остаток от деления обычной суммы a и b на m ,

a [*] b = (a*b)%m — остаток от деления обычного произведения a и b на m ,

[-]a = m — a , и [-]0 = 0 . Соответственно a [-] b = a [+] ([-]b)

Деление — самая хитрая операция в множестве вычетов. a [/] b — это такое число c , что b [*] c = a . Так вот, в отличие от целых чисел, которые делятся друг на друга довольно редко, классы вычетов делятся друг на друга почти всегда. Для этого необходимо и достаточно, чтобы a и b не имели общих делителей с m . Если m — простое число, то все ненулевые пары a и b можно делить. Для деления Z/mZ используется расширенный алгоритм Евклида.

Как это связано с классами эквивалентности. Возьмем ваш пример Z3 =

Класс эквивалентности [0] обозначает все те целые числа, которые при делении на 3 дадут остаток 0: [0] ==

Класс эквивалентности [1] обозначает все те целые числа, которые при делении на 3 дадут остаток 1: [1] ==

Класс эквивалентности [2] обозначает все те целые числа, которые при делении на 3 дадут остаток 2: [2] ==

Операции с классами эквивалентности определяются так (для определённости рассмотрим сумму): давайте возьмём из каждого класса по одному представителю, сложим их и в качестве результата возьмём класс эквивалентности получившейся суммы. Например [1] [+] [2] — возьмём из [1] число 1, а из [2] возьёмем 2. 1+2 = 3 . Класс эквивалентности, к которому принадлежит 3 — это [0] . Следовательно, [1] [+] [2] = [0]

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

Источник

Модульная арифметика

2.2. Модульная арифметика

Уравнение деления ( ), рассмотренное в предыдущей секции, имеет два входа ( a и n ) и два выхода ( q и r ). В модульной арифметике мы интересуемся только одним из выходов — остатком r . Мы не заботимся о частном q . Другими словами, когда мы делим a на n , мы интересуемся только тем, что значение остатка равно r . Это подразумевает, что мы можем представить изображение вышеупомянутого уравнения как бинарный оператор с двумя входами a и n и одним выходом r .

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

Вышеупомянутый бинарный оператор назван оператором по модулю и обозначается как mod . Второй вход ( n ) назван модулем. Вывод r назван вычетом. Рисунок 2.9 показывает отношение деления по сравнению с оператором по модулю.

Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из множества Z и положительный модуль ( n ). Оператор определяет неотрицательный остаток ( r ).

Мы можем сказать, что

Найти результат следующих операций:

Мы ищем вычет r . Мы можем разделить a на n и найти q и r . Далее можно игнорировать q и сохранить r .

а. Разделим 27 на 5 — результат: r = 2 . Это означает, что 27 mod 5 = 2 .

б. Разделим 36 на 12 — результат: r = 0 . Это означает, что 36 mod 12 = 0 .

в. Разделим (–18) на 14 — результат: r = –4 . Однако мы должны прибавить модуль (14) , чтобы сделать остаток неотрицательным. Мы имеем r = –4 + 14 = 10 . Это означает, что –18 mod 14 = 10 .

г. Разделим (–7) на 10 — результат: r = –7 . После добавления модуля –7 мы имеем r = 3 . Это означает, что –7 mod 10 = 3 .

Система вычетов: Zn

Результат операции по модулю n — всегда целое число между 0 и n — 1 . Другими словами, результат a mod n — всегда неотрицательное целое число, меньшее, чем n . Мы можем сказать, что операция по модулю создает набор, который в модульной арифметике можно понимать как систему наименьших вычетов по модулю n, или Z_n . Однако мы должны помнить, что хотя существует только одно множество целых чисел ( Z ), мы имеем бесконечное число множеств вычетов ( Z_n ), но лишь одно для каждого значения n . Рисунок 2.10 показывает множество Z_n и три множества Z₂ , Z₆ и Z₁₁ .

Сравнения

В криптографии мы часто используем понятие сравнения вместо равенства. Отображение Z в Z_n не отображаются «один в один». Бесконечные элементы множества Z могут быть отображены одним элементом Z_n . Например, результат 2 mod 10 = 2 , 12 mod 10 = 2 , 22 mod 10 = 2 , и так далее. В модульной арифметике целые числа, подобные 2 , 12 , и 22 , называются сравнимыми по модулю 10 (mod 10) . Для того чтобы указать, что два целых числа сравнимы, мы используем оператор сравнения ( ). Мы добавляем mod n к правой стороне сравнения, чтобы определить значение модуля и сделать равенство правильным. Например, мы пишем:

Рисунок 2.11 показывает принцип сравнения. Мы должны объяснить несколько положений.

a. Оператор сравнения напоминает оператор равенства, но между ними есть различия. Первое: оператор равенства отображает элемент Z самого на себя; оператор сравнения отображает элемент Z на элемент Z_n . Второе: оператор равенства показывает, что наборы слева и справа соответствуют друг другу «один в один», оператор сравнения — «многие — одному».

б. Обозначение ( mod n ), которое мы вставляем с правой стороны оператора сравнения, обозначает признак множества ( Z_n ). Мы должны добавить это обозначение, чтобы показать, какой модуль используется в отображении. Символ, используемый здесь, не имеет того же самого значения, как бинарный оператор в уравнении деления. Другими словами, символ mod в выражении 12 mod 10 — оператор; а сочетание ( mod 10 ) в сравнении означает, что набор — Z₁₀ .

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

Система вычетов [a] , или [a]_n , — множество целых чисел, сравнимых по модулю n . Другими словами, это набор всех целых чисел, таких, что x = a (mod n) . Например, если n = 5 , мы имеем множество из пяти элементов [0] , [1] , [2] , [3] и [4] , таких как это показано ниже:

Целые числа в наборе [0] все дают остаток 0 при делении на 5 (сравнимы по модулю 5 ). Целые числа в наборе [1] все дают остаток 1 при делении на 5 (сравнимы по модулю 5 ), и так далее. В каждом наборе есть один элемент, называемый наименьшим (неотрицательным) вычетом. В наборе [0] это элемент 0 ; в наборе [1] — 1 , и так далее. Набор, который показывает все наименьшие вычеты: Z₅ = <0, 1, 2, 3, 4>. Другими словами, набор Z_n — набор всех наименьших вычетов по модулю n.

Круговая система обозначений

Понятие «сравнение» может быть лучше раскрыто при использовании круга в качестве модели. Так же, как мы применяем линию, чтобы показать распределение целых чисел в Z , мы можем использовать круг, чтобы показать распределение целых чисел в Z_n .

Рисунок 2.12 позволяет сравнить два этих подхода. Целые числа от 0 до n–1 расположены равномерно вокруг круга. Все целые числа, сравнимые по модулю n , занимают одни и те же точки в круге. Положительные и отрицательные целые числа от Z отображаются в круге одним и тем же способом, соблюдая симметрию между ними.

Мы пользуемся сравнением по модулю в нашей ежедневной жизни; например, мы применяем часы, чтобы измерить время. Наша система часов использует арифметику по модулю 12 . Однако вместо 0 мы берем отсечку 12 , так что наша система часов начинается с 0 (или 12 ) и идет до 11 . Поскольку наши сутки длятся 24 часа, мы считаем по кругу два раза и обозначаем первое вращение как утро до полудня, а второе — как вечер после полудня.

Операции в Zn

Три бинарных операции ( сложение, вычитание и умножение ), которые мы обсуждали для Z , могут также быть определены для набора Z_n . Результат, возможно, должен быть отображен в Z_n с использованием операции по модулю, как это показано на рис. 2.13.

Фактически применяются два набора операторов: первый набор — один из бинарных операторов ; второй — операторы по модулю. Мы должны использовать круглые скобки, чтобы подчеркнуть порядок работ. Как показано на рис. 2.13, входы ( a и b ) могут быть членами Z или Z_n .

Выполните следующие операторы (поступающие от Z_n ):

а. Сложение 7 и 14 в Z₁₅

б. Вычитание 11 из 7 в Z₁₃

в. Умножение 11 на 7 в Z₂₀

Ниже показаны два шага для каждой операции:

Выполните следующие операции (поступающие от Z_n ):

a. Сложение 17 и 27 в Z₁₄

b. Вычитание 43 из 12 в Z₁₃

c. Умножение 123 на -10 в Z₁₉

Ниже показаны два шага для каждой операции:

Свойства

Мы уже упоминали, что два входа для трех бинарных операторов в сравнении по модулю могут использовать данные из Z или Z_n . Следующие свойства позволяют нам сначала отображать два входа к Z_n (если они прибывают от Z ) перед выполнением этих трех бинарных операторов . Заинтересованные читатели могут найти доказательства для этих свойств в приложении Q.

Первое свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n

Второе свойство: (a – b) mod n = [(a mod n) — (b mod n)] mod n

Третье свойство: (a x b) mod n = [(a mod n) x (b mod n)] mod n

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

Следующие примеры показывают приложение вышеупомянутых свойств.

В арифметике мы часто должны находить остаток от степеней числа 10 при делении на целое число. Например, мы должны найти 10 mod 3 , 10 2 mod 3 , 10 3 mod 3 , и так далее. Мы также должны найти 10 mod 7 , 10 2 mod 7 , 10 3 mod 7 , и так далее. Третье свойство модульных операторов, упомянутое выше, делает жизнь намного проще.

Источник