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

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

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

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

Это отношение эквивалентности на множестве целых чисел, ℤ , а классы эквивалентности называются классы конгруэнтных по модулю т или классы вычетов по модулю т . Обозначим через класс сравнения, содержащий целое число a , ^[6], тогда${\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 является наибольшим общим делителем из и т то линейное сравнение ах ≡ Ь ( по модулю т ) имеет решение , если и только если г делит б . Если d делит b , то существует ровно d решений. ^[7]

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

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

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

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

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

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

Целые числа по модулю 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} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m}$${\displaystyle \mathbb {Z} _{m}}$

Классы сравнения целых чисел по модулю m традиционно назывались классами вычетов по модулю m , что отражает тот факт, что все элементы класса сравнения имеют один и тот же остаток (т. Е. «Остаток») после деления на m . Любой набор из m целых чисел, выбранный так, что каждое происходит из другого класса сравнения по модулю m, называется полной системой вычетов по модулю m . ^[9] В алгоритме деление показывает , что множество целых чисел, {0, 1, 2, ..., т - 1} образуют полную систему вычетов по модулю т , известный как наименее остаток системы по модулю т. При работе с арифметическими задачами иногда удобнее работать с полной системой вычетов и использовать язык сравнений, в то время как в других случаях более полезна точка зрения классов конгруэнции кольца . ^[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} }$

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

Чтобы проиллюстрировать приведенные выше определения, рассмотрим следующий пример с использованием модуля 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). В частности, каждое целое число в удовлетворяет сравнению, поскольку эти целые числа имеют вид 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 , этот gcd должен быть 1. Последнее из нескольких уравнений, созданных алгоритмом, может быть решено для этого gcd. Затем, используя метод, называемый «обратная подстановка», можно получить выражение, связывающее исходные параметры и этот НОД. Другими словами, можно найти целые числа 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]

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

${\displaystyle a^{\phi (m)}\equiv 1{\pmod {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}}.}$

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

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

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

Множественные инверсии [ править ]

Можно вычислить обратное значение нескольких чисел a _i по модулю общего m с помощью одного вызова алгоритма Евклида и трех умножений на каждый дополнительный ввод. ^[12] Основная идея заключается в том, чтобы сформировать произведение всех _я , инвертный , что, затем умножить на виде _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
     _{я -1}= b⁻¹
     _яа _я .
4. Наконец,⁻¹
   ₁= b⁻¹
   ₁.

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

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

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

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

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

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

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

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

X ≡ 4 (мод. 5)

X ≡ 4 (мод. 7)

X ≡ 6 (мод.11)

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

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

где

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

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

t ₃ = 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 .
• Гевара Васкес, Фернандо предоставляет решенный пример решения мультипликативной обратной по модулю с использованием алгоритма Евклида.