В математике модульная арифметика представляет собой систему расчета для целых чисел, при помощи которой они «переворачиваются» при достижении определенного значения - модуля (или множественного числа оных). Современный подход к этому виду науки был развит Карлом Фридрихом Гауссом в его книге Disquisitiones Arithmeticae, опубликованной в 1801 году. Этим методом очень любят пользоваться специалисты по информатике, поскольку это очень интересно и открывает определенные новые возможности в операциях с числами.
Суть
Вам будет интересно:Клубов Александр Федорович: биография, боевые вылеты, награды, дата и причина смерти
Поскольку число часов начинается заново после того, как оно достигает 12, это арифметическое по модулю 12. Согласно приведенному ниже определению 12 соответствует не только 12, но и 0, поэтому можно также назвать время, называемое «12:00». «0:00». Ведь 12 совпадает с 0 по модулю 12.
Модульная арифметика может обрабатываться математически, путем введения конгруэнтного отношения к целым числам, которое совместимо с операциями над целыми числами: сложение, вычитание и умножение. Для положительного целого числа n два числа a и b называются конгруэнтными по модулю n, если их разность a - b кратна n (то есть, если существует целое число k такое, что a - b = kn).
Вам будет интересно:Образование звезды: основные этапы и условия
Вычеты
В теоретической математике модульная арифметика является одной из основ теории чисел, затрагивающей почти все аспекты ее изучения, а также широко используется в теории групп, колец, узлов и абстрактной алгебре. В области прикладной математики она используется в компьютерной алгебре, криптографии, информатике, химии, изобразительном и в музыкальном искусстве.
Практика
Очень практичным применением является вычисление контрольных сумм в идентификаторах серийных номеров. Например некоторые общепринятые стандарты книг используют арифметику по модулю 11 (если выпущена до 1 января 2007 г.) или по модулю 10 (если выпущена до или после 1 января 2007 г.). Аналогичным образом, например, в Международных номерах банковских счетов (IBAN). Здесь используется арифметика по модулю 97 для выявления ошибок ввода пользователем в номерах банковских счетов.
Вам будет интересно:Клубов Александр Федорович: биография, боевые вылеты, награды, дата и причина смерти
В химии последняя цифра регистрационного номера CAS (уникальный идентификационный номер для каждого химического соединения) является контрольной цифрой. Она рассчитывается путем взятия последней цифры из первых двух частей регистрационного номера CAS, умноженной на 1, предыдущую цифру 2 раза, предыдущая цифра 3 раза и т. д., складывая все это и вычисляя сумму по модулю 10.
Что такое криптография? Дело в том, что она имеет весьма сильную связь с обсуждаемой темой. В криптографии законы модульной арифметики, непосредственно, лежат в основе систем с открытым ключом, таких как RSA и Диффи-Хелльман. Здесь она предоставляет конечные поля, которые лежат в основе эллиптических кривых. Используется в различных алгоритмах симметричного ключа, включая Advanced Encryption Standard (AES), Международный алгоритм шифрования данных и RC4.
Применение
Этот способ применяется в тех областях, где нужно читать цифры. Его разработали математики, а пользуются им все, особенно специалисты по информатике. Это хорошо описано в книгах вроде "Модульная арифметика для чайников". Впрочем, ряд специалистов рекомендует не воспринимать такую литературу всерьез.
В информатике модульная арифметика часто применяется в побитовых и других операциях, включающих циклические структуры данных фиксированной ширины. Ее очень любят использовать аналитики. Операция по модулю реализована во многих языках программирования и калькуляторах. В данном случае она является одним из примеров такого применения. Сравнение по модулю, деление с остатком и прочие приемы также применяются в программировании.
В музыке арифметика по модулю 12 используется при рассмотрении системы равного темперамента из двенадцати тонов, в которой происходит эквивалентность октавы и энгармоники. Иными словами, тональности в соотношении 1-2 или 2-1 эквивалентны. В музыке и других гуманитарных дисциплинах арифметика играет довольно значимую роль, но в учебниках информатики об этом обычно не пишут.
Вам будет интересно:Мохенджо-Даро и Хараппа: история, оставленный город, древняя цивилизация и теории об исчезновении
Метод приведения девяток
Метод приведения девяток предлагает быструю проверку десятичных арифметических вычислений, выполненных вручную. Он основан на модульной арифметике по модулю 9 и, в частности, на решающем свойстве 10 10 1.
существуют и другие примеры. Арифметическое по модулю 7 используется в алгоритмах, которые определяют день недели для конкретной даты. В частности, конгруэнтность Целлера и алгоритм "Судного дня" интенсивно используют арифметику по модулю 7.
Иные области применения
О модульной арифметике в криптографии уже было сказано. В этой сфере она попросту незаменима. В более общем смысле, модульная арифметика также находит применение в таких дисциплинах, как право, экономика (например, теория игр) и другие области социальных наук. Иными словами, там, где пропорциональное разделение и распределение ресурсов играет главную роль.
Поскольку модульная арифметика имеет такой широкий спектр применений, важно знать, насколько сложно решить систему сравнений. Линейная система конгруэнций может быть решена за полиномиальное время в форме исключения Гаусса. Подробнее это описывает теорема о линейной конгруэнции. Алгоритмы, такие как редукция Монтгомери, также существуют, чтобы позволить эффективно выполнять простые арифметические операции. Например, умножение и возведение в степень по модулю n, для больших чисел. Это очень важно знать для понимания того, что такое криптография. Ведь в ней как раз работают с подобными операциями.
Конгруэнция
Некоторые операции, такие как поиск дискретного логарифма или квадратичной конгруэнции, кажутся такими же сложными, как целочисленная факторизация, и, таким образом, являются отправной точкой для криптографических алгоритмов и шифрования. Эти проблемы могут быть NP-промежуточными.
Примеры
Ниже приведены три достаточно быстрые функции C - две для выполнения модульного умножения и одна для возведения в модулярные числа для целых чисел без знака, не превышающих 63 бита, без переполнения переходных операций.
Вскоре после обнаружения целых чисел (1, 2, 3, 4, 5 ...) становится очевидным, что они делятся на две группы:
- Четный: делится на 2 (0, 2, 4, 6 ..).
- Нечетное: не делится на 2 (1, 3, 5, 7…).
Почему это различие важно? Это начало абстракции. Мы замечаем свойства числа (например, четное или нечетное), а не только само число («37»).
Это позволяет нам исследовать математику на более глубоком уровне и находить отношения между типами чисел, а не конкретными.
Свойства числа
Быть «тройкой» - это просто еще одно свойство числа. Возможно, не так сразу полезно, как четное/нечетное, но оно есть. Мы можем создать правила типа «тринадцать х три вена = тринадцать» и так далее. Но это сводит с ума. Мы не можем делать новые слова все время.
Операция по модулю (сокращенно mod или «%» во многих языках программирования) является остатком при делении. Например, «5 mod 3 = 2», что означает 2 - остаток, когда вы делите 5 на 3.
При преобразовании повседневных терминов в математику «четное число» - это то, где оно равно «0 mod 2», то есть остаток равен 0 при делении на 2. Нечетное число равно «1 mod 2» (имеет остаток 1).
Четные и нечетные числа
Что такое четный х четный х нечетный х нечетный? Ну, это 0 x 0 x 1 x 1 = 0. На самом деле, вы можете видеть, умножается ли где-либо четное число, где весь результат будет равен нулю.
Хитрость модульной математики в том, что мы уже использовали ее для хранения времени - иногда ее называют «арифметикой часов».
Например: 7:00 (утра/вечера - не имеет значения). Где будет часовая стрелка через 7 часов?
Модуляции
(7 + 7) mod 12 = (14) mod 12 = 2 mod 12 [2 - это остаток, когда 14 делится на 12. Уравнение 14 mod 12 = 2 mod 12 означает, что 14 часов и 2 часа выглядят одинаково на 12-часовых часах. Они являются конгруэнтными, обозначенными знаком тройного равенства: 14 ≡ 2 mod 12.
Другой пример: сейчас 8:00. Где будет большая стрелка через 25 часов?
Вместо добавления 25 к 8, вы можете понять, что 25 часов - это просто «1 день + 1 час». Ответ прост. Итак, часы закончатся на 1 час вперед - в 9:00.
(8 + 25) мод 12 ≡ (8) мод 12 + (25) мод 12 ≡ (8) мод 12 + (1) мод 12 ≡ 9 мод 12. Вы интуитивно конвертировали 25 в 1 и добавили это к 8.
Используя часы в качестве аналогии, мы можем выяснить, работают ли правила модульной арифметики, а они работают.
Сложение/Вычитание
Допустим, два раза выглядят одинаково на наших часах («2:00» и «14:00»). Если мы добавим одинаковые х часов к обоим, что произойдет? Ну, они меняются на ту же сумму на часах! 2:00 + 5 часов ≡ 14:00 + 5 часов - оба покажут 7:00.
Зачем? Мы можем просто добавить 5 к 2 остаткам, которые оба имеют, и они продвигаются одинаково. Для всех конгруэнтных чисел (2 и 14) сложение и вычитание имеют одинаковый результат.
Труднее понять, остается ли умножение таким же. Если 14 ≡ 2 (мод 12), можем ли мы умножить оба числа и получить одинаковый результат? Давайте посмотрим, что произойдет, когда мы умножим на 3.
Ну, 2:00 * 3 × 6:00. Но что такое 14:00 * 3?
Помните, 14 = 12 + 2. Итак, мы можем сказать,
14 * 3 = (12 + 2) * 3 = (12 * 3) + (2 * 3)
Первую часть (12 * 3) можно игнорировать! Переполнение 12 часов, которое несет 14, просто повторяется несколько раз. Но кого это волнует? В любом случае мы игнорируем переполнение.
Умножение
При умножении имеет значение только остаток, то есть те же 2 часа для 14:00 и 2:00. Интуитивно понятно, что именно так я вижу, что умножение не меняет отношения с модульной математикой (вы можете умножить обе стороны модульного отношения и получить один и тот же результат).
Мы делаем это интуитивно, но приятно дать ему имя. У вас есть рейс, прибывающий в 3 часа дня. Он задерживается на 14 часов. Во сколько он приземлится?
14 ≡ 2 мод 12. Так что, стоит думать об этом как 2 часа, поэтому самолет приземлиться 5 часов утра. Решение простое: 3 + 2 = 5 утра. Это немного сложнее, чем простая операция по модулю, но принцип тот же.