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

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

${\ Displaystyle Ax \ Equiv 1 {\ pmod {m}},}$

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

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

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

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

${\ Displaystyle Ax \ Equiv B {\ pmod {m}}.}$

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

Содержание

• 1 Модульная арифметика
  • 1.1 Целые числа по модулю m
  • 1.2 Мультипликативная группа целых чисел по модулю m
• 2 Пример
• 3 Расчет
  • 3.1 Расширенный алгоритм Евклида
  • 3.2 Использование теоремы Эйлера
  • 3.3 Множественные инверсии
• 4 Приложения
• 5 См. Также
• 6 Примечания
• 7 ссылки
• 8 Внешние ссылки

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

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

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

${\ Displaystyle a \ Equiv b {\ pmod {m}}.}$

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

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

Линейная конгруэнтность представляет собой модульное конгруэнтность формы

${\ Displaystyle Ax \ Equiv B {\ pmod {m}}.}$

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

Если d является наибольшим общим делителем из и т то линейное сравнение ах ≡ Ь ( по модулю т) имеет решение, если и только если г делит б. Если d делит b, то существует ровно d решений.

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

${\ Displaystyle Ax \ Equiv 1 {\ pmod {m}}.}$

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

Когда у ax ≡ 1 (mod m ) есть решение, его часто обозначают так -

${\ Displaystyle х \ эквив а ^ {- 1} {\ pmod {m}},}$

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

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

Отношение сравнения по модулю 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}}.}$

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

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

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

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

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

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

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

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

пример

Чтобы проиллюстрировать приведенные выше определения, рассмотрим следующий пример с использованием модуля 10.

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

${\ Displaystyle 32 \ Equiv 12 {\ pmod {10}}}$ поскольку 10 делит 32 - 12 = 20, и

${\ 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}}}$

Поскольку gcd (3, 10) = 1, линейное сравнение 3 x ≡ 1 (mod 10) будет иметь решения, то есть будут существовать модульные мультипликативные обратные числа 3 по модулю 10. Фактически, 7 удовлетворяет этому сравнению (т. Е. 21 - 1 = 20). Однако другие целые числа также удовлетворяют сравнению, например 17 и −3 (т.е. 3 (17) - 1 = 50 и 3 (−3) - 1 = −10). В частности, каждое целое число in будет удовлетворять сравнению, поскольку эти числа имеют вид 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}}$

Вычисление

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

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

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

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

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

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

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

это,

${\ Displaystyle Ax \ Equiv 1 {\ pmod {m}},}$

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

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

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

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

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

${\ Displaystyle а ^ {\ фи (м)} \ экви 1 {\ pmod {м}},}$

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

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

В частном случае, когда m - простое число, а модульный обратный равен ${\ Displaystyle \ фи (м) = м-1}$

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

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

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

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

Множественные инверсии

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

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

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

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

Приложения

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

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

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

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

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

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

X ≡ 4 (мод. 5)

X ≡ 4 (мод 7)

X ≡ 6 (мод.11)

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

Х = t 1 (7 × 11) × 4 + t 2 (5 × 11) × 4 + t 3 (5 × 7) × 6

где

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

t 2 = 6 является модульным мультипликативным обратным 5 × 11 (mod 7) и

t 3 = 6 является модульным мультипликативным обратным 5 × 7 (mod 11).

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

Х = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

и в уникальном сокращенном виде

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

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

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

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

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

Заметки

использованная литература

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

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

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