В математике , модульные арифметическое представляет собой система арифметических для целых чисел , где число «обтекать» при достижении определенной величины, называется модулем . Современный подход к модульной арифметике был разработан Карлом Фридрихом Гауссом в его книге 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-часовом формате.
Конгруэнтность [ править ]
Для целого числа n > 1 , называемого модулем , два целых числа называются конгруэнтными по модулю n , если n является делителем их разности (т. Е. Если существует целое число k такое, что a - b = kn ).
Конгруэнтность по модулю n - это отношение конгруэнтности , означающее, что это отношение эквивалентности , совместимое с операциями сложения , вычитания и умножения . Сравнение по модулю n обозначается:
Скобки означают, что (mod n ) применяется ко всему уравнению, а не только к правой части (здесь b ). Это обозначение не следует путать с обозначением b mod n (без скобок), которое относится к операции по модулю . В самом деле, b mod n обозначает уникальное целое число a такое, что 0 ≤ a < n и (то есть остаток от деления на [1] ).
Отношение конгруэнтности можно переписать как
явно показывая его связь с евклидовым делением . Однако b здесь не обязательно должно быть остатком от деления a на n . Вместо этого утверждение a ≡ b (mod n ) утверждает, что a и b имеют одинаковый остаток при делении на n . То есть,
где 0 ≤ r < n - общий остаток. Вычитая эти два выражения, мы восстанавливаем предыдущее соотношение:
положив k = p - q .
Примеры [ править ]
По модулю 12 можно утверждать, что:
потому что 38 - 14 = 24 , что кратно 12. Другой способ выразить это - сказать, что и 38, и 14 имеют одинаковый остаток 2 при делении на 12.
Определение конгруэнтности также применимо к отрицательным значениям. Например:
Свойства [ править ]
Отношение конгруэнтности удовлетворяет всем условиям отношения эквивалентности :
- Рефлексивность: 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 1 ≡ b 1 (mod n ) и a 2 ≡ b 2 (mod n ), или если a ≡ b (mod n ), то:
- a + k ≡ b + k (mod n ) для любого целого k (совместимость с переводом)
- ka ≡ kb (mod n ) для любого целого k (совместимость с масштабированием)
- a 1 + a 2 ≡ b 1 + b 2 (mod n ) (совместимость с сложением)
- a 1 - a 2 ≡ b 1 - b 2 (mod n ) (совместимость с вычитанием)
- a 1 a 2 ≡ b 1 b 2 (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 ( по модулю п ) может быть эффективно вычислены путем решения уравнения Беза для -Использования расширенного алгоритма Евклида .
В частности, если 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 −1 ≡ a p - 2 (mod p ) является мультипликативным обратным к 0 < a < p . В более общем смысле, из теоремы Эйлера, если a и n взаимно просты, то a −1 ≡ 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 −1 является обратным к mпо модулю n и n m −1 является обратным к n по модулю m .
- Теорема Лагранжа : сравнение f ( x ) ≡ 0 (mod p ) , где p простое, а f ( x ) = a 0 x n + ... + a n - многочлен с целыми коэффициентами, такой что a 0 ≠ 0 (mod p ) , имеет не более n корней.
- Первообразный корень : Число г является первообразным корнем по модулю п , если для всякого целого числа в копервичном к п , существует целое число к такому , что г к ≡ ( по модулю п ) . Примитивный корень по модулю n существует тогда и только тогда, когда n равно 2, 4, p k или 2 p k , где p - нечетное простое число, а k - положительное целое число. Если первообразный корень по модулю n существует, то существует ровно φ( φ ( n )) такие первообразные корни, где φ - функция Эйлера.
- Квадратичный вычет : целое число a является квадратичным вычетом по модулю n , если существует целое число x такое, что x 2 ≡ a (mod n ) . Критерий Эйлера утверждает, что если p - нечетное простое число и a не делится на p , то a является квадратичным вычетом по модулю p тогда и только тогда, когда
Классы конгруэнтности [ редактировать ]
Как и любое отношение конгруэнтности, сравнение по модулю n является отношением эквивалентности , а класс эквивалентности целого числа a , обозначенного a n , - это множество {…, a - 2 n , a - n , a , a + n , a + 2 п ,…} . Этот набор, состоящий из всех целых чисел конгруэнтных , чтобы в по модулю п , называется класс конгруэнции , класс вычетов , или просто остатокцелого числа a по модулю n . Когда модуль 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.
Целые числа по модулю n [ править ]
Множество всех классов конгруэнтных целых чисел для модуля п называется кольцо целых чисел по модулю п , [6] и обозначается , или . [1] [7] Нотация , однако, не рекомендуется, поскольку ее можно спутать с набором n -адических целых чисел . Кольцо является фундаментальным для различных разделов математики (см. § Приложения ниже).
Набор определяется для n > 0 как:
(При п = 0 , не является пустым множеством , а, скорее, она изоморфна к , так как 0 = { } .)
Мы определяем сложение, вычитание и умножение по следующим правилам:
Для проверки правильности этого определения используются свойства, приведенные ранее.
Таким образом, становится коммутативным кольцом . Например, в кольце мы имеем
как в арифметике для 24-часовых часов.
Мы используем обозначения , потому что это фактор - кольцо из по идеалу , набор , содержащий все целые числа , делящиеся на п , где является одноточечное множество {0} . Таким образом , это поле , когда это максимальный идеал (то есть, когда п простой).
Его также можно построить из группы только с помощью операции сложения. Класс вычетов a n - это смежный класс группы a в фактор-группе , циклической группе . [8]
Вместо исключения особого случая n = 0 более полезно включить (который, как упоминалось ранее, изоморфен кольцу целых чисел). На самом деле, это включение полезно при обсуждении характеристики в виде кольца .
Кольцо целых чисел по модулю п является конечным полем тогда и только тогда , когда п является простым (это гарантирует , что каждый ненулевой элемент имеет мультипликативную обратный ). Если - степень простого числа с k > 1, существует единственное (с точностью до изоморфизма) конечное поле с n элементами, но это не так , которое не может быть полем, потому что оно имеет делители нуля .
Мультипликативная подгруппа целых чисел по модулю п обозначается . Он состоит из (где a взаимно просто с n ), которые являются в точности классами, обладающими мультипликативным обратным. Это образует коммутативную группу относительно умножения с порядком .
Приложения [ править ]
В теоретической математике, модульная арифметика одна из основ теории чисел , затрагивая почти каждый аспект его исследования, и он также широко используется в теории групп , теории колец , теории узлов и абстрактной алгебры . В прикладной математике он используется в компьютерной алгебре , криптографии , информатике , химии, а также в изобразительном и музыкальном искусстве.
Очень практичное приложение - вычисление контрольных сумм в идентификаторах серийных номеров. Например, Международный стандартный номер книги (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 используется при рассмотрении системы двенадцатитонной одинаковой темперации , в которой происходит октавная и энгармоническая эквивалентность (т. Е. Высота звука в соотношении 1 or2 или 2∶1 эквивалентна, а до- диез - считается так же, как D- бемоль ).
Метод исключения девяток предлагает быструю проверку десятичных арифметических вычислений, выполняемых вручную. Он основан на модульной арифметике по модулю 9 и, в частности, на ключевом свойстве 10 ≡ 1 (mod 9).
Арифметика по модулю 7 используется в алгоритмах, определяющих день недели для заданной даты. В частности, сравнение Зеллера и алгоритм Судного дня широко используют арифметику по модулю 7.
В более общем плане модульная арифметика также применяется в таких дисциплинах, как право (например, распределение ), экономика (например, теория игр ) и других областях социальных наук , где пропорциональное разделение и распределение ресурсов играет центральную часть анализа.
Вычислительная сложность [ править ]
Поскольку модульная арифметика имеет такой широкий спектр приложений, важно знать, насколько сложно решить систему сравнений. Линейная система сравнений может быть решена за полиномиальное время с помощью метода исключения Гаусса , подробности см. В теореме о линейном сравнении . Алгоритмы, такие как редукция по Монтгомери , также существуют, чтобы позволить простым арифметическим операциям, таким как умножение и возведение в степень по модулю n , эффективно выполняться над большими числами.
Некоторые операции, такие как нахождение дискретного логарифма или квадратичного сравнения, кажутся такими же сложными, как целочисленная факторизация, и поэтому являются отправной точкой для криптографических алгоритмов и шифрования . Эти проблемы могут быть NP-промежуточными .
Решение системы нелинейных модулярных арифметических уравнений является NP-полным . [10]
Примеры реализации [ править ]
Этот раздел, возможно, содержит оригинальные исследования . Май 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( |
Ниже приведены три достаточно быстрые функции C, две для выполнения модульного умножения и одна для модульного возведения в степень для целых чисел без знака, не превышающих 63 бит, без переполнения переходных операций.
Алгоритмический способ вычисления : [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 .
Алгоритмический способ вычисления :
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 бит.
См. Также [ править ]
- Логическое кольцо
- Круглый буфер
- Отдел (математика)
- Конечное поле
- Символ Лежандра
- Модульное возведение в степень
- Modulo (математика)
- Мультипликативная группа целых чисел по модулю n
- Период Пизано (последовательности Фибоначчи по модулю n )
- Примитивный корень по модулю n
- Квадратичная взаимность
- Квадратичный остаток
- Рациональная реконструкция (математика)
- Система пониженного остатка
- Арифметика серийных номеров (частный случай модульной арифметики)
- Двухэлементная булева алгебра
- Темы, относящиеся к теории групп, лежащей в основе модульной арифметики:
- Циклическая группа
- Мультипликативная группа целых чисел по модулю n
- Другие важные теоремы, относящиеся к модульной арифметике:
- Теорема Кармайкла
- Китайская теорема об остатках
- Теорема Эйлера
- Малая теорема Ферма (частный случай теоремы Эйлера)
- Теорема Лагранжа
- Лемма Туэ
Заметки [ править ]
- ^ a b «Исчерпывающий список символов алгебры» . Математическое хранилище . 2020-03-25 . Проверено 12 августа 2020 .
- ^ Вайсштейн, Эрик В. «Модульная арифметика» . mathworld.wolfram.com . Проверено 12 августа 2020 .
- ^ Pettofrezzo & Byrkit (1970 , стр. 90)
- ^ Длинный (1972 , стр.78)
- ^ Длинный (1972 , стр. 85)
- ^ Это кольцо , как показано ниже.
- ^ "2.3: Целые числа по модулю n" . Математика LibreTexts . 2013-11-16 . Проверено 12 августа 2020 .
- ^ Сенгадир Т., Дискретная математика и комбинаторика , с. 293, в Google Книгах
- ^ "Гипотеза Эйлера о сумме степеней" . rosettacode.org . Проверено 11 ноября 2020 .
- ^ Garey, MR; Джонсон, Д.С. (1979). Компьютеры и неразрешимость, руководство по теории NP-полноты . WH Freeman. ISBN 0716710447.
- ^ В этом коде используется буквальная нотация C для длинных длинных шестнадцатеричных чисел без знака, которые заканчиваются на
ULL
. См. Также раздел 6.4.4 спецификации языка n1570 .
Ссылки [ править ]
- Джон Л. Берггрен. «модульная арифметика» . Британская энциклопедия .
- Апостол, Том М. (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
- Модульная арифметика и шаблоны в таблицах сложения и умножения