Модульная арифметика
В математике — модульная арифметика это система арифметики целых чисел , в которой числа «закручиваются» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был развит Карлом Фридрихом Гауссом в его книге 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).
Конгруэнтность [ править ]
Учитывая целое число m ≥ 1 , называемое модулем , два целых числа a и b называются конгруэнтными по модулю m , если m является делителем их разности; то есть, если существует целое число k такое, что
- а - б знак равно км .
Сравнение по модулю m является отношением сравнения , что означает, что это отношение эквивалентности , совместимое с операциями сложения , вычитания и умножения . Сравнение по модулю m обозначается
- а ≡ б (мод м ) .
Круглые скобки означают, что (mod m ) применяется ко всему уравнению, а не только к его правой части (здесь b ).
Это обозначение не следует путать с обозначением b mod m (без круглых скобок), которое относится к операции по модулю , остатку b при делении на m : то есть b mod m обозначает уникальное целое число r такое, что 0 ≤ r < м и р ≡ б (мод м ) .
Отношение конгруэнтности можно переписать как
- а = км + б ,
явно показывая его связь с евклидовым делением . Однако здесь b не обязательно должен быть остатком от деления a на m . Скорее, a ≡ b (mod m ) утверждает, что a и b имеют одинаковый остаток при делении на m . То есть,
- а = pm + r ,
- б = дм + р ,
где 0 ≤ r < m – общий остаток. Мы восстанавливаем предыдущее соотношение ( a − b = km ), вычитая эти два выражения и устанавливая k = p − q .
Поскольку сравнение по модулю m определяется делимостью на m и поскольку является единицей в кольце целых чисел, число делится на -m m ровно в том случае, если оно делится на -1 . Это означает, что любое ненулевое целое число m можно принять за модуль.
Примеры [ править ]
По модулю 12 можно утверждать, что:
- 38 ≡ 14 (мод. 12)
потому что разница составляет 38 - 14 = 24 = 2 × 12 , кратно 12 . Эквивалентно, 38 и 14 имеют одинаковый остаток 2 при делении на 12 .
Определение соответствия также применимо к отрицательным значениям. Например:
Основные свойства [ править ]
Отношение конгруэнтности удовлетворяет всем условиям отношения эквивалентности :
- Рефлексивность: a ≡ a (mod m )
- Симметрия: a ≡ b (mod m ), если b ≡ a (mod m ) .
- Транзитивность: если a ≡ b (mod m ) и b ≡ c (mod m ) , то a ≡ c (mod m ).
Если a 1 ≡ b 1 (mod m ) и a 2 ≡ b 2 (mod m ) или если a ≡ b (mod m ) , то: [1]
- a + k ≡ b + k (mod m ) для любого целого числа k (совместимость с переводом)
- ka ≡ kb (mod m ) для любого целого числа k (совместимость с масштабированием)
- ka ≡ kb (mod km ) для любого целого k
- a 1 + a 2 ≡ b 1 + b 2 (mod m ) (совместимость со сложением)
- a 1 - a 2 ≡ b 1 - b 2 (mod m ) (совместимость с вычитанием)
- a 1 a 2 ≡ b 1 b 2 (mod m ) (совместимость с умножением)
- а к ≡ б к (mod m ) для любого неотрицательного целого числа k (совместимость с возведением в степень)
- p ( a ) ≡ p ( b ) (mod m ) для любого многочлена p ( x ) с целыми коэффициентами (совместимость с полиномиальной оценкой)
Если a ≡ b (mod m ) , то, как правило, неверно, что k а ≡ к б (мод. м ) . Однако верно следующее:
- Если c ≡ d (mod φ ( m )), где φ — тотент-функция Эйлера , то a с ≡ а д (mod m ) — при условии, что a взаимно просто с m .
Для отмены общих условий у нас действуют следующие правила:
- Если a + k ≡ b + k (mod m ) , где k — любое целое число, то a ≡ b (mod m ) .
- Если ka ≡ kb (mod m ) и k взаимно просто с m , то a ≡ b (mod m ) .
- Если ka ≡ kb (mod km ) и k ≠ 0 , то a ≡ b (mod m ) .
Последнее правило можно использовать для перевода модульной арифметики в деление. Если b делит a , то ( a / b ) mod m = ( a mod bm )/ b .
Модульный мультипликативный обратный определяется следующими правилами:
- Существование: существует целое число, обозначаемое −1 такой, что аа −1 ≡ 1 (mod m ) тогда и только тогда, когда a взаимно просто с m . Это целое число а −1 называется мультипликативным модулем m обратным . модулярным
- Если a ≡ b (mod m ) и a −1 существует, то −1 ≡ б −1 (mod m ) (совместимость с мультипликативным обратным и, если a = b , уникальность по модулю m ).
- Если ax ≡ b (mod m ) и a взаимно просто с m , то решение этого линейного сравнения определяется как x ≡ a −1 б (мод. м ) .
Мультипликативный обратный x ≡ a −1 (mod m ) можно эффективно вычислить, решив уравнение Безу a x + my = 1 для x , y , используя расширенный алгоритм Евклида .
В частности, если p — простое число, то a взаимно просто с p для любого a такого, что 0 < a < p ; таким образом, мультипликативный обратный существует для всех a , которые не конгруэнтны нулю по модулю p .
Расширенные свойства [ править ]
Некоторые из наиболее продвинутых свойств отношений конгруэнтности следующие:
- Маленькая теорема Ферма : если p простое и не делит a , то a р -1 ≡ 1 (против п ) .
- Теорема Эйлера : если a и m взаимно просты, то a φ ( м ) ≡ 1 (mod m ) , где φ — функция тотента Эйлера .
- Простое следствие маленькой теоремы Ферма состоит в том, что если p простое, то a −1 ≡ а р -2 (mod p ) является мультипликативным обратным 0 < a < p . В более общем смысле, согласно теореме Эйлера, если a и m взаимно просты, то a −1 ≡ а φ ( м )−1 (мод. м ) .
- Другое простое следствие состоит в том, что если a ≡ b (mod φ ( m )) , где φ — тотент-функция Эйлера, то k а ≡ к б (mod m ) при условии, что k взаимно просто с m .
- Теорема Вильсона : p простое тогда и только тогда, когда ( p − 1)! ≡ -1 (мод п ) .
- Китайская теорема об остатках : для любых a , b и взаимно простых m , n существует единственный x (mod mn ) такой, что x ≡ a (mod m ) и x ≡ b (mod n ) . В самом деле, x ≡ bm n −1 м + м −1 n (mod mn ) , где m n −1 является обратным к m по модулю n и n m −1 является обратным n по модулю m .
- Теорема Лагранжа : сравнение f ( x ) ≡ 0 (mod p ) , где p — простое число, и f ( x ) = a 0 x м + ... + a m — многочлен с целыми коэффициентами такой, что a 0 ≠ 0 (mod p ) имеет не более m корней.
- Примитивный корень по модулю m : число g является примитивным корнем по модулю m , если для каждого целого числа, взаимно простого с m , существует целое число k такое, что g к ≡ а (мод м ) . Примитивный корень по модулю m существует тогда и только тогда, когда m равно 2, 4, p к или 2 п. к , где p — нечетное простое число, а k — целое положительное число. Если примитивный корень по модулю m существует, то таких примитивных корней ровно φ ( φ ( m )) , где φ — тотент-функция Эйлера.
- Квадратичный вычет : Целое число a является квадратичным вычетом по модулю m , если существует целое число x такое, что x 2 ≡ а (мод м ) . Критерий Эйлера утверждает, что если p — нечетное простое число и a не кратно p , то a — квадратичный вычет по модулю p тогда и только тогда, когда
- а ( п −1)/2 ≡ 1 (против п ) .
Классы конгруэнтности [ править ]
Отношение конгруэнтности является отношением эквивалентности . Класс эквивалентности по модулю m целого числа a — это набор всех целых чисел вида a + km , где k — любое целое число. Он называется классом сравнения или вычетов модуля m , m и может обозначаться как ( mod ) ] когда или как a или [ a классом модуль m известен из контекста.
Каждый класс вычетов по модулю m содержит ровно одно целое число в диапазоне . Таким образом, эти целые числа являются представителями соответствующих классов вычетов.
Обычно легче работать с целыми числами, чем с наборами целых чисел; то есть наиболее часто рассматриваемые представители, а не их классы остатков.
Следовательно, ( a mod m ) обычно обозначает уникальное целое число k такое, что 0 ≤ k < m и k ≡ a (mod m ) ; называется остатком по модулю m он .
В частности, ( a mod m ) = ( b mod m ) эквивалентно a ≡ b (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 включают:
- {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 неконгруэнтных класса вычетов.
Системы пониженного остатка [ править ]
Учитывая тотент-функцию Эйлера φ ( m ) , любой набор целых чисел φ ( m ) , которые являются относительно простыми с m и взаимно неконгруэнтными по модулю m, называется приведенной системой вычетов по модулю m . [5] Например, набор {5, 15} , приведенный выше, является примером системы сокращенных вычетов по модулю 4.
Системы покрытия [ править ]
Покрывающие системы представляют собой еще один тип системы остатков, который может содержать остатки с разными модулями.
Целые числа по модулю m [ править ]
Примечание. В контексте этого параграфа модуль m почти всегда принимается положительным.
Множество всех классов конгруэнтности по модулю m называется кольцом целых чисел по модулю m , [6] и обозначается , , или . [7] Обозначения однако не рекомендуется, поскольку его можно спутать с набором m -адических целых чисел . Кольцо является фундаментальным для различных разделов математики (см. § Приложения ниже).
Для m > 0 имеем
Когда m = 1 , – нулевое кольцо ; когда м = 0 , не является пустым множеством ; , он изоморфен скорее , поскольку а 0 = { а } .
Сложение, вычитание и умножение определены на по следующим правилам:
Приведенные выше свойства подразумевают, что при выполнении этих операций является коммутативным кольцом . Например, на ринге , у одного есть
как в арифметике для 24-часовых часов.
Обозначения используется потому, что это кольцо факторкольцом является по идеалу , набор, образованный всеми км с
Рассматривается как группа в стадии добавления, является циклической группой , и все циклические группы изоморфны для некоторых м . [8]
Кольцо целых чисел по модулю m является полем тогда и только тогда, когда ( это m простое гарантирует, что каждый ненулевой элемент имеет мультипликативный обратный ). Если м = р к — простая степень с k > 1 , существует единственное (с точностью до изоморфизма) конечное поле с m элементами, что не изоморфно , которое не может быть полем, поскольку имеет делители нуля .
Если m > 1 , обозначает мультипликативную группу целых чисел по модулю m обратимых классов конгруэнтности am . Он состоит из , где a взаимно просто с m ; это именно классы, обладающие мультипликативным обратным. они образуют абелеву группу При умножении ; его порядок равен φ ( m ) , где φ — функция тотента Эйлера.
Расширение до действительных чисел [ править ]
Этот раздел пуст. Вы можете помочь, добавив к нему . ( июль 2022 г. ) |
Приложения [ править ]
В чистой математике модульная арифметика является одной из основ теории чисел , затрагивающей почти каждый аспект ее изучения, а также широко используется в теории групп , теории колец , теории узлов и абстрактной алгебре . В прикладной математике он используется в компьютерной алгебре , криптографии , информатике , химии , изобразительном и музыкальном искусстве.
Очень практичным применением является вычисление контрольных сумм в идентификаторах серийных номеров. Например, международный стандартный номер книги (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 микрокомпьютере с использованием всего лишь одной четверти целочисленной точности, используемой суперкомпьютером 6600, CDC чтобы опровергнуть ее двумя десятилетиями ранее. через поиск методом перебора . [9]
В информатике модульная арифметика часто применяется в побитовых операциях фиксированной ширины и других операциях, включающих циклические структуры данных . Операция по модулю, реализованная во многих языках программирования и калькуляторах , представляет собой применение модульной арифметики, которая часто используется в этом контексте. Логический оператор XOR суммирует 2 бита по модулю 2.
Использование длинного деления для преобразования дроби в повторяющуюся десятичную дробь с любой базой b эквивалентно модульному умножению b по модулю знаменателя. Например, для десятичной дроби b = 10.
В музыке арифметика по модулю 12 используется при рассмотрении системы двенадцати тонов равной темперации , где имеет место октавная и энгармоническая эквивалентность (т. е. высоты звука в соотношении 1:2 или 2:1 эквивалентны, а до диез - считается тем же, что и ре- бемоль ).
Метод выбрасывания девяток предлагает быструю проверку вычислений десятичной арифметики, выполняемых вручную. Он основан на модульной арифметике по модулю 9 и, в частности, на ключевом свойстве: 10 ≡ 1 (по модулю 9).
Арифметика по модулю 7 используется в алгоритмах, определяющих день недели для заданной даты. В частности, сравнение Целлера и алгоритм Судного дня широко используют арифметику по модулю 7.
В более общем смысле, модульная арифметика также имеет применение в таких дисциплинах, как право (например, распределение ), экономика (например, теория игр ) и других областях социальных наук , где пропорциональное разделение и распределение ресурсов играет центральную часть анализа.
Вычислительная сложность [ править ]
Поскольку модульная арифметика имеет столь широкий спектр применений, важно знать, насколько сложно решить систему сравнений. Линейная система сравнений может быть решена за полиномиальное время методом исключения Гаусса , подробности см. в теореме о линейном сравнении . Алгоритмы, такие как сокращение Монтгомери простые арифметические операции, такие как умножение и возведение в степень по модулю m , также существуют, чтобы позволить эффективно выполнять , с большими числами.
Некоторые операции, такие как нахождение дискретного логарифма или квадратичного сравнения, кажутся такими же сложными, как факторизация целых чисел , и поэтому являются отправной точкой для криптографических алгоритмов и шифрования . Эти проблемы могут быть NP-промежуточными .
Решение системы нелинейных модульных арифметических уравнений является NP-полным . [10]
Пример реализации [ править ]
Возможно, этот раздел содержит оригинальные исследования . ( Май 2020 г. ) |
Ниже приведены три достаточно быстрые функции 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;
int i;
if (a >= m) a %= m;
if (b >= m) b %= m;
for (i = 0; i < 64; ++i) {
d = (d > mp2) ? (d << 1) - m : d << 1;
if (a & 0x8000000000000000ULL) d += b;
if (d >= m) d -= m;
a <<= 1;
}
return d;
}
В компьютерных архитектурах, где расширенный формат точности доступен с минимум 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;
if (a >= m) a %= m;
if (b >= m) b %= m;
x = a;
c = x * b / m;
r = (int64_t)(a * b - c * m) % (int64_t)m;
return r < 0 ? r + m : r;
}
Ниже приведена функция C для выполнения модульного возведения в степень, которая использует функцию mul_mod , реализованную выше.
Алгоритмический способ вычисления б (мод. м ) :
uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m) {
uint64_t r = m == 1 ? 0 : 1;
while (b > 0) {
if (b & 1) r = mul_mod(r, a, m);
b = b >> 1;
a = mul_mod(a, a, m);
}
return r;
}
Однако для того, чтобы все вышеперечисленные процедуры работали, m не должно превышать 63 бита.
См. также [ править ]
- Булево кольцо
- Круговой буфер
- Отдел (математика)
- Конечное поле
- Легендарный символ
- Модульное возведение в степень
- По модулю (математика)
- Мультипликативная группа целых чисел по модулю n
- Период Пизано (последовательности Фибоначчи по модулю n )
- Примитивный корень по модулю n
- Квадратичная взаимность
- Квадратичный остаток
- Рациональная реконструкция (математика)
- Система пониженного остатка
- Арифметика серийных номеров (частный случай модульной арифметики)
- Двухэлементная булева алгебра
- Темы, относящиеся к теории групп, лежащей в основе модульной арифметики:
- Другие важные теоремы, относящиеся к модульной арифметике:
- Теорема Кармайкла
- Китайская теорема об остатках
- Теорема Эйлера
- Малая теорема Ферма (частный случай теоремы Эйлера)
- Теорема Лагранжа
- Лемма Туэ
Примечания [ править ]
- ^ Шандор Лехочки; Ричард Руски (2006). Дэвид Патрик (ред.). Искусство решения проблем . Том. 1 (7-е изд.). Компания «АоПС Инкорпорейтед». п. 44. ИСБН 0977304566 .
- ^ Вайсштейн, Эрик В. «Модульная арифметика» . Вольфрам Математический мир . Архивировано из оригинала 14 июля 2023 г. Проверено 12 августа 2020 г.
- ^ Петтофреззо и Биркит (1970 , стр. 90)
- ^ Лонг (1972 , стр. 78)
- ^ Лонг (1972 , стр. 85)
- ^ Это кольцо , как показано ниже.
- ^ «2.3: Целые числа по модулю n» . Математика LibreTexts . 16 ноября 2013 г. Архивировано из оригинала 19 апреля 2021 г. Проверено 12 августа 2020 г.
- ^ Сенгадир Т., Дискретная математика и комбинаторика , с. 293, в Google Книгах.
- ^ «Гипотеза Эйлера о сумме степеней» . Rosettacode.org . Архивировано из оригинала 26 марта 2023 г. Проверено 11 ноября 2020 г.
- ^ Гэри, MR; Джонсон, DS (1979). Компьютеры и трудноразрешимые проблемы. Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0716710447 .
- ^ Этот код использует литеральную нотацию C для беззнаковых длинных шестнадцатеричных чисел, которые заканчиваются на
ULL
. См. также раздел 6.4.4 спецификации языка n1570. Архивировано 29 марта 2018 г. на Wayback Machine .
Ссылки [ править ]
- Джон Л. Берггрен. «модульная арифметика» . Британская энциклопедия .
- Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Тексты для студентов по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3 , МР 0434929 , Збл 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). Элементы теории чисел . Энглвудские скалы: Прентис-холл . ISBN 9780132683005 . LCCN 71081766 .
- Сенгадир, Т. (2009). Дискретная математика и комбинаторика . Ченнаи, Индия: Pearson Education India. ISBN 978-81-317-1405-8 . OCLC 778356123 .
Внешние ссылки [ править ]
- «Конгруэнтность» , Математическая энциклопедия , EMS Press , 2001 [1994]
- В этой статье о модульном искусстве можно узнать больше о применении модульной арифметики в искусстве.
- Статья . о модульной арифметике на вики GIMPS
- Модульная арифметика и шаблоны сложения и таблицы умножения