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

=^(а" mod ;j;j mod in• j mod m = |(9" mod 31] mod 31 •9 j mod 31 - =(l9" mod31-9) mod31 = 180 mod 31 = 25. Ответ; у = с/ mod m = 25. Опишем второй вариант схемы Горнера. Пусть первые пять шагов совпадают с алгоритмом первого варианта схемы Горнера: 6. Пусть результат v = 1, переменная цикла i = k-\ и г =а ' mod т . 7. Если Xi = 1 (/-й разряд числа л- равен 1), то у = О'' • m o d т, иначе у = у" modт . 8. Вычислить i = i - 1. Если i > О, то перейти к шагу 7. 9. Если л'о = 1 (учесть последний бит числа х), то у = (у • а) mod т . 10. Вывод результата у. Выход. Пример 1.15. Вычислим у = а' mod т при а = 5, .v = 13, т = 11. Число л- в двоичном виде можно представить Kaic.v = 13io = 1 ЮЬ. Пусть у = 1. Представим вычисления шагов 7-8 в виде трас­ сировочной таблицы (табл. 1.11). TaO.'imia 1.11 Шаг, i •I'i V 3 .V, = 1 (1 • II) mod 14 = II 2 Л'2 ~ 1 (II'- I Dm o d 14=(9- l l ) m o d 14=1 1 Л-, = 0 1 mod 14 = 1 На шаге 9 будет учтен последний бит числа .v; у = (у •rt'" ) mod in - (\ • 5) mod 14 = 5. Ответ: у =« ' mod т = 5. Вычислите по второму варианту дополнительные примеры. 36