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

1. Bi «vi с консо.чи значения основания степени а, степени .v II MT);I\'JIHТ . 2. Hc.iii 111 - 0. то деление на ноль, выход. .г Ксли и = О, то результат равен у = О, переход к п. 8. 4. Нсли и= 1 или .V = 0,10 результат равен у = I, переход к п. 8. 5. П{чм13й0днм поиск для числа .v верхней границы, являю­ щейся ci eneiibio числа 2; число КЕ. N такое, что .v < 2\ т.е. К > logix. а) Пусть г - 2" и к = 0; пока к < 32 (максимальное число раз­ рядов в маинпнюм слове) и г<х, возводим 2 в степень к: ;- = 2^ и увслнчипаем к па единицу. б) Кслн />: = О плн к > 32, то задача не решается в установ­ ленных условиях, выход (число 32 обозначает максимальную сте­ пень дво11К11 /и1я ^машинного слова, т.е. число 2"'" задает максимальное чис.'ю различных значений, которые можно сохранить в машинном слове). Иначе п. 6. 6. Пусть г = 11. Если степень .v нечетна (остаток от деления на 2 равен единице), то у = а, иначе у = 1. 7. Для всех / = 1, /. -1 выполняем следующие действия; а) г= [(/-mod /»)-('• mod »;)] mod tu = г mod nv, б) ecjHi /-Н бит числа .v равен единице .v, = I, то у = (у • г) modт . 8. Вывод результата у. Выход. Вычислительная сложность схемы Горнсра равна o(logU.v)). Пример 1.13. Необ.ходимо число а = 2 возвести в степень д- = 25 н привести результат по модулю пг = 29. Тогда к. удовлетворяющее неравенству к > log^.v, равно 5. Число .V прсдставимо в двоичной форме как = 25|о= 1 0012- Это число является нечетным. На шаге 6 получаем, что r-a = v = 2. Далее представим шаг в виде трассировочной таблицы (табл. 1.10). 34