Модульный мультипликативный обратный

Концепция модульной арифметики

В математике , особенно в области арифметики , модульное мультипликативное обратное целое число a представляет собой целое число x такое, что произведение ax конгруэнтно 1 относительно модуля m . ^[1] В стандартных обозначениях модульной арифметики это сравнение записывается как

${\displaystyle ax\equiv 1{\pmod {m}},}$

это сокращенный способ записи утверждения о том, что m делит (нацело) количество ax − 1 , или, другими словами, остаток после деления ax на целое число m равен 1. Если a действительно имеет обратный модуль m , то представляют собой бесконечное число решений этого сравнения, образующих класс сравнения по этому модулю. Более того, любое целое число, которое конгруэнтно a (т.е. находится в классе конгруэнтности ' ), имеет любой элемент класса конгруэнтности x как модульную мультипликативную инверсию. Используя обозначение для обозначения класса конгруэнтности, содержащего w , это можно выразить, сказав, что мультипликативный модуль, обратный классу конгруэнтности , является таким классом конгруэнтности , что: ${\displaystyle {\overline {w}}}$ ${\displaystyle {\overline {a}}}$ ${\displaystyle {\overline {x}}}$

${\displaystyle {\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},}$

где символ обозначает умножение классов эквивалентности по модулю m . ^[2] Написанная таким образом, ясно представлена ​​аналогия с обычной концепцией мультипликативной обратной операции для множества рациональных или действительных чисел , заменяющей числа классами сравнения и соответствующим образом изменяющей бинарную операцию . ${\displaystyle \cdot _{m}}$

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

${\displaystyle ax\equiv b{\pmod {m}}.}$

Нахождение модульных мультипликативных инверсий также имеет практическое применение в области криптографии , например, в криптографии с открытым ключом и алгоритме RSA . ^{[3] [4] [5]} Преимущество компьютерной реализации этих приложений заключается в том, что существует очень быстрый алгоритм ( расширенный алгоритм Евклида ), который можно использовать для вычисления модульных мультипликативных обратных чисел.

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

Для данного положительного целого числа m два целых числа, a и b , называются конгруэнтными по модулю m, если m делит их разность. Это бинарное отношение обозначается

${\displaystyle a\equiv b{\pmod {m}}.}$

Это отношение эквивалентности на множестве целых чисел , и классы эквивалентности называются классами конгруэнтности по модулю m или классами вычетов по модулю m . Обозначим класс сравнения, содержащий целое число a , ^[6], тогда ${\displaystyle \mathbb {Z} }$ ${\displaystyle {\overline {a}}}$

${\displaystyle {\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.}$

Линейное сравнение — это модульное сравнение вида

${\displaystyle ax\equiv b{\pmod {m}}.}$

В отличие от линейных уравнений над действительными числами, линейные сравнения могут иметь ноль, одно или несколько решений. Если x является решением линейного сравнения, то каждый элемент в также является решением, поэтому, говоря о количестве решений линейного сравнения, мы имеем в виду количество различных классов сравнений, содержащих решения. ${\displaystyle {\overline {x}}}$

Если d — наибольший общий делитель a и m , то линейное сравнение ax ≡ b (mod m ) имеет решения тогда и только тогда, когда d делит b . Если d делит b , то существует ровно d решений. ^[7]

Модульное мультипликативное обращение целого числа a по модулю m является решением линейного сравнения

${\displaystyle ax\equiv 1{\pmod {m}}.}$

Предыдущий результат говорит, что решение существует тогда и только тогда, когда НОД( a , m ) = 1 , то есть a и m должны быть относительно простыми (т.е. взаимно простыми). Более того, когда это условие выполняется, существует ровно одно решение, т. е. когда оно существует, модульный мультипликативный обратный модуль уникален: ^[8] Если b и b' оба являются модулярными мультипликативными обратными модулями относительно модуля m , то

${\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}$

поэтому

${\displaystyle a(b-b')\equiv 0{\pmod {m}}.}$

Если a ≡ 0 (mod m ) , то gcd( a , m ) = a , и a даже не будет иметь модульного мультипликативного обратного. Следовательно, b ≡ b' (mod m ) .

Когда ax ≡ 1 (mod m ) имеет решение, его часто обозначают следующим образом:

${\displaystyle x\equiv a^{-1}{\pmod {m}},}$

но это можно считать злоупотреблением обозначениями, поскольку оно может быть неправильно истолковано как обратное число (которое, в отличие от модульного мультипликативного обратного числа, не является целым числом, за исключением случаев, когда a равно 1 или -1). Обозначение будет правильным, если a интерпретируется как лексема, обозначающая класс сравнения , поскольку мультипликативная инверсия класса сравнения является классом сравнения с умножением, определенным в следующем разделе. ${\displaystyle a}$ ${\displaystyle {\overline {a}}}$

Целые числа по модулю м

Отношение конгруэнтности по модулю m делит набор целых чисел на m классов конгруэнтности. Операции сложения и умножения можно определить над этими m объектами следующим образом: чтобы сложить или умножить два класса сравнения, сначала выберите представителя (любым способом) из каждого класса, затем выполните обычную операцию для целых чисел над двумя представителями. и, наконец, возьмем класс сравнения, в котором находится результат целочисленной операции, как результат операции над классами сравнения. В символах, представляющих операции над классами сравнения, эти определения имеют вид ${\displaystyle +_{m}}$ ${\displaystyle \cdot _{m}}$

${\displaystyle {\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}}$

и

${\displaystyle {\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.}$

Эти операции четко определены , а это означает, что конечный результат не зависит от выбора представителей, которые были сделаны для получения результата.

Классы сравнения m с этими двумя определенными операциями образуют кольцо , называемое кольцом целых чисел по модулю m . Для этих алгебраических объектов используется несколько обозначений, чаще всего или , но в некоторых элементарных текстах и ​​областях применения используются упрощенные обозначения, когда путаница с другими алгебраическими объектами маловероятна. ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /m}$ ${\displaystyle \mathbb {Z} _{m}}$

Классы сравнения целых чисел по модулю m традиционно были известны как классы вычетов по модулю m , что отражает тот факт, что все элементы класса сравнения имеют одинаковый остаток (т.е. «вычет») при делении на m . Любой набор из m целых чисел, выбранный так, что каждое из них принадлежит к разным классам конгруэнтности по модулю m, называется полной системой вычетов по модулю m . ^[9] Алгоритм деления показывает, что набор целых чисел {0, 1, 2, ..., m − 1} образует полную систему вычетов по модулю m , известную как система наименьших вычетов по модулю m . При работе с арифметическими задачами иногда удобнее работать с полной системой вычетов и пользоваться языком сравнений, а в других случаях более полезна точка зрения классов конгруэнтности кольца . ^[10] ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

Мультипликативная группа целых чисел по модулю m

Не каждый элемент полной системы вычетов по модулю m имеет модульный мультипликативный обратный, например, ноль никогда не имеет. После удаления элементов полной системы вычетов, которые не являются относительно простыми с m , остается то, что называется приведенной системой вычетов , все элементы которой имеют модульные мультипликативные обратные. Число элементов в системе приведенных вычетов равно , где – функция Эйлера , т. е. количество натуральных чисел, меньших m , которые являются относительно простыми с m . ${\displaystyle \phi (m)}$ ${\displaystyle \phi }$

В общем кольце с единицей не каждый элемент имеет мультипликативный обратный , а те, у которых он есть, называются единицами . Поскольку произведение двух единиц является единицей, единицы кольца образуют группу , группу единиц кольца и часто обозначаемую R ^× , если R — имя кольца. Группа единиц кольца целых чисел по модулю m называется мультипликативной группой целых чисел по модулю m и изоморфна приведенной системе вычетов. В частности, он имеет порядок (размер), . ${\displaystyle \phi (m)}$

В случае, когда m является простым числом , скажем, p , тогда и все ненулевые элементы имеют мультипликативные обратные, таким образом, поле является конечным . В этом случае мультипликативная группа целых чисел по модулю p образует циклическую группу порядка p − 1 . ${\displaystyle \phi (p)=p-1}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

Пример

Для любого целого числа всегда имеет место модульная мультипликативная инверсия по отношению к модулю , поскольку . Примеры : , и так далее. ${\displaystyle n>1}$ ${\displaystyle n^{2}-n+1}$ ${\displaystyle n+1}$ ${\displaystyle n^{2}}$ ${\displaystyle (n+1)(n^{2}-n+1)=n^{3}+1}$ ${\displaystyle 3\times 3\equiv 1{\pmod {4}}}$ ${\displaystyle 4\times 7\equiv 1{\pmod {9}}}$ ${\displaystyle 5\times 13\equiv 1{\pmod {16}}}$

В следующем примере используется модуль 10: Два целых числа конгруэнтны по модулю 10 тогда и только тогда, когда их разница делится на 10, например

${\displaystyle 32\equiv 2{\pmod {10}}}$так как 10 делит 32 - 2 = 30, и

${\displaystyle 111\equiv 1{\pmod {10}}}$так как 10 делит 111 - 1 = 110.

Некоторые из десяти классов сравнения по этому модулю:

${\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \}}$

${\displaystyle {\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \}}$

${\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \}}$и

${\displaystyle {\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.}$

Линейное сравнение 4 x ≡ 5 (mod 10) не имеет решений, поскольку целые числа, конгруэнтные 5 (т. е. те, что в ), все нечетны, а 4 x всегда четны. Однако линейное сравнение 4 x ≡ 6 (mod 10) имеет два решения: x = 4 и x = 9 . НОД (4, 10) = 2 и 2 не делят 5, но делят 6. ${\displaystyle {\overline {5}}}$

Поскольку НОД(3, 10) = 1 , линейное сравнение 3 x ≡ 1 (mod 10) будет иметь решения, то есть будут существовать модульные мультипликативные обратные числа 3 по модулю 10. Фактически, 7 удовлетворяет этому сравнению (т. е. 21 − 1 = 20). Однако другие целые числа также удовлетворяют сравнению, например 17 и -3 (т. е. 3(17) - 1 = 50 и 3(-3) - 1 = -10). В частности, каждое целое число в будет удовлетворять сравнению, поскольку эти целые числа имеют вид 7 + 10 r для некоторого целого числа r и ${\displaystyle {\overline {7}}}$

${\displaystyle 3(7+10r)-1=21+30r-1=20+30r=10(2+3r),}$

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

Произведение классов сравнения и можно получить, выбрав элемент из , скажем, 25, и элемент из , скажем -2, и наблюдая, что их произведение (25)(-2) = -50 находится в классе сравнения . Таким образом, . Сложение определяется аналогичным образом. Десять классов сравнения вместе с этими операциями сложения и умножения классов сравнения образуют кольцо целых чисел по модулю 10, т.е. ${\displaystyle {\overline {5}}}$ ${\displaystyle {\overline {8}}}$ ${\displaystyle {\overline {5}}}$ ${\displaystyle {\overline {8}}}$ ${\displaystyle {\overline {0}}}$ ${\displaystyle {\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}}$ ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

Полная система вычетов по модулю 10 может представлять собой набор {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, где каждое целое число находится в другом классе сравнения по модулю 10. Уникальная система наименьших вычетов по модулю 10 равно {0, 1, 2, ..., 9}. Система уменьшенных остатков по модулю 10 может быть {1, 3, 7, 9}. Произведение любых двух классов конгруэнтности, представленных этими числами, снова является одним из этих четырех классов конгруэнтности. Это подразумевает, что эти четыре класса конгруэнтности образуют группу, в данном случае циклическую группу четвертого порядка, имеющую либо 3, либо 7 в качестве (мультипликативного) генератора. Представленные классы конгруэнтности образуют группу единиц кольца . Эти классы конгруэнтности — это именно те классы, которые имеют модульные мультипликативные обратные. ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

Вычисление

Расширенный алгоритм Евклида

Модульный мультипликативный обратный модулю m можно найти с помощью расширенного алгоритма Евклида.

Алгоритм Евклида определяет наибольший общий делитель (НОД) двух целых чисел, скажем, a и m . Если a имеет мультипликативный обратный модуль m , этот НОД должен быть равен 1. Последнее из нескольких уравнений, созданных алгоритмом, может быть решено для этого НОД. Затем, используя метод под названием «обратная подстановка», можно получить выражение, связывающее исходные параметры и этот НОД. Другими словами, можно найти целые числа x и y , удовлетворяющие тождеству Безу :

${\displaystyle ax+my=\gcd(a,m)=1.}$

Переписано, это

${\displaystyle ax-1=(-y)m,}$

то есть,

${\displaystyle ax\equiv 1{\pmod {m}},}$

Итак, модульный мультипликативный обратный элемент a был вычислен. Более эффективной версией алгоритма является расширенный алгоритм Евклида, который с помощью вспомогательных уравнений сокращает два прохода алгоритма (обратную замену можно рассматривать как обратный проход алгоритма) до одного.

В нотации большого O этот алгоритм работает за время O(log ² ( m )) , предполагая | а | < m и считается очень быстрым и, как правило, более эффективным, чем его альтернатива — возведение в степень.

Используя теорему Эйлера

В качестве альтернативы расширенному алгоритму Евклида теорема Эйлера может использоваться для вычисления обратных модулей. ^[11]

Согласно теореме Эйлера , если a взаимно просто с m , то есть НОД( a , m ) = 1 , то

${\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}$

где – функция Эйлера . Это следует из того, что a принадлежит мультипликативной группе ^× тогда и только тогда, когда a взаимно просто с m . Следовательно, модульный мультипликативный обратный можно найти напрямую: ${\displaystyle \phi }$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )}$

${\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}$

В частном случае, когда m — простое число, а обратное по модулярному значению определяется выражением ${\displaystyle \phi (m)=m-1}$

${\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}.}$

Этот метод обычно медленнее, чем расширенный алгоритм Евклида, но иногда используется, когда уже доступна реализация модульного возведения в степень. Некоторые недостатки этого метода включают в себя:

• Значение должно быть известно , и наиболее эффективное известное вычисление требует факторизации m . Широко распространено мнение, что факторизация является вычислительно сложной проблемой. Однако вычисления несложны, если известна простая факторизация m . ${\displaystyle \phi (m)}$ ${\displaystyle \phi (m)}$
• Относительная стоимость возведения в степень. Хотя это может быть реализовано более эффективно с использованием модульного возведения в степень , когда задействованы большие значения m , это наиболее эффективно вычисляется с помощью метода приведения Монтгомери , который сам по себе требует модульного обратного модуля m , который и должен был быть рассчитан в первое место. Без метода Монтгомери стандартное двоичное возведение в степень , которое требует деления по модулю m на каждом шаге, является медленной операцией, когда m велико.

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

Несколько инверсий

Можно вычислить обратное к нескольким числам a _i по модулю общего m с помощью одного вызова алгоритма Евклида и трех умножений на каждый дополнительный вход. ^[12] Основная идея состоит в том, чтобы сформировать произведение всех a i _, инвертировать его, а затем умножить на a _j для всех j ≠ i , чтобы оставить только желаемое a.⁻¹
_я.

Более конкретно, алгоритм (все арифметические действия выполняются по модулю m ):

1. Вычислите префиксные произведения для всех i ≤ n . ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$
2. Вычислить б⁻¹
   _ниспользуя любой доступный алгоритм.
3. Для i от n до 2 вычислите
   • а⁻¹
     _я= б⁻¹
     _яб _{я -1} и
   • б⁻¹
     _{я −1}= б⁻¹
     _яа _я .
4. Наконец ,⁻¹
   ₁= б⁻¹
   ₁.

Можно выполнять умножения в древовидной структуре, а не линейно, используя параллельные вычисления .

Приложения

Поиск модульного мультипликативного обратного имеет множество приложений в алгоритмах, основанных на теории модульной арифметики. Например, в криптографии использование модульной арифметики позволяет выполнять некоторые операции быстрее и с меньшими требованиями к хранению, в то время как другие операции становятся более трудными. ^[13] Обе эти особенности можно использовать с пользой. В частности, в алгоритме RSA шифрование и дешифрование сообщения выполняется с использованием пары чисел, которые являются мультипликативными обратными по отношению к тщательно выбранному модулю. Один из этих номеров является общедоступным и может использоваться в процедуре быстрого шифрования, тогда как другой, используемый в процедуре расшифровки, остается скрытым. Определение скрытого номера по общедоступному номеру считается невозможным с вычислительной точки зрения, и именно это заставляет систему работать над обеспечением конфиденциальности. ^[14]

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

1. Используйте расширенный алгоритм Евклида для вычисления k ⁻¹ , модульного мультипликативного обратного значения k mod 2 ^w , где w — количество битов в слове. Это обратное будет существовать, поскольку числа нечетные, а модуль не имеет нечетных множителей.
2. Для каждого числа в списке умножьте его на k ⁻¹ и возьмите наименее значимое слово результата.

На многих машинах, особенно на тех, у которых нет аппаратной поддержки деления, деление — более медленная операция, чем умножение, поэтому этот подход может дать значительное ускорение. Первый шаг относительно медленный, но его нужно сделать только один раз.

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

Например, система

Х ≡ 4 (по модулю 5)

Х ≡ 4 (по модулю 7)

Х ≡ 6 (по модулю 11)

имеет общие решения, так как 5,7 и 11 попарно взаимно просты . Решение дается

Х = т ₁ (7 × 11) × 4 + т ₂ (5 × 11) × 4 + т ₃ (5 × 7) × 6

где

t ₁ = 3 — модульное мультипликативное обратное число 7 × 11 (mod 5),

t ₂ = 6 — модульное мультипликативное обратное число 5 × 11 (по модулю 7), а

t ₃ = 6 — модульное мультипликативное число, обратное 5 × 7 (по модулю 11).

Таким образом,

Икс = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

и в его уникальной уменьшенной форме

Х ≡ 3504 ≡ 39 (мод. 385)

поскольку 385 — это НОК 5,7 и 11.

Кроме того, модульное мультипликативное обратное число занимает видное место в определении суммы Клоостермана .

Смотрите также

• Инверсивный конгруэнтный генератор - генератор псевдослучайных чисел, использующий модульные мультипликативные инверсии.
• Рациональная реконструкция (математика)

Примечания

1. Розен 1993, с. 132.
2. Шумахер 1996, с. 88.
3. Стинсон, Дуглас Р. (1995), Криптография / Теория и практика , CRC Press, стр. 124–128, ISBN 0-8493-8521-0
4. Трапп и Вашингтон, 2006, стр. 164–169.
5. Мориарти, К.; Калиски, Б.; Йонссон, Дж.; Раш, А. (2016). «PKCS # 1: Спецификации криптографии RSA, версия 2.2». Рабочая группа по интернет-инжинирингу RFC 8017 . Рабочая группа по интернет-инжинирингу . Проверено 21 января 2017 г.
6. Часто используются и другие обозначения, в том числе [ a ] и [ a ] _m .
7. Ирландия и Розен 1990, с. 32
8. Шуп, Виктор (2005), Вычислительное введение в теорию чисел и алгебру, издательство Кембриджского университета, теорема 2.4, с. 15, ISBN 9780521851541
9. Розен 1993, с. 121
10. Ирландия и Розен 1990, с. 31
11. Томас Коши. Элементарная теория чисел с приложениями, 2-е изд. ISBN 978-0-12-372487-8 . С. 346. 
12. Брент, Ричард П .; Циммерманн, Пол (декабрь 2010 г.). «§2.5.1 Сразу несколько инверсий» (PDF) . Современная компьютерная арифметика. Кембриджские монографии по вычислительной и прикладной математике. Том. 18. Издательство Кембриджского университета. стр. 67–68. ISBN 978-0-521-19469-3.
13. Трапп и Вашингтон 2006, с. 167
14. Трапп и Вашингтон 2006, с. 165

Рекомендации

• Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (2-е изд.), Springer-Verlag, ISBN 0-387-97329-Х
• Розен, Кеннет Х. (1993), Элементарная теория чисел и ее приложения (3-е изд.), Аддисон-Уэсли, ISBN 978-0-201-57889-8
• Шумахер, Кэрол (1996). Глава нулевая: Фундаментальные понятия абстрактной математики . Аддисон-Уэсли. ISBN 0-201-82653-4.
• Траппе, Уэйд; Вашингтон, Лоуренс К. (2006), Введение в криптографию с теорией кодирования (2-е изд.), Прентис-Холл, ISBN 978-0-13-186239-5

Внешние ссылки

• Вайсштейн, Эрик В. «Модульная инверсия». Математический мир .
• Гевара Васкес, Фернандо представляет решенный пример решения мультипликативного обратного по модулю с использованием алгоритма Евклида.