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

Для хронометража на этих часах используется арифметика по модулю 12.

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

Знакомое использование модульной арифметики находится в 12-часовой формат, в котором день разделен на два 12-часовых периода. Если сейчас 7:00, то через 8 часов будет 3:00. Простое добавление приведет к 7 + 8 = 15, но часы "переключаются" каждые 12 часов. Поскольку число часов начинается заново после достижения 12, это арифметика. по модулю 12. Согласно приведенному ниже определению, 15 - это конгруэнтный до 3 по модулю 12, поэтому "15:00" на 24-часовые часы отображается «3:00» в 12-часовом формате.

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

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

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

${displaystyle aequiv b {pmod {n}}.}$

Скобки означают, что (мод п) применяется ко всему уравнению, а не только к правой части (здесь б). Это обозначение не следует путать с обозначением б мод п (без скобок), что относится к операция по модулю. В самом деле, б мод п обозначает уникальное целое число а такой, что 0 ≤ а < п и ${displaystyle aequiv b; ({ext {mod}}; n)}$ (т.е. оставшаяся часть ${displaystyle b}$ при делении на ${displaystyle n}$^[1]).

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

${displaystyle a = kn + b,}$

явно показывая свою связь с Евклидово деление. Тем не менее б здесь не должно быть остатка от деления а к п. Вместо этого, что заявление а ≡ б (мод п) утверждает, что а и б имеют тот же остаток при делении на п. То есть,

${displaystyle a = pn + r,}$

${displaystyle b = qn + r,}$

куда 0 ≤ р < п - общий остаток. Вычитая эти два выражения, мы восстанавливаем предыдущее соотношение:

${displaystyle a-b = kn,}$

установив k = п − q.

Примеры

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

${displaystyle 38equiv 14 {pmod {12}}}$

потому что 38 − 14 = 24, который кратен 12. Другой способ выразить это - сказать, что и 38, и 14 имеют одинаковый остаток 2 при делении на 12.

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

${Displaystyle {эгин {выровненный} -8 & эквив 7 {pmod {5}} 2 & эквив -3 {пмод {5}} - 3 & эквив -8 {пмод {5}}. конец {выровненный}}}$

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

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

• Рефлексивность: а ≡ а (мод п)
• Симметрия: а ≡ б (мод п) если б ≡ а (мод п) для всех а, б, и п.
• Транзитивность: если а ≡ б (мод п) и б ≡ c (мод п), тогда а ≡ c (мод п)

Если а₁ ≡ б₁ (мод п) и а₂ ≡ б₂ (мод п), или если а ≡ б (мод п), тогда:

• а + k ≡ б + k (мод п) для любого целого k (совместимость с переводом)
• к а ≡ к б (мод п) для любого целого k (совместимость с масштабированием)
• а₁ + а₂ ≡ б₁ + б₂ (мод п) (совместимость с дополнением)
• а₁ – а₂ ≡ б₁ – б₂ (мод п) (совместимость с вычитанием)
• а₁ а₂ ≡ б₁ б₂ (мод п) (совместимость с умножением)
• а^k ≡ б^k (мод п) для любого неотрицательного целого числа k (совместимость с возведением в степень)
• п(а) ≡ п(б) (мод п), для любого многочлен п(Икс) с целыми коэффициентами (совместимость с полиномиальной оценкой)

Если а ≡ б (мод п), то обычно неверно, что k^а ≡ k^б (мод п). Однако верно следующее:

• Если c ≡ d (мод φ(п)), куда φ является Функция Эйлера, тогда а^c ≡ а^d (мод п)-при условии, что а является совмещать с п.

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

• Если а + k ≡ б + k (мод п), куда k любое целое число, то а ≡ б (мод п)
• Если к а ≡ к б (мод п) и k взаимно прост с п, тогда а ≡ б (мод п)
• Если к а ≡ к б (мод кн) , тогда а ≡ б (мод п)

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

• Существование: существует целое число, обозначенное а^–1 такой, что аа^–1 ≡ 1 (мод п) если и только если а взаимно прост с п. Это целое число а^–1 называется модульный мультипликативный обратный из а по модулю п.
• Если а ≡ б (мод п) и а^–1 существует, тогда а^–1 ≡ б^–1 (мод п) (совместимость с мультипликативным обратным, и, если а = б, уникальность по модулю п)
• Если а х ≡ б (мод п) и а взаимно прост с п, то решение этого линейного сравнения дается формулой Икс ≡ а^–1б (мод п)

Мультипликативный обратный Икс ≡ а^–1 (мод п) может быть эффективно вычислен путем решения Уравнение Безу ${displaystyle ax + ny = 1}$ за ${displaystyle x, y}$-с использованием Расширенный алгоритм Евклида.

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

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

• Маленькая теорема Ферма: Если п простое и не делит а, тогда а ^{п – 1} ≡ 1 (мод п).
• Теорема Эйлера: Если а и п взаимно просты, то а ^φ(п) ≡ 1 (мод п), куда φ является Функция Эйлера
• Простое следствие малой теоремы Ферма состоит в том, что если п простое, то а⁻¹ ≡ а ^{п − 2} (мод п) является мультипликативным обратным к 0 < а < п. В более общем смысле, из теоремы Эйлера, если а и п взаимно просты, то а⁻¹ ≡ а ^{φ(п) − 1} (мод п).
• Еще одно простое следствие: если а ≡ б (мод φ(п)), куда φ - функция Эйлера, то k^а ≡ k^б (мод п) при условии k является совмещать с п.
• Теорема Вильсона: п прост тогда и только тогда, когда (п - 1)! ≡ −1 (mod п).
• Китайская теорема об остатках: Для любого а, б и coprime м, п, существует единственный Икс (мод млн) такой, что Икс ≡ а (мод м) и Икс ≡ б (мод п). Фактически, Икс ≡ б м_п^–1 м + а н_м^–1 п (мод млн) куда м_п⁻¹ является инверсией м по модулю п и п_м⁻¹ является инверсией п по модулю м.
• Теорема Лагранжа: Соответствие ж (Икс) ≡ 0 (мод. п), куда п простое, и ж (Икс) = а₀ Икс^п + ... + а_п это многочлен с целыми коэффициентами такими, что а₀ ≠ 0 (мод п), имеет не более п корни.
• Примитивный корень по модулю n: Число грамм примитивный корень по модулю п если для каждого целого числа а взаимно простой с п, есть целое число k такой, что грамм^k ≡ а (мод п). Примитивный корень по модулю п существует тогда и только тогда, когда п равно 2, 4, п^k или же 2п^k, куда п нечетное простое число и k положительное целое число. Если примитивный корень по модулю п существует, то есть ровно φ(φ(п)) такие первобытные корни, где φ - функция Эйлера.
• Квадратичный остаток: Целое число а квадратичный вычет по модулю п, если существует целое число Икс такой, что Икс² ≡ а (мод п). Критерий Эйлера утверждает, что если п - нечетное простое число, и а не является кратным п, тогда а квадратичный вычет по модулю п если и только если

${displaystyle a ^ {(p-1) / 2} Equiv 1 {pmod {p}}.}$

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

Как и любое отношение конгруэнтности, сравнение по модулю п является отношение эквивалентности, а класс эквивалентности целого числа а, обозначаемый а_п, это множество {… , а − 2п, а − п, а, а + п, а + 2п, …}. Этот набор, состоящий из всех целых чисел, конгруэнтных а по модулюп, называется класс конгруэнтности, класс остатка, или просто остаток целого числа а по модулюп. Когда модуль п известно из контекста, этот остаток также может быть обозначен [а].

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

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

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

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

• {1, 2, 3, 4}
• {13, 14, 15, 16}
• {−2, −1, 0, 1}
• {−13, 4, 17, 18}
• {−5, 0, 6, 21}
• {27, 32, 37, 42}

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

• {−5, 0, 6, 22}, поскольку 6 сравнимо с 22 по модулю 4.
• {5, 15}, поскольку полная система вычетов по модулю 4 должна иметь ровно 4 инконгруэнтных класса вычетов.

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

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

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

Набор всех классы конгруэнтности целых чисел для модуля п называется кольцо целых чисел по модулю п,^[6] и обозначается ${extstyle mathbb {Z} / nmathbb {Z}}$, ${displaystyle mathbb {Z} / n}$, или же ${displaystyle mathbb {Z} _ {n}}$.^[1][7] Обозначение ${displaystyle mathbb {Z} _ {n}}$ однако не рекомендуется, поскольку его можно спутать с набором п-адические целые числа. Кольцо ${displaystyle mathbb {Z} / nmathbb {Z}}$ лежит в основе различных разделов математики (см. § Приложения ниже).

Набор определен для п > 0 как:

${displaystyle mathbb {Z} / nmathbb {Z} = left {{overline {a}} _ {n} mid ain mathbb {Z} ight} = left {{overline {0}} _ {n}, {overline {1) }} _ {n}, {overline {2}} _ {n}, ldots, {overline {n {-} 1}} _ {n} ight}.}$

(Когда п = 0, ${displaystyle mathbb {Z} / nmathbb {Z}}$ не является пустой набор; скорее, это изоморфный к ${displaystyle mathbb {Z}}$, поскольку а₀ = {а}.)

Мы определяем сложение, вычитание и умножение на ${displaystyle mathbb {Z} / nmathbb {Z}}$ по следующим правилам:

• ${displaystyle {overline {a}} _ {n} + {overline {b}} _ {n} = {overline {(a + b)}} _ {n}}$
• ${displaystyle {overline {a}} _ {n} - {overline {b}} _ {n} = {overline {(a-b)}} _ {n}}$
• ${displaystyle {overline {a}} _ {n} {overline {b}} _ {n} = {overline {(ab)}} _ {n}.}$

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

Таким образом, ${displaystyle mathbb {Z} / nmathbb {Z}}$ становится коммутативное кольцо. Например, на ринге ${displaystyle mathbb {Z} / 24mathbb {Z}}$, у нас есть

${displaystyle {overline {12}} _ {24} + {overline {21}} _ {24} = {overline {33}} _ {24} = {overline {9}} _ {24}}$

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

Мы используем обозначения ${displaystyle mathbb {Z} / nmathbb {Z}}$ потому что это кольцо частного из ${displaystyle mathbb {Z}}$ посредством идеальный ${displaystyle nmathbb {Z}}$, набор, содержащий все целые числа, делящиеся на п, куда ${displaystyle 0mathbb {Z}}$ это одноэлементный набор {0}. Таким образом ${displaystyle mathbb {Z} / nmathbb {Z}}$ это поле когда ${displaystyle nmathbb {Z}}$ это максимальный идеал (т.е. когда п простое).

Это также можно построить из группы ${displaystyle mathbb {Z}}$ только при операции сложения. Остаточный класс а_п это группа смежный из а в факторгруппа ${displaystyle mathbb {Z} / nmathbb {Z}}$, а циклическая группа.^[8]

Вместо того, чтобы исключать особый случай п = 0, полезнее включить ${displaystyle mathbb {Z} / 0mathbb {Z}}$ (которое, как упоминалось ранее, изоморфно кольцу ${displaystyle mathbb {Z}}$ целых чисел). Фактически, это включение полезно при обсуждении характеристика из звенеть.

Кольцо целых чисел по модулю п это конечное поле если и только если п является основной (это гарантирует, что каждый ненулевой элемент имеет мультипликативный обратный ). Если ${displaystyle n = p ^ {k}}$ это основная сила с k > 1 существует единственное (с точностью до изоморфизма) конечное поле ${displaystyle mathrm {GF} (n) = mathbb {F} _ {n}}$ с п элементы, но это нет ${displaystyle mathbb {Z} / nmathbb {Z}}$, который не может быть полем, потому что делители нуля.

В мультипликативная подгруппа целых чисел по модулю п обозначается ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {imes}}$. Это состоит из ${displaystyle {overline {a}} _ {n}}$ (куда а взаимно простой к п), которые являются в точности классами, обладающими мультипликативным обратным. Это образует коммутативный группа при умножении, с порядком ${displaystyle varphi (n)}$.

Приложения

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

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

В криптографии модульная арифметика напрямую лежит в основе открытый ключ такие системы как ЮАР и Диффи – Хеллмана, и предоставляет конечные поля которые лежат в основе эллиптические кривые, и используется в различных алгоритмы с симметричным ключом включая Расширенный стандарт шифрования (AES), Международный алгоритм шифрования данных (IDEA) и RC4. RSA и Диффи – Хеллмана используют модульное возведение в степень.

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

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

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

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

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

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

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

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

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

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

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

Эта секция возможно содержит оригинальные исследования. Пожалуйста Улучши это к проверка заявленные претензии и добавление встроенные цитаты. Заявления, содержащие только оригинальные исследования, следует удалить. (Май 2020 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Алгоритмический способ вычисления ${displaystyle acdot b {pmod {m}}}$:^[11]

uint64_t mul_mod(uint64_t а, uint64_t б, uint64_t м){   если (!((а | б) & (0xFFFFFFFFULL << 32)))       возвращаться а * б % м;   uint64_t d = 0, mp2 = м >> 1;   int я;   если (а >= м) а %= м;   если (б >= м) б %= м;   за (я = 0; я < 64; ++я)   {       d = (d > mp2) ? (d << 1) - м : d << 1;       если (а & 0x8000000000000000ULL)           d += б;       если (d >= м) d -= м;       а <<= 1;   }   возвращаться d;}

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

uint64_t mul_mod(uint64_t а, uint64_t б, uint64_t м){   длинный двойной Икс;   uint64_t c;   int64_t р;   если (а >= м) а %= м;   если (б >= м) б %= м;   Икс = а;   c = Икс * б / м;   р = (int64_t)(а * б - c * м) % (int64_t)м;   возвращаться р < 0 ? р + м : р;}

Ниже приведена функция C для выполнения модульного возведения в степень, которая использует mul_mod функция реализована выше.

Алгоритмический способ вычисления ${displaystyle a ^ {b} {pmod {m}}}$:

uint64_t pow_mod(uint64_t а, uint64_t б, uint64_t м){    uint64_t р = м==1?0:1;    пока (б > 0) {        если (б & 1)            р = mul_mod(р, а, м);        б = б >> 1;        а = mul_mod(а, а, м);    }    возвращаться р;}

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

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

Примечания

Рекомендации

• Джон Л. Берггрен. «модульная арифметика». Британская энциклопедия.
• Апостол, Том М. (1976), Введение в аналитическую теорию чисел, Тексты для бакалавриата по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN  978-0-387-90163-3, МИСТЕР  0434929, Zbl  0335.10001. См., В частности, главы 5 и 6 для обзора базовой модульной арифметики.
• Маартен Буллинк "Модульная арифметика до C.F. Гаусс. Систематизация и обсуждение остаточных проблем в Германии XVIII века "
• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7. Раздел 31.3: Модульная арифметика, стр. 862–868.
• Энтони Джоя, Теория чисел, введение Перепечатка (2001) Dover. ISBN  0-486-41449-3.
• Лонг, Кальвин Т. (1972). Элементарное введение в теорию чисел (2-е изд.). Лексингтон: Д. К. Хит и компания. LCCN  77171950.
• Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970). Элементы теории чисел. Энглвудские скалы: Prentice Hall. LCCN  71081766.
• Сенгадир Т. (2009). Дискретная математика и комбинаторика. Ченнаи, Индия: Pearson Education India. ISBN  978-81-317-1405-8. OCLC  778356123.

внешняя ссылка

• «Конгруэнтность», Энциклопедия математики, EMS Press, 2001 [1994]
• В этом модульное искусство статью, можно узнать больше о приложениях модульной арифметики в искусстве.
• An статья по модульной арифметике в GIMPS wiki
• Модульная арифметика и шаблоны в таблицах сложения и умножения