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

а при т = 1 всегда будет получаться результат, равный нулю, так как во множестве результатов О, гп - 1 будет существовать только один элемент, равный нулю), 4. Задаются векторы U = {«,, , V = {v,, v^, v,}. Производится начальная установка параметров значениями. Вектор С/ = {О, 1,т } ; вектор V= {1, О, о}, 5. Пока щ Ф I и 1(3 ф О , ш v j Ф О, выполняются следующие дей­ ствия (пояснение: при щ = 1 результат будет получен в U\ (успеш­ ное завершение алгоритма); при vj = О будет деление на нуль в п. а); если щ - О, то доказывается, что два чиела а и т не являются вза­ имно простыми): а) найти результат целочисленного деления числа на I'v" q = б) для V / = 1, 3 - находится значение выражения t = и, - v, • cf, - Hi присваивается значение v,-: Ui= v,- (т.е. значение перемен­ ной V,- с предыдущего шага); - V,- присваивается новое значение: Vj = /; в) переход к началу. 6. Если щ Ф I, то обратный элемент не существует, выход. 7. Если нз = 1, то в переменной u\ хранится значение обрат­ ного элемента а~'. Если u i <0 , то осуществляется приведение результата к положительному числу: ui =m + U]. Далее осущесгв- ляется вывод значения и^. Выход. Примеры работы расширенного алгоритма Евклида Пример 2.5. Необходимо для числа а = 16 найти обратный элемент а~' и нормировать результат числовым модулем т = 29. Инищ1ализируем векторы U и V; С= {О, 1, нг = 29}, V = {1, О, с/ = 1 6 } . Далее представим шаги алгоритма в виде трассировочной таблицы (табл. 2.3). 47