Вычисления в конечных полях

Пример 2.3. Пусть « = 5, in = l. Решим раиспсгни ( « - «•') mod m = 1 или (5 • ^Г') mod 7 = I. НаЛдсм « ' псрсГгором. Прн этом число должно искаться в интервале </' = !. т - 1. Результаты предсгавиы в виде фассировочио!! габлипы (табл. 2.2) (искомый результат подчеркнут лииие!!). Теш ища 2,2 Ш а г . ' (.5 • (I ' 1 moJ 7 1 5 .S 2 10 .4 3 1.5 1 Шаг, я ' 5 • (5 • (Г' 1 moU 7 4 20 6 2S 4 6 Ж) Т Получаем, что сГ^ = 5"' mod 7 = 3. Вариантом переборного алгоритма является более быегрьп"! сле­ дующий алгоритм. Если числа а и т взаимно просгы (НОД(</, т)= 1 ), т о существуе! обратный элемент для а, а выражение аха'^ ^ 1 mod in можно записать в виде ахсГ' mod m= (1 + mxt) mod in, где t - нату­ ральное число. Числа а и т заданы, неизвестны числа t и а~\ Нужно найти такое наименьшее t, при котором а"' будет целым и будет удовлетворять условию существования обратного элемента: ЙХ(Г' = = 1 mod »;. Перепишем выражение ЙХ«"' mod tn = ( \ + inxt) mod т к а к а = 1+ lilt ^ mod/ ». Описание алгоритма 1. Если HOД(^^ п) Ф 1 (алгоритм Евклида, раздел 1.1), то вы­ х о д . Обратный элемент не существует. 2. Для любого t е[0, +°°) вычисляются следующие действия: 1 + int если значение выражения не является иат)'ральным числом, а т о переход к п. 2. Иначе это выражение задает обратный элемент; а ' = Jmodm , выход. Алгоритм будет конечен в том случае, когда выполняется ус­ ловие взаимной простоты двух чисел а и т (условие существования обратного элемента). 45