Обратное по модулю число

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

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

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

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

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

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