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

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

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

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

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

Предыдущий результат говорит, что решение существует тогда и только тогда, когда gcd( a , m ) = 1 , то есть a и m должны быть взаимно простыми (т.е. взаимно простыми). Более того, когда это условие выполняется, существует ровно одно решение, т.е. когда оно существует, модульное мультипликативное обратное является уникальным: ^[8] Если b и b' являются модульными мультипликативными обратными a относительно модуля 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 . ${\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}}}$

Так как 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} }$

Вычисление

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

Модульное мультипликативное обратное число по модулю 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 )) , предполагая, что | a | < m , и считается очень быстрым и, как правило, более эффективным, чем его альтернатива — возведение в степень.

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

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

Согласно теореме Эйлера , если a взаимно просто с m , то есть gcd( 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, это наиболее эффективно вычисляется с помощью метода редукции Монтгомери , который сам по себе требует модульного обратного mod m , что и должно было быть вычислено в первую очередь. Без метода Монтгомери стандартное бинарное возведение в степень , которое требует деления mod 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. Вычислить b⁻¹
   _нс использованием любого доступного алгоритма.
3. Для i от n до 2 вычислить
   • а⁻¹
     _я= б⁻¹
     _яb _{i −1} и
   • б⁻¹
     _{я −1}= б⁻¹
     _яа _я .
4. Наконец ,⁻¹
   ₁= б⁻¹
   ₁.

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

Приложения

Нахождение модульной мультипликативной инверсии имеет множество применений в алгоритмах, которые опираются на теорию модульной арифметики. Например, в криптографии использование модульной арифметики позволяет выполнять некоторые операции быстрее и с меньшими требованиями к памяти, в то время как другие операции становятся более сложными. ^[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 являются попарно взаимно простыми . Решение дается формулой

X = t1 (7 _× 11) × 4 + t2 (5 × ₁₁ ) × 4 + t3 (5 _× 7) × 6

где

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

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

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

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

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

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

X ≡ 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. doi : 10.17487/RFC8017 . RFC 8017. Получено 21 января 2017 г.
6. Часто используются и другие обозначения, включая [ a ] и [ a ] _m .
7. Айрленд и Розен 1990, стр. 32
8. Шоуп, Виктор (2005), Вычислительное введение в теорию чисел и алгебру, Cambridge University Press, Теорема 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. Cambridge University Press. С. 67–68. ISBN 978-0-521-19469-3.
13. Трапп и Вашингтон 2006, стр. 167
14. Трапп и Вашингтон 2006, стр. 165

Ссылки

• Айрленд, Кеннет; Розен, Майкл (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-е изд.), Prentice-Hall, ISBN 978-0-13-186239-5

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

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