Вычисление мультипликативных обратных.

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

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

воспользоваться расширенным алгоритмом Евклида. Из условия получаем

или, перенеся ту в правую часть,

откуда вытекает, что

и, следовательно, — мультипликативный обратный к а по модулю [Отметим, что в нашем случае мы имеем дело с короткими целыми числами; поэтому, полагая в выражении для времени работы алгоритма Евклида, получаем, что мультипликативный обратный вычисляется за время ]

Пример. В поле вычислим — мультипликативный обратный элемент к 4 по модулю 11. Применяя расширенный алгоритм Евклида к 11 и 4, получим следующую таблицу:

Итерация

Из последней строки вытекает, что , где числа —1 и 3 расположены в столбцах соответственно; следовательно, . Можно ускорить вычисление мультипликативных обратных, заметив, что в нашем случае не обязательно вычислять последовательность элементов (Обратный элемент появляется в столбце который содержит множители при 4; он мог бы появиться в столбце если бы мы поменяли местами числа 4 и 11.)

Другой способ вычисления мультипликативного обратного по модулю простого числа состоит в применении следующей замечательной теоремы (см. историческое замечание 4).