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

Таблица 23 Шаг, i ЛЧ?' 1 (J ^ 0 ^ 0 Выход'.' f/ "1 «2 "л V| VT V .l Д о цикла Да Да Да Нет - 0 1 111 = 29 1 0 fl=:16 1 Да Да Да Ист 1 1 0 16 -1 1 13 2 Да Да Да Нет 1 -1 1 13 2 -1 3 3 Да Да Да Нет 4 2 -1 3 -9 5 1 4 Да Да Да Нет 3 -9 1 29 -16 0 t-lTor: Нет Да Нет Да - iri+Ui = 20 - - - - - На шаге 4 значение стало равным 1, тогда в щ находится результат; = -9. Нормируем результат; iti = т + И) = 29 - 9 = 20 Обратный элемент равен 20. Проверка. (]6'20) mod 29 должно быть равно 1: (16'20) mod 29 = 320 mod 29 = (11 -29 + 1) mod 29 = - (I 1-29 mod 29 + I mod 29) mod 29 равно 1. Правильно. Пример 2.6. Необходимо для числа а = 6 найти обратный элемент и нормировать результат числовым модулем т = 28. Рассмотрим этот пример в предположении, что заранее неизвестно - является ли число т простым. Отмстим, что числа а = 6 и /н = 28 невзаимно простые. Инициализируем векторы U к V: U={Q, 1, m = 28}, V={I, О, л = 6}. Далее представим шаги алгоритма в виде трассировочной таб­ лицы (табл. 2.4). Таблица 2.4 Шаг. i 1 «1 ^ 0 V5 0 Выход? '•/ «1 "2 м, v\ \*2 ^'.1 Д о цикла Да Да Да Нет - 0 1 т = 2Н 1 0 а = 6 1 Да Да Да Нет 4 1 0 6 - 4 1 4 2 Да Да Да Нет 1 - 4 1 4 -1 2 3 Да Да Да Нет 2 S -1 2 -14 3 0 Итог; Да Да Нет Да 2/0 = 7 Значе!ше а не определено 48