Jump to content

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

Для измерения времени в этих часах используется арифметика по модулю 12. Прибавление 4 часов к 9 часам дает 1 час, поскольку 13 соответствует 1 по модулю 12.

В математике модульная арифметика это система арифметики целых чисел , в которой числа «закручиваются» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был развит Карлом Фридрихом Гауссом в его книге 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 а к б (мод. м ) . Однако верно следующее:

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

  • Если 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 ) , где φ функция тотента Эйлера.

Расширение до действительных чисел [ править ]

Приложения [ править ]

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

Очень практичным применением является вычисление контрольных сумм в идентификаторах серийных номеров. Например, международный стандартный номер книги (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]

Пример реализации [ править ]

Ниже приведены три достаточно быстрые функции 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 бита.

См. также [ править ]

Примечания [ править ]

  1. ^ Шандор Лехочки; Ричард Руски (2006). Дэвид Патрик (ред.). Искусство решения проблем . Том. 1 (7-е изд.). Компания «АоПС Инкорпорейтед». п. 44. ИСБН  0977304566 .
  2. ^ Вайсштейн, Эрик В. «Модульная арифметика» . Вольфрам Математический мир . Архивировано из оригинала 14 июля 2023 г. Проверено 12 августа 2020 г.
  3. ^ Петтофреззо и Биркит (1970 , стр. 90)
  4. ^ Лонг (1972 , стр. 78)
  5. ^ Лонг (1972 , стр. 85)
  6. ^ Это кольцо , как показано ниже.
  7. ^ «2.3: Целые числа по модулю n» . Математика LibreTexts . 16 ноября 2013 г. Архивировано из оригинала 19 апреля 2021 г. Проверено 12 августа 2020 г.
  8. ^ Сенгадир Т., Дискретная математика и комбинаторика , с. 293, в Google Книгах.
  9. ^ «Гипотеза Эйлера о сумме степеней» . Rosettacode.org . Архивировано из оригинала 26 марта 2023 г. Проверено 11 ноября 2020 г.
  10. ^ Гэри, MR; Джонсон, DS (1979). Компьютеры и трудноразрешимые проблемы. Руководство по теории NP-полноты . У. Х. Фриман. ISBN  0716710447 .
  11. ^ Этот код использует литеральную нотацию C для беззнаковых длинных шестнадцатеричных чисел, которые заканчиваются на ULL. См. также раздел 6.4.4 спецификации языка n1570. Архивировано 29 марта 2018 г. на Wayback Machine .

Ссылки [ править ]

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 84b06dec8ba97994078c5fba0a39a4c2__1715799300
URL1:https://arc.ask3.ru/arc/aa/84/c2/84b06dec8ba97994078c5fba0a39a4c2.html
Заголовок, (Title) документа по адресу, URL1:
Modular arithmetic - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)