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

1.7. Возведение натуральных чисел но модулю в большие степени Пусть задано выражение вида у - а ' modm, ( 1 . I ) где а е N - основание етепенн; д- е N- степень выражения; гп е Л/ — числовой модуль, число, нормирующее выражение в д и а п а _ зоне [0; т - 1]; mod - знак операции взятия остатка от деленх1я делимого а ' на делитель т ; у - результат вычисленного в ы р а ­ жения, лежащий в диапазоне [0; т - 1]; N - множество натурали^- ных чисел. Пусть все операции производятся над натуральными ч и с ­ лами, целочисленно, без округлений. При непосредственном вычислении значение выражения может выйти за размеры машинного слова (значения которогом о ­ гут лежать в диапазоне [0; 2'^" - 1]) уже при малых значениях а и j v , например при и-3 и .х-= 21. Поэтому необходимы другие м е х а ­ низмы получения результата, полагая, что будет использоваться модульная арифметика. Схема Горнера обладает следующими особенностями: - выражение (1.1) вычисляется при ограничениях на диапа з он натуральных чисел для ПЭВМ (промежуточные результаты берут;-ся по модулю); - каждая операция разбивается на подмножество эквивалент­ ных; - используется, в отличие от последовательного возведения числа а в степень .v, меньше операций умножения из-за разложения степени выражения (1.1) на сумму степеней числа 2. Десятичное число л- можно представить в виде еуммы е диниц , десятков, сотен, тысяч и т.д., т.е. в виде десятичного полинома: Л" = .VOXLO" + .VIXЮ ' + Л'АХ1 0 " + . . . + / Х 1 0 * ' " где .V, е [О; 9] - является десятичным числом, i = Q, k~\,ks/V — число, такое, что .v < Например, десятичное число 50921 м о ж н о записать в виде полинома: 50921 ю = 5x10'* + ОхЮ' + 9х 10" + 2х 10* -ь 32