В математике модульная арифметика — это система арифметики целых чисел , в которой числа «закручиваются» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был развит Карлом Фридрихом Гауссом в его книге Disquisitiones Arithmeticae , опубликованной в 1801 году.
Знакомое использование модульной арифметики — 12-часовые часы , в которых день делится на два 12-часовых периода. Если сейчас время 7:00, то через 8 часов будет 3:00. Простое сложение привело бы к 7 + 8 = 15 , но 15:00 читается как 3:00 на циферблате, потому что часы «оборачиваются» каждые 12 часов, а отсчет часов начинается с нуля, когда он достигает 12. Мы говорим, что 15 конгруэнтно 3 по модулю 12, записанному 15 ≡ 3 (по модулю 12), так что 7 + 8 ≡ 3 (по модулю 12). Точно так же 8:00 представляет собой период в 8 часов, а дважды это даст 16:00, что на циферблате означает 4:00, записанное как 2 × 8 ≡ 4 (модуль 12).
Учитывая целое число n ≥ 1 , называемое модулем , два целых числа a и b называются конгруэнтными по модулю n , если n является делителем их разности; то есть, если существует целое число k такое, что
Сравнение по модулю n является отношением сравнения , то есть это отношение эквивалентности , совместимое с операциями сложения , вычитания и умножения . Сравнение по модулю n обозначается
Круглые скобки означают, что (mod n ) применяется ко всему уравнению, а не только к его правой части (здесь b ).
Это обозначение не следует путать с обозначением b mod n (без круглых скобок), которое относится к операции по модулю , остатку b при делении на n : то есть b mod n обозначает уникальное целое число r такое, что 0 ≤ r < п и р ≡ б (мод п ) .
Отношение конгруэнтности можно переписать как
явно показывая его связь с евклидовым делением . Однако здесь b не обязательно должен быть остатком от деления a на n . Скорее, a ≡ b (mod n ) утверждает, что a и b имеют одинаковый остаток при делении на n . То есть,
где 0 ≤ r < n — общий остаток. Мы восстанавливаем предыдущее соотношение: a − b = kn , вычитая эти два выражения и полагая k = p − q .
По модулю 12 можно утверждать, что:
потому что разница составляет 38 - 14 = 24 = 2 × 12 , кратно 12 . Эквивалентно, 38 и 14 имеют одинаковый остаток 2 при делении на 12 .
Определение соответствия также применимо к отрицательным значениям. Например:
Отношение конгруэнтности удовлетворяет всем условиям отношения эквивалентности :
Если a 1 ≡ b 1 (mod n ) и a 2 ≡ b 2 (mod n ) , или если a ≡ b (mod n ) , то: [1]
Если a ≡ b (mod n ) , то утверждение k a ≡ k b (mod n ) вообще неверно . Однако верно следующее:
Для отмены общих условий у нас действуют следующие правила:
Последнее правило можно использовать для перевода модульной арифметики в деление. Если b делит a , то ( a / b ) mod n = ( a mod bn )/ b .
Модульный мультипликативный обратный определяется следующими правилами:
Мультипликативный обратный x ≡ a −1 (mod n ) может быть эффективно вычислен путем решения уравнения Безу ax + ny = 1 для x , y – с использованием расширенного алгоритма Евклида .
В частности, если p — простое число, то a взаимно просто с p для любого a такого, что 0 < a < p ; таким образом, мультипликативный обратный существует для всех a , которые не конгруэнтны нулю по модулю p .
Некоторые из наиболее продвинутых свойств отношений конгруэнтности следующие:
Отношение конгруэнтности является отношением эквивалентности . Класс эквивалентности по модулю n целого числа a — это набор всех целых чисел вида a + kn , где k — любое целое число. Он называется классом сравнения или классом вычетов по модулю n и может обозначаться как mod n ) , или как a или [ a ] , когда модуль n известен из контекста.
Каждый класс вычетов по модулю n содержит ровно одно целое число в диапазоне 0, ..., n − 1 . Таким образом, эти n целых чисел являются представителями соответствующих классов вычетов.
Обычно легче работать с целыми числами, чем с наборами целых чисел; то есть наиболее часто рассматриваемые представители, а не их классы остатков.
Следовательно, ( a mod n ) обычно обозначает уникальное целое число k такое, что 0 ≤ k < n и k ≡ a (mod n ) ; он называется остатком по модулю n .
В частности, ( a mod n ) = ( b mod n ) эквивалентно a ≡ b (mod n ) , и это объясняет, почему в этом контексте вместо « ≡ » часто используется « = ".
Каждый класс остатков по модулю n может быть представлен любым из его членов, хотя мы обычно представляем каждый класс остатков наименьшим неотрицательным целым числом, принадлежащим этому классу [2] (поскольку это правильный остаток, полученный в результате деления). Любые два члена разных классов вычетов по модулю n не конгруэнтны по модулю n . Более того, каждое целое число принадлежит одному и только одному классу вычетов по модулю n . [3]
Набор целых чисел {0, 1, 2, ..., n − 1} называется системой наименьших вычетов по модулю n . Любой набор из n целых чисел, никакие два из которых не конгруэнтны по модулю n , называется полной системой вычетов по модулю n .
Система наименьших вычетов — это полная система вычетов, а полная система вычетов — это просто набор, содержащий ровно одного представителя каждого класса вычетов по модулю n . [4] Например, система наименьших вычетов по модулю 4 равна {0, 1, 2, 3} . Некоторые другие системы полных остатков по модулю 4 включают:
Некоторые наборы, которые не являются полными системами вычетов по модулю 4:
Учитывая тотент-функцию Эйлера φ ( n ) , любой набор целых чисел φ ( n ) , которые взаимно просты с n и взаимно неконгруэнтны по модулю n , называется приведенной системой вычетов по модулю n . [5] Набор {5, 15}, приведенный выше, например, является примером системы сокращенных вычетов по модулю 4.
Покрывающие системы представляют собой еще один тип системы остатков, который может содержать остатки с разными модулями.
Множество всех классов конгруэнтности по модулю n называется кольцом целых чисел по модулю n , [6] и обозначается , , или . [7] Однако использовать эту запись не рекомендуется, поскольку ее можно спутать с набором n -адических целых чисел . Кольцо имеет фундаментальное значение для различных разделов математики (см. § Приложения ниже).
Для n > 0 имеем
Когда n = 1 , — нулевое кольцо ; когда n = 0 , это не пустое множество ; скорее , он изоморфен , поскольку a 0 = { a } .
Сложение, вычитание и умножение определяются следующими правилами:
Из приведенных выше свойств следует, что с этими операциями кольцо является коммутативным . Например, на ринге есть
как в арифметике для 24-часовых часов.
Обозначение используется потому, что это кольцо является факторкольцом идеала , множества , образованного всеми kn с
Рассматриваемая как группа при добавлении, является циклической группой , и все циклические группы изоморфны с для некоторого n . [8]
Кольцо целых чисел по модулю n является полем тогда и только тогда, когда n простое ( это гарантирует, что каждый ненулевой элемент имеет мультипликативный обратный ). Если n = pk — степень простого числа с k > 1 , то существует единственное (с точностью до изоморфизма) конечное поле с n элементами, которое не изоморфно tp и которое не может быть полем, поскольку имеет делители нуля .
Если n > 1 , обозначает мультипликативную группу целых чисел по модулю n , которые являются обратимыми. Он состоит из классов конгруэнтности an , где a взаимно прост с n ; это именно классы, обладающие мультипликативным обратным. При умножении они образуют абелеву группу ; его порядок равен φ ( n ) , где φ — функция тотента Эйлера.
В чистой математике модульная арифметика является одной из основ теории чисел , затрагивающей почти каждый аспект ее изучения, а также широко используется в теории групп , теории колец , теории узлов и абстрактной алгебре . В прикладной математике он используется в компьютерной алгебре , криптографии , информатике , химии , изобразительном и музыкальном искусстве.
Очень практичным применением является вычисление контрольных сумм в идентификаторах серийных номеров. Например, международный стандартный номер книги (ISBN) использует арифметику по модулю 11 (для 10-значного ISBN) или по модулю 10 (для 13-значного ISBN) для обнаружения ошибок. Аналогичным образом, например, международные номера банковских счетов (IBAN) используют арифметику по модулю 97 для выявления ошибок ввода пользователем номеров банковских счетов. В химии последняя цифра регистрационного номера CAS (уникальный идентификационный номер для каждого химического соединения) является контрольной цифрой , которая рассчитывается путем умножения последней цифры первых двух частей регистрационного номера CAS на 1, предыдущую цифру. умножить на 2, предыдущую цифру умножить на 3 и т. д., сложив все это и вычислив сумму по модулю 10.
В криптографии модульная арифметика непосредственно лежит в основе систем с открытым ключом , таких как RSA и Диффи-Хеллмана , и обеспечивает конечные поля , лежащие в основе эллиптических кривых , и используется во множестве алгоритмов симметричного ключа , включая Advanced Encryption Standard (AES), Международный алгоритм шифрования данных ( ИДЕЯ) и 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 (по модулю 9).
Арифметика по модулю 7 используется в алгоритмах, определяющих день недели для заданной даты. В частности, сравнение Целлера и алгоритм Судного дня широко используют арифметику по модулю 7.
В более общем смысле, модульная арифметика также имеет применение в таких дисциплинах, как право (например, распределение ), экономика (например, теория игр ) и других областях социальных наук , где пропорциональное разделение и распределение ресурсов играет центральную часть анализа.
Поскольку модульная арифметика имеет столь широкий спектр применений, важно знать, насколько сложно решить систему сравнений. Линейная система сравнений может быть решена за полиномиальное время методом исключения Гаусса , подробности см. в теореме о линейном сравнении . Алгоритмы, такие как сокращение Монтгомери , также существуют, позволяющие эффективно выполнять простые арифметические операции, такие как умножение и возведение в степень по модулю n , с большими числами.
Некоторые операции, такие как нахождение дискретного логарифма или квадратичного сравнения, кажутся такими же сложными, как факторизация целых чисел , и поэтому являются отправной точкой для криптографических алгоритмов и шифрования . Эти проблемы могут быть NP-промежуточными .
Решение системы нелинейных модульных арифметических уравнений является NP-полным . [10]
Ниже приведены три достаточно быстрые функции C: две для выполнения модульного умножения и одна для модульного возведения в степень целых чисел без знака длиной не более 63 бит без переполнения переходных операций.
Алгоритм вычисления a ⋅ b (mod 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 ; интервал я ; если ( а >= м ) а %= м ; если ( б >= м ) б %= м ; для ( я знак равно 0 ; я < 64 ; ++ я ) { d = ( d > mp2 ) ? ( d << 1 ) - m : d << 1 ; если ( a & 0x8000000000000000ULL ) d += b ; если ( d >= м ) d -= м ; а <<= 1 ; } Вернуть д ; }
В компьютерных архитектурах, где доступен формат расширенной точности с минимум 64 битами мантиссы (например, тип long double в большинстве компиляторов C x86), следующая процедура выполняется быстрее, чем решение, использующее цикл, благодаря использованию трюка, который: аппаратное обеспечение, умножение с плавающей запятой приводит к сохранению наиболее значимых битов произведения, тогда как целочисленное умножение приводит к сохранению младших значащих битов: [ нужна ссылка ]
uint64_t mul_mod ( uint64_t a , uint64_t b , uint64_t m ) { long double x ; uint64_t c ; int64_t р ; если ( а >= м ) а %= м ; если ( б >= м ) б %= м ; х знак равно а ; с = х * б / м ; r = ( int64_t )( a * b - c * m ) % ( int64_t ) m ; вернуть р < 0 ? р + м : р ; }
Ниже приведена функция C для выполнения модульного возведения в степень, которая использует функцию mul_mod , реализованную выше.
Алгоритмический способ вычисления a b (mod m ) :
uint64_t pow_mod ( uint64_t a , uint64_t b , uint64_t м ) { uint64_t р = м == 1 ? 0 : 1 ; в то время как ( б > 0 ) { если ( б & 1 ) р знак равно mul_mod ( р , а , м ); б = б >> 1 ; а = mul_mod ( а , а , м ); } Вернуть р ; }
Однако для того, чтобы все вышеперечисленные процедуры работали, m не должно превышать 63 бита.
ULL
. См. также раздел 6.4.4 спецификации языка n1570.