stringtranslate.com

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

Для отсчета времени на этих часах используется арифметика по модулю 12. Прибавление 4 часов к 9 часам дает 1 час, поскольку 13 сравнимо с 1 по модулю 12.

В математике модульная арифметика — это система арифметики для целых чисел , где числа «переходят» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был разработан Карлом Фридрихом Гауссом в его книге Disquisitiones Arithmeticae , опубликованной в 1801 году.

Знакомое использование модульной арифметики — в 12-часовом формате , в котором день делится на два 12-часовых периода. Если сейчас 7:00, то через 8 часов будет 3:00. Простое сложение даст результат 7 + 8 = 15 , но 15:00 читается как 3:00 на циферблате часов, потому что часы «переворачиваются» каждые 12 часов, и номер часа начинается заново с нуля, когда достигает 12. Мы говорим, что 15 сравнимо с 3 по модулю 12, что записывается как 15 ≡ 3 (mod 12), так что 7 + 8 ≡ 3 (mod 12). Аналогично, 8:00 представляет собой период в 8 часов, а умножив это число дважды, получим 16:00, что на циферблате часов отображается как 4:00, что записывается как 2 × 8 ≡ 4 (mod 12).

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

Для данного целого числа m ≥ 1 , называемого модулем , два целых числа a и b называются сравнимыми по модулю m , если m является делителем их разности; то есть если существует целое число k такое, что

аb = км .

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

аb (mod m ) .

Скобки означают, что (mod m ) применяется ко всему уравнению, а не только к правой части (здесь b ).

Эту запись не следует путать с записью b mod m (без скобок), которая относится к операции деления по модулю , остатку от b при делении на m : то есть b mod m обозначает уникальное целое число r, такое что 0 ≤ r < m и rb (mod m ) .

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

а = км + б ,

явно показывая его связь с евклидовым делением . Однако b здесь не обязательно должен быть остатком при делении a на m . Скорее, ab (mod m ) утверждает, что a и b имеют одинаковый остаток при делении на m . То есть,

а = пм + г ,
б = + г ,

где 0 ≤ r < m — общий остаток. Мы восстанавливаем предыдущее соотношение ( ab = km ), вычитая эти два выражения и устанавливая k = pq .

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

Примеры

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

38 ≡ 14 (мод 12)

потому что разность составляет 38 − 14 = 24 = 2 × 12 , кратная 12. Эквивалентно, 38 и 14 имеют одинаковый остаток 2 при делении на 12 .

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

Основные свойства

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

Если a 1b 1 (mod m ) и a 2b 2 (mod m ) , или если ab (mod m ) , то: [1]

Если ab (mod m ) , то, как правило, неверно, что k ak b (mod m ) . Однако верно следующее:

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

Последнее правило можно использовать для переноса модульной арифметики в деление. Если b делит a , то ( a / b ) mod m = ( a mod bm )/ b .

Модульная мультипликативная обратная величина определяется следующими правилами:

Мультипликативный обратный элемент xa −1 (mod m ) можно эффективно вычислить, решив уравнение Безу a x + my = 1 для x , y , используя расширенный алгоритм Евклида .

В частности, если p — простое число, то a взаимно просто с p для любого a, такого что 0 < a < p ; таким образом, существует мультипликативная обратная величина для всех a , которые не сравнимы с нулем по модулю p .

Расширенные свойства

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

Классы соответствия

Отношение конгруэнтности — это отношение эквивалентности . Класс эквивалентности по модулю m целого числа a — это множество всех целых чисел вида a + km , где k — любое целое число. Он называется классом конгруэнтности или классом вычетов a по модулю  m и может обозначаться как ( a mod m ) , или как a или [ a ], когда модуль m известен из контекста.

Каждый класс остатков по модулю  m содержит ровно одно целое число в диапазоне . Таким образом, эти целые числа являются представителями своих соответствующих классов остатков.

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

Следовательно, ( a mod m ) обозначает, как правило, единственное целое число k, такое что 0 ≤ k < m и ka (mod m ) ; оно называется вычетом числа a по модулю  m .

В частности, ( a mod m ) = ( b mod m ) эквивалентно ab (mod m ) , и это объясняет, почему в этом контексте « = » часто используется вместо « ».

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

Каждый класс остатков по модулю m может быть представлен любым из его членов, хотя мы обычно представляем каждый класс остатков наименьшим неотрицательным целым числом, которое принадлежит этому классу [2] (так как это правильный остаток, который получается в результате деления). Любые два члена различных классов остатков по модулю m являются несопоставимыми по модулю m . Более того, каждое целое число принадлежит одному и только одному классу остатков по модулю m . [3]

Набор целых чисел {0, 1, 2, ..., m − 1} называется наименьшей системой вычетов по модулю m . Любой набор из m целых чисел, никакие два из которых не сравнимы по модулю m , называется полной системой вычетов по модулю m .

Система наименьших остатков — это полная система остатков, а полная система остатков — это просто набор, содержащий ровно одного представителя каждого класса остатков по модулю m . [4] Например, система наименьших остатков по модулю 4 — это {0, 1, 2, 3} . Некоторые другие системы полных остатков по модулю 4 включают:

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

Системы с уменьшенным остатком

При наличии функции Эйлера φ ( m ) любой набор целых чисел φ ( m ) , которые взаимно просты с m и взаимно неконгруэнтны по модулю m, называется приведенной системой вычетов по модулю m . [5] Например, набор {5, 15} из вышеприведенного примера является примером приведенной системы вычетов по модулю 4.

Системы покрытия

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

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

Замечание: В контексте этого параграфа модуль m почти всегда принимается положительным.

Множество всех классов конгруэнтности по модулю m называется кольцом целых чисел по модулю m , [6] и обозначается , , или . [7] Однако эта нотация не рекомендуется, поскольку ее можно спутать с множеством m -адических целых чисел . Кольцо является основополагающим для различных разделов математики (см. § Приложения ниже).

При m > 0 имеем

При m = 1 — нулевое кольцо ; при m = 0 — не пустое множество ; скорее, оно изоморфно , поскольку a 0 = { a } .

Сложение, вычитание и умножение определяются следующими правилами:

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

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

Обозначение используется потому, что это кольцо является фактор-кольцом по идеалу , множеству, образованному всеми km с

Рассматриваемая как группа по сложению, является циклической группой , и все циклические группы изоморфны для некоторого m . [8]

Кольцо целых чисел по модулю m является полем тогда и только тогда, когда mпростое число (это гарантирует, что каждый ненулевой элемент имеет мультипликативный обратный элемент ). Если m = p kстепень простого числа с k > 1 , то существует единственное (с точностью до изоморфизма) конечное поле с m элементами, которое не изоморфно , которое не является полем, поскольку имеет делители нуля .

Если m > 1 , обозначает мультипликативную группу целых чисел по модулю m , которые обратимы. Она состоит из классов конгруэнтности a m , где a взаимно просто с m ; это как раз те классы, которые обладают мультипликативным обратным. Они образуют абелеву группу относительно умножения; ее порядок равен φ ( m ) , где φфункция Эйлера

Приложения

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

Очень практичным применением является вычисление контрольных сумм в идентификаторах серийных номеров. Например, Международный стандартный номер книги (ISBN) использует арифметику по модулю 11 (для 10-значного ISBN) или по модулю 10 (для 13-значного ISBN) для обнаружения ошибок. Аналогично, например, Международные номера банковских счетов (IBAN) используют арифметику по модулю 97 для обнаружения ошибок ввода пользователя в номера банковских счетов. В химии последняя цифра номера реестра CAS (уникальный идентификационный номер для каждого химического соединения) является контрольной цифрой , которая вычисляется путем взятия последней цифры первых двух частей номера реестра CAS, умноженного на 1, предыдущей цифры, умноженной на 2, предыдущей цифры, умноженной на 3 и т. д., сложения всех этих цифр и вычисления суммы по модулю 10.

В криптографии модульная арифметика напрямую поддерживает системы открытого ключа , такие как RSA и Диффи–Хеллмана , и обеспечивает конечные поля , которые лежат в основе эллиптических кривых , и используется во множестве алгоритмов симметричного ключа , включая Advanced Encryption Standard (AES), International Data Encryption Algorithm (IDEA) и RC4 . RSA и Диффи–Хеллмана используют модульное возведение в степень .

В компьютерной алгебре модульная арифметика обычно используется для ограничения размера целочисленных коэффициентов в промежуточных вычислениях и данных. Она используется в полиномиальной факторизации , задаче, для которой все известные эффективные алгоритмы используют модульную арифметику. Она используется наиболее эффективными реализациями полиномиального наибольшего общего делителя , точной линейной алгебры и алгоритмов базиса Грёбнера над целыми и рациональными числами. Как было опубликовано на Fidonet в 1980-х годах и заархивировано в Rosetta Code , модульная арифметика была использована для опровержения гипотезы Эйлера о сумме степеней на микрокомпьютере Sinclair QL, используя всего одну четвертую целочисленной точности, используемой суперкомпьютером CDC 6600, чтобы опровергнуть ее два десятилетия назад с помощью поиска методом грубой силы . [9]

В информатике модульная арифметика часто применяется в побитовых операциях и других операциях, включающих циклические структуры данных фиксированной ширины . Операция по модулю, реализованная во многих языках программирования и калькуляторах , является применением модульной арифметики, которое часто используется в этом контексте. Логический оператор XOR суммирует 2 бита по модулю 2.

Использование длинного деления для превращения дроби в периодическую десятичную дробь в любой системе счисления с основанием b эквивалентно модульному умножению b на знаменатель. Например, для десятичной дроби b = 10.

В музыке арифметика по модулю 12 используется при рассмотрении системы двенадцатитоновой равномерной темперации , где имеет место октавная и энгармоническая эквивалентность (то есть высоты тона в соотношении 1:2 или 2:1 эквивалентны, а нота до- диез считается такой же, как и нота ре- бемоль ).

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

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

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

Сложность вычислений

Поскольку модульная арифметика имеет такой широкий спектр приложений, важно знать, насколько сложно решить систему сравнений. Линейная система сравнений может быть решена за полиномиальное время с помощью метода исключения Гаусса , подробности см. в линейной теореме о сравнении . Существуют также алгоритмы, такие как редукция Монтгомери , позволяющие эффективно выполнять простые арифметические операции, такие как умножение и возведение в степень по модулю  m , над большими числами.

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

Решение системы нелинейных модульных арифметических уравнений является NP-полной задачей . [10]

Смотрите также

Примечания

  1. ^ Шандор Лехоцки; Ричард Русцки (2006). Дэвид Патрик (ред.). Искусство решения проблем . Том 1 (7-е изд.). AoPS Incorporated. стр. 44. ISBN 0977304566.
  2. ^ Weisstein, Eric W. "Modular Arithmetic". Wolfram MathWorld . Архивировано из оригинала 2023-07-14 . Получено 2020-08-12 .
  3. ^ Петтофреццо и Биркит (1970, стр. 90)
  4. ^ Лонг (1972, стр. 78)
  5. ^ Лонг (1972, стр. 85)
  6. ^ Это кольцо , как показано ниже.
  7. ^ "2.3: Целые числа по модулю n". Mathematics LibreTexts . 2013-11-16. Архивировано из оригинала 2021-04-19 . Получено 2020-08-12 .
  8. ^ Сенгадир Т., Дискретная математика и комбинаторика , стр. 293, в Google Books
  9. ^ "Гипотеза Эйлера о сумме степеней". rosettacode.org . Архивировано из оригинала 2023-03-26 . Получено 2020-11-11 .
  10. ^ Гэри, М. Р.; Джонсон, Д. С. (1979). Компьютеры и неразрешимость, руководство по теории NP-полноты . WH Freeman. ISBN 0716710447.

Ссылки

Внешние ссылки