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

II. Можно вычислить для элемента а обратный элемент а ' и при знании функции Эйлера ф(/н), где НОД {а,т ) = 1. Так как о''""" 1П0с1нг = I и (а • й~') mod нг = 1,то а'*""" modm = (а- £ Г')modm => => й-ч"'"'"' iTiodw = fl"' mod/H =>«"' =ЙГ'р'""~' mod/ « . Данную формулу можно вычислить с меньшими вычисли­ тельными затратами, используя схему Горнера для быстрого возве­ дения числа а в степень (ф(нг) - 1). Пример 2.4. Пусть а = 5, т =7. Найдем а"' с помощью функ­ ции Эйлера. Модуль т = 1 является простым числом. Поэтому функция Эйлера равна ф(т) = ф(7) = m - 1=6. Тогда обратная ве­ личина от 5 по модулю 7 равна сГ' = modm = 5®"' mod 7 = 5'' mod 7. Используем схему Горнера для разложения степени у числа 5: 5''mod 7 = (5^mod 7)-(5"mod 1)-{5 mod 7) mod 7 = (4 • 4 • 5) mod 7 = = (2 • 5) mod 7 = 3. Таким образом, для числа а обратный элемент равен а"' = 3. Ш. Использование расширенного алгоритма Евклвда, В алгоритме вее операции производятся над целыми числами. Под обозначением ]к[ будем понимать взятие от числа к только це­ лой части, без округления. На вход алгоритма подаются: числа а е Z и т е N, НОД (й,т ) = 1. На выходе ожидается число а""' =1, т- \. Расширенный алгоритм Евклида для нахождения обратного элемента Й~' можно представить в виде следующих шагов: 1.Ввод числа а, для которого необходимо найти обратный элемент . 2. Ввод модулят , нормирующего результат. 3. Если « =О или т=^0 или m= I, то были заданы некоррект­ ные параметры, выход (пояснение: при а =О не существует обрат­ ного элемента; при m=О возникает ситуация деления иа нуль; 46