В математике , в частности , в области теории чисел , в модульном мультипликативном обратном А.Н. целого представляет собой целое число х , что произведение ах является конгруэнтно 1 по отношению к модулю м . [1] В стандартных обозначениях модульной арифметики это сравнение записывается как
что является сокращенным способом записать утверждение, что m делит (поровну) величину ax - 1 , или, другими словами, остаток после деления ax на целое число m равен 1. Если a имеет обратный по модулю m, существует бесконечное число решений этого сравнения, которые образуют класс сравнения по этому модулю. Более того, любое целое число, которое конгруэнтно a (т. Е. Находится в классе конгруэнтности a ), будет иметь любой элемент класса конгруэнтности x в качестве модульного мультипликативного обратного. Используя обозначениячтобы указать класс конгруэнции, содержащий w , это можно выразить, сказав, что мультипликативный обратный по модулю класс конгруэнции класс сравнения такой, что:
где символ обозначает умножение классов эквивалентности по модулю m . [2] Написанная таким образом аналогия с обычной концепцией мультипликативного обратного в множестве рациональных или действительных чисел четко представлена, заменяя числа классами сравнения и соответствующим образом изменяя бинарную операцию .
Как и в случае аналогичной операции с действительными числами, основное использование этой операции заключается в решении, когда это возможно, линейных сравнений вида
Нахождение модульных мультипликативных инверсий также имеет практическое применение в области криптографии , т. Е. Криптографии с открытым ключом и алгоритма RSA. [3] [4] [5] Преимущество компьютерной реализации этих приложений состоит в том, что существует очень быстрый алгоритм ( расширенный алгоритм Евклида ), который можно использовать для вычисления модульных мультипликативных обратных величин.
Модульная арифметика
Для данного положительного целого числа m два целых числа a и b называются конгруэнтными по модулю m, если m делит их разность. Это бинарное отношение обозначается как,
Это отношение эквивалентности на множестве целых чисел, ℤ , а классы эквивалентности называются классы конгруэнтных по модулю т или классы вычетов по модулю т . Позволятьобозначим класс сравнения, содержащий целое число a , [6], то
Линейная конгруэнтность представляет собой модульное конгруэнтность формы
В отличие от линейных уравнений над вещественными числами, линейные сравнения могут иметь ноль, одно или несколько решений. Если x - решение линейного сравнения, то каждый элемент в также является решением, поэтому, говоря о количестве решений линейной конгруэнции, мы имеем в виду количество различных классов конгруэнции, которые содержат решения.
Если d является наибольшим общим делителем из и т то линейное сравнение ах ≡ Ь ( по модулю т ) имеет решение , если и только если г делит б . Если d делит b , то существует ровно d решений. [7]
Модульное мультипликативное обратное целое число a по модулю m является решением линейного сравнения
Предыдущий результат говорит, что решение существует тогда и только тогда, когда gcd ( a , m ) = 1 , то есть a и m должны быть взаимно простыми (т.е. взаимно простыми). Более того, когда это условие выполняется, существует ровно одно решение, т. Е. Когда оно существует, модульный мультипликативный обратный элемент единственен. [8]
Когда ax ≡ 1 (mod m ) имеет решение, его часто обозначают так -
но это злоупотребление нотации , поскольку модульным мультипликативного обратного представляет собой целое число , и -1 не является целым числом , когда представляет собой целое число , отличное от 1 или - 1. Запись будет правильным , если интерпретируется как лексемы, обозначающие класс конгруэнтности, поскольку мультипликативный обратный класс конгруэнции является классом конгруэнции с умножением, определенным в следующем разделе.
Целые числа по модулю m
Отношение сравнения по модулю m разбивает множество целых чисел на m классов сравнения. Операции сложения и умножения могут быть определены для этих m объектов следующим образом: чтобы сложить или умножить два класса сравнения, сначала выберите представителя (любым способом) из каждого класса, затем выполните обычную операцию для целых чисел на двух представителях. и, наконец, возьмем класс сравнения, в котором лежит результат целочисленной операции как результат операции над классами сравнения. В символах с а также представляющие операции над классами конгруэнтности, эти определения
а также
Эти операции четко определены , что означает, что конечный результат не зависит от выбора представителей, которые были сделаны для получения результата.
В м классы конгруэнтно с этими двумя определенными операциями образуют кольцо , называемое кольцом целых чисел по модулю т . Для этих алгебраических объектов используется несколько обозначений, чаще всего или же , но некоторые элементарные тексты и прикладные области используют упрощенные обозначения когда путаница с другими алгебраическими объектами маловероятна.
Классы сравнения целых чисел по модулю m традиционно назывались классами вычетов по модулю m , что отражает тот факт, что все элементы класса сравнения имеют один и тот же остаток (т. Е. «Остаток») после деления на m . Любой набор из m целых чисел, выбранный так, что каждое происходит из другого класса сравнения по модулю m, называется полной системой вычетов по модулю m . [9] В алгоритме деление показывает , что множество целых чисел, {0, 1, 2, ..., т - 1} образуют полную систему вычетов по модулю т , известный как наименее остаток системы по модулю т . При работе с арифметическими задачами иногда удобнее работать с полной системой вычетов и использовать язык сравнений, а в других случаях - точку зрения классов конгруэнтности кольцаполезнее. [10]
Мультипликативная группа целых чисел по модулю m
Не каждый элемент полной системы вычетов по модулю m имеет модульную мультипликативную инверсию, например, ноль никогда не имеет. После удаления элементов полной системы вычетов, которые не являются взаимно простыми с m , то, что осталось, называется редуцированной системой вычетов , все элементы которой имеют модульные мультипликативные обратные. Количество элементов в системе с приведенным остатком составляет, где - функция Эйлера , т. е. количество натуральных чисел меньше m , взаимно простых с m .
В общем кольце с единицей не каждый элемент имеет обратный мультипликатив, и те, которые имеют, называются единицами . Поскольку произведение двух единиц является единицей, единицы кольца образуют группу , группу единиц кольца и часто обозначаются R ×, если R - это имя кольца. Группа единиц кольца целых чисел по модулю m называется мультипликативной группой целых чисел по модулю m , и она изоморфна приведенной системе вычетов. В частности, имеет порядок (размер),.
В случае, когда т является простой , скажем , р , то и все ненулевые элементы имеют мультипликативные обратные, таким образом это конечное поле . В этом случае мультипликативная группа целых чисел по модулю p образует циклическую группу порядка p - 1 .
Пример
Чтобы проиллюстрировать приведенные выше определения, рассмотрим следующий пример с использованием модуля 10.
Два целых числа совпадают по модулю 10 тогда и только тогда, когда их разность делится на 10, например
- так как 10 делит 32 - 12 = 20, и
- поскольку 10 делит 111 - 1 = 110.
Вот некоторые из десяти классов конгруэнтности по этому модулю:
- а также
Линейное сравнение 4 x ≡ 5 (mod 10) не имеет решений, поскольку целые числа, которые сравнимы с 5 (т.е.) все нечетные, а 4 x всегда четные. Однако линейное сравнение 4 x ≡ 6 (mod 10) имеет два решения, а именно x = 4 и x = 9 . НОД (4, 10) = 2 и 2 не делит 5, но делает разрыв 6.
Поскольку 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 и
явно делится на 10. Это сравнение имеет только один класс конгруэнции решений. Решение в этом случае можно было бы получить, проверив все возможные случаи, но для больших модулей потребуются систематические алгоритмы, которые будут приведены в следующем разделе.
Произведение классов конгруэнтности а также можно получить, выбрав элемент , скажем 25, и элемент , скажем −2, и заметив, что их произведение (25) (- 2) = −50 находится в классе сравнения . Таким образом,. Сложение определяется аналогично. Десять классов сравнения вместе с этими операциями сложения и умножения классов сравнения образуют кольцо целых чисел по модулю 10, т. Е..
Полная система вычетов по модулю 10 может быть набором {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, где каждое целое число находится в другом классе сравнения по модулю 10. Уникальная система наименьших вычетов по модулю 10 это {0, 1, 2, ..., 9}. Система приведенных остатков по модулю 10 может быть {1, 3, 7, 9}. Произведение любых двух классов конгруэнтности, представленных этими числами, снова является одним из этих четырех классов конгруэнтности. Это означает, что эти четыре класса конгруэнции образуют группу, в данном случае циклическую группу четвертого порядка, имеющую либо 3, либо 7 в качестве (мультипликативного) генератора. Представленные классы конгруэнции образуют группу единиц кольца. Именно эти классы конгруэнции имеют модульные мультипликативные инверсии.
Вычисление
Расширенный алгоритм Евклида
Модульный мультипликативный обратный к модулю м можно найти с помощью расширенного алгоритма Евклида.
Алгоритм Евклида определяет наибольший общий делитель (GCD) двух целых чисел, скажем , и т . Если a имеет мультипликативный обратный по модулю m , этот gcd должен быть 1. Последнее из нескольких уравнений, созданных алгоритмом, может быть решено для этого gcd. Затем, используя метод, называемый «обратная подстановка», можно получить выражение, связывающее исходные параметры и этот НОД. Другими словами, можно найти целые числа x и y, удовлетворяющие тождеству Безу ,
Переписанный, это
это,
Итак, была вычислена модульная мультипликативная обратная к a . Более эффективной версией алгоритма является расширенный алгоритм Евклида, который с помощью вспомогательных уравнений сокращает два прохода алгоритма (обратная подстановка может рассматриваться как прохождение алгоритма в обратном направлении) до одного.
В нотации большого O этот алгоритм работает за время O (log ( m ) 2 ) , предполагая, что | а | < m , и считается очень быстрым и обычно более эффективным, чем его альтернатива, возведение в степень.
Используя теорему Эйлера
В качестве альтернативы расширенному алгоритму Евклида теорема Эйлера может использоваться для вычисления модульных обратных величин. [11]
Согласно теореме Эйлера , если является взаимно просты с т , то есть, НОД ( , м ) = 1 , то
где - функция Эйлера . Это следует из того, что a принадлежит мультипликативной группе× тогда и только тогда , когда является взаимно просты в м . Следовательно, модульное мультипликативное обратное можно найти напрямую:
В частном случае, когда m простое число, а модульный обратный дается формулой
Этот метод обычно медленнее, чем расширенный алгоритм Евклида, но иногда используется, когда реализация для модульного возведения в степень уже доступна. К недостаткам этого метода можно отнести:
- Значение должны быть известны и наиболее эффективным известным вычисление требует м «s факторизации . Широко распространено мнение, что факторизация представляет собой сложную в вычислительном отношении проблему. Однако расчетпрямолинейно, когда известно факторизация m на простые множители .
- Относительная стоимость возведения в степень. Хотя это может быть реализовано более эффективно с использованием модульного возведения в степень , при больших значениях m это наиболее эффективно вычисляется с помощью метода редукции Монтгомери . Сам этот алгоритм требует модульного обратного модуля m , который и должен был быть вычислен в первую очередь. Без метода Монтгомери стандартное двоичное возведение в степень , которое требует деления по модулю m на каждом шаге, является медленной операцией, когда m велико.
Одним из заметных преимуществ этого метода является то, что отсутствуют условные переходы, которые зависят от значения a , и, таким образом, значение a , которое может быть важным секретом в криптографии с открытым ключом , может быть защищено от атак по побочным каналам . По этой причине стандартная реализация Curve25519 использует этот метод для вычисления обратного.
Множественные инверсии
Можно вычислить обратное значение нескольких чисел a i по модулю общего m с помощью одного вызова алгоритма Евклида и трех умножений на каждый дополнительный ввод. [12] Основная идея заключается в том, чтобы сформировать произведение всех я , инвертный , что, затем умножить на виде J для всех J ≠ я оставить только нужные A−1
я.
В частности, алгоритм (вся арифметика выполняется по модулю m ):
- Вычислить префикс продуктов для всех i ≤ n .
- Вычислить b−1
п используя любой доступный алгоритм. - Для i от n до 2 вычислить
- а−1
я= b−1
яb i −1 и - б-1
я -1= b−1
яа я .
- а−1
- Наконец,−1
1= b−1
1.
Можно выполнять умножения в древовидной структуре, а не линейно, чтобы использовать параллельные вычисления .
Приложения
Нахождение модульной мультипликативной обратной имеет множество приложений в алгоритмах, основанных на теории модульной арифметики. Например, в криптографии использование модульной арифметики позволяет выполнять некоторые операции быстрее и с меньшими требованиями к памяти, в то время как другие операции становятся более сложными. [13] Обе эти функции можно использовать с пользой. В частности, в алгоритме RSA шифрование и дешифрование сообщения выполняется с использованием пары чисел, которые являются обратными по отношению к тщательно выбранному модулю. Один из этих номеров является общедоступным и может использоваться в процедуре быстрого шифрования, в то время как другой, используемый в процедуре дешифрования, остается скрытым. Считается, что определение скрытого номера из общедоступного номера невозможно с вычислительной точки зрения, и именно это заставляет систему работать для обеспечения конфиденциальности. [14]
В качестве другого примера в другом контексте рассмотрим задачу точного деления в информатике, где у вас есть список нечетных чисел размером со слово, каждое из которых делится на k, и вы хотите разделить их все на k . Одно из решений следующее:
- Используйте расширенный алгоритм Евклида для вычисления k −1 , модульного мультипликативного обратного k mod 2 w , где w - количество битов в слове. Это обратное будет существовать, поскольку числа нечетные, а модуль не имеет нечетных множителей.
- Для каждого числа в списке умножьте его на k −1 и возьмите младшее значащее слово результата.
На многих машинах, особенно без аппаратной поддержки деления, деление является более медленной операцией, чем умножение, поэтому такой подход может привести к значительному ускорению. Первый шаг относительно медленный, но его нужно сделать только один раз.
Модульные мультипликативные инверсии используются для получения решения системы линейных сравнений, которое гарантируется китайской теоремой об остатках .
Например, система
- 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.
Кроме того, модульные мультипликативные обратные фигуры занимают видное место в определении суммы Клоостермана .
Смотрите также
- Инверсивный конгруэнтный генератор - генератор псевдослучайных чисел, который использует модульные мультипликативные инверсии
- Рациональная реконструкция (математика)
Заметки
- Перейти ↑ Rosen 1993 , p. 132
- ^ Шумахер 1996 , стр. 88
- ^ Стинсон, Дуглас Р. (1995), Криптография / Теория и практика , CRC Press, стр. 124–128, ISBN 0-8493-8521-0
- ^ Trappe и Вашингтон 2006 , стр. 164-169
- ^ Мориарти, К .; Калиски, Б .; Jonsson, J .; Руш, А. (2016). «PKCS # 1: Спецификации криптографии RSA, версия 2.2» . Инженерная рабочая группа Интернета RFC 8017 . Инженерная группа Интернета . Проверено 21 января 2017 года .
- ^ Часто используются другие обозначения, включая [ a ] и [ a ] m .
- ^ Ирландия и Розен 1990 , стр. 32
- ^ Виктор Шуп (2005), Вычислительное введение в теорию чисел и алгебру , Cambridge University Press, теорема 2.4, с. 15, ISBN 9780521851541
- Перейти ↑ Rosen 1993 , p. 121
- ^ Ирландия и Розен 1990 , стр. 31 год
- ^ Томас Koshy. Элементарная теория чисел с приложениями , 2-е издание. ISBN 978-0-12-372487-8 . С. 346.
- ^ Брент, Ричард П .; Циммерманн, Пауль (декабрь 2010 г.). «§2.5.1 Несколько инверсий сразу» (PDF) . Современная компьютерная арифметика . Кембриджские монографии по вычислительной и прикладной математике. 18 . Издательство Кембриджского университета. С. 67–68. ISBN 978-0-521-19469-3.
- ^ Trappe и Вашингтон 2006 , стр. 167
- ^ Trappe и Вашингтон 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-е изд.), Прентис-Холл, ISBN 978-0-13-186239-5
Внешние ссылки
- Вайсштейн, Эрик В. «Модульная инверсия» . MathWorld .
- Гевара Васкес, Фернандо предоставляет решенный пример решения мультипликативной обратной по модулю с использованием алгоритма Евклида.