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

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

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

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

Для данного целого числа n > 1 , называемого модулем , два целых числа называются конгруэнтными по модулю n , если n является делителем их разности (т.е. если существует целое число k такое, что a - b = kn ).

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

${\ Displaystyle a \ Equiv b {\ pmod {n}}.}$

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

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

${\ displaystyle a = kn + b,}$

явно показывая его связь с евклидовым делением . Однако здесь b не обязательно должно быть остатком от деления a на n . Вместо этого утверждение a ≡ b (mod n ) утверждает, что a и b имеют одинаковый остаток при делении на n . Это,

${\ displaystyle a = pn + r,}$

${\ displaystyle b = qn + r,}$

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

${\ displaystyle ab = kn,}$

положив k = p - q .

Примеры

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

${\ Displaystyle 38 \ Equiv 14 {\ pmod {12}}}$

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

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

${\ Displaystyle {\ begin {align} 2 & \ Equiv -3 {\ pmod {5}} \\ - 8 & \ Equiv 7 {\ pmod {5}} \\ - 3 & \ Equiv -8 {\ pmod {5}} . \ end {выровнено}}}$

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

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

Если a ₁ ≡ b ₁ (mod n ) и a ₂ ≡ b ₂ (mod n ), или если a ≡ b (mod n ), то:

• a + k ≡ b + k (mod n ) для любого целого k (совместимость с переводом)
• ka ≡ kb (mod n ) для любого целого k (совместимость с масштабированием)
• a ₁ + a ₂ ≡ b ₁ + b ₂ (mod n ) (совместимость с сложением)
• a ₁ - a ₂ ≡ b ₁ - b ₂ (mod n ) (совместимость с вычитанием)
• a ₁ a ₂ ≡ b ₁ b ₂ (mod n ) (совместимость с умножением)
• a ^k ≡ b ^k (mod n ) для любого неотрицательного целого числа k (совместимость с возведением в степень)
• p ( a ) ≡ p ( b ) (mod n ) , для любого полинома p ( x ) с целыми коэффициентами (совместимость с полиномиальной оценкой)

Если a ≡ b (mod n ) , то, как правило, неверно, что k ^a ≡ k ^b (mod n ) . Однако верно следующее:

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

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

• Если a + k ≡ b + k (mod n ) , где k - любое целое число, то a ≡ b (mod n )
• Если ka ≡ kb (mod n ) и k взаимно просто с n , то a ≡ b (mod n )
• Если ka ≡ kb (mod kn ) , то a ≡ b (mod n )

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

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

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

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

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

• Маленькая теорема Ферма : если p простое и не делит a , то a ^{p - 1} ≡ 1 (mod p ) .
• Теорема Эйлера : если a и n взаимно просты, то a ^{φ ( n )} ≡ 1 (mod n ) , где φ - функция Эйлера.
• Простое следствие малой теоремы Ферма состоит в том, что если p простое, то a ⁻¹ ≡ a ^{p - 2} (mod p ) является мультипликативным обратным к 0 < a < p . В более общем смысле, из теоремы Эйлера, если a и n взаимно просты, то a ⁻¹ ≡ a ^{φ ( n ) - 1} (mod n ) .
• Другим простым следствием является то , что , если ≡ Ь ( по модулю φ ( п )), где φ является Функция Эйлера, то к ≡ к ^Ь ( по модулю п ) при условии , к является взаимно просты с п .
• Теорема Вильсона : p простое тогда и только тогда, когда ( p - 1)! −1 (по модулю p ) .
• Китайская теорема об остатке : для любых a , b и взаимно простых m , n существует единственный x (mod mn ) такой, что x ≡ a (mod m ) и x ≡ b (mod n ) . Фактически, x ≡ bm _n ^–1 m + an _m ^–1 n (mod mn ), где m _n ⁻¹ является обратным к m по модулю n, а n _m ⁻¹ является обратным к n по модулю m .
• Теорема Лагранжа : сравнение f ( x ) ≡ 0 (mod p ) , где p простое, а f ( x ) = a ₀ x ⁿ + ... + a _n - многочлен с целыми коэффициентами, такой что a ₀ ≠ 0 (mod p ) , имеет не более n корней.
• Первообразный корень по модулю п : Число г является первообразным корнем по модулю п , если для всякого целого числа в копервичном к п , существует целое число к такому , что г ^к ≡ ( по модулю п ) . Примитивный корень по модулю n существует тогда и только тогда, когда n равно 2, 4, p ^k или 2 p ^k , где p - нечетное простое число, а k - положительное целое число. Если существует первообразный корень по модулю n , то таких первообразных корней ровно φ ( φ ( n )) , где φ - функция Эйлера.
• Квадратичный вычет : целое число a является квадратичным вычетом по модулю n , если существует целое число x такое, что x ² ≡ a (mod n ) . Критерий Эйлера утверждает, что если p - нечетное простое число и a не делится на p , то a является квадратичным вычетом по модулю p тогда и только тогда, когда

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

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

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

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

Система наименьших остатков - это полная система остатков, а полная система остатков - это просто набор, содержащий ровно одного представителя каждого класса остатков по модулю n . ^[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 инконгруэнтных класса вычетов.

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

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

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

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

${\ displaystyle \ mathbb {Z} / n \ mathbb {Z} = \ left \ {{\ overline {a}} _ {n} \ mid a \ in \ mathbb {Z} \ right \} = \ left \ { {\ overline {0}} _ {n}, {\ overline {1}} _ {n}, {\ overline {2}} _ {n}, \ ldots, {\ overline {n {-} 1}} _ {n} \ right \}.}$

(Когда n = 0 ,${\ Displaystyle \ mathbb {Z} / п \ mathbb {Z}}$не пустой набор ; скорее, оно изоморфно к${\ Displaystyle \ mathbb {Z}}$, поскольку a ₀ = { a } .)

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

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

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

Этим способом, ${\ Displaystyle \ mathbb {Z} / п \ mathbb {Z}}$становится коммутативным кольцом . Например, на ринге${\ Displaystyle \ mathbb {Z} / 24 \ mathbb {Z}}$, у нас есть

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

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

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

Это также можно построить из группы ${\ Displaystyle \ mathbb {Z}}$только при операции сложения. Класс вычетов _п представляет собой группу смежных классов из в фактор - группе ${\ Displaystyle \ mathbb {Z} / п \ mathbb {Z}}$, циклическая группа . ^[8]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

uint64_t  mul_mod ( uint64_t  a ,  uint64_t  b ,  uint64_t  m ) {  if  ( ! (( a  |  b )  &  ( 0xFFFFFFFFULL  <<  32 )))  return  a  *  b  %  m ; uint64_t  d  =  0 ,  mp2  =  m  >>  1 ;  int  i ;  если  ( a  > =  m )  a  % =  m ;  если  ( b  > =  m )  b  % =  m ;  для  ( i  =  0 ;  i  <  64 ;  ++ i )  {  d  =  ( d  >  mp2 )  ?  ( d  <<  1 )  -  m  :  d  <<  1 ;  если  ( a  &  0x8000000000000000ULL )  d  + =  b ;  если  ( d  > =  m )  d  - =  m ;  а  << =  1 ;  }  return  d ; }

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

uint64_t  mul_mod ( uint64_t  a ,  uint64_t  b ,  uint64_t  m ) {  длинный  двойной  x ;  uint64_t  c ;  int64_t  r ;  если  ( a  > =  m )  a  % =  m ;  если  ( b  > =  m )  b  % =  m ;  х  =  а ;  с  =  х  *  б  /  м ;  r  =  ( int64_t ) ( a  *  b  -  c  *  m )  %  ( int64_t ) m ;  вернуть  r  <  0  ?  г  +  м  :  г ; }

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

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

uint64_t  pow_mod ( uint64_t  a ,  uint64_t  b ,  uint64_t  m ) {  uint64_t  r  =  m == 1 ? 0 : 1 ;  while  ( b  >  0 )  {  если  ( b  &  1 )  r  =  mul_mod ( r ,  a ,  m );  b  =  b  >>  1 ;  а  =  mul_mod ( а ,  а ,  м );  }  return  r ; }

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

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

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