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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

поэтому

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычисление

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

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

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

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

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

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

$ax-1=(-y)m,$

то есть,

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

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

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

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

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

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

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

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

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

В частном случае, когда m — простое число, $\phi (m)=m-1$ а модульное обратное имеет вид

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

X = t₁ (7 × 11) × 4 + t₂ (5 × 11) × 4 + t₃х

где

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.

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

См. также

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

Ссылки

• Ирландия, Кеннет; Розен, Майкл (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

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

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