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

+ IxlO" (слева направо: 5 в рачряде десятков тысяч;О - в разряде тысяч; 9 - в разряде сотен; 2 - в разряде десятков, а 1 - в разряде единиц). Аналогично можно представить число .v в виде двоичного числа (двоичного полинома): t-i Л" = .V()X2" + л-|Х2' +Л-2Х2' + , . .+ .Л'а- |X2*"'И Л И ,V = - , (1.2) где Л", = (О, 1} - двоичное число, / = О, ic - 1 , ке N - число двоич­ ных разрядов, необходимое для представления числа х (л- < 2* ]. Например, двоичиос число 10111 можно записать в виде полинома: 1011 Ь = 1 X Ю' + О X 10^ + 1 X 10" + I X Ю' + 1 X К)" (слева направо: 1 в разряде десягков тысяч;О - в разряде тысяч; 1 - в разряде со­ тен; 1 - в разряде десятков, а 1 - в разряде единиц). Тогда из формул (1.1) и (1.2) при использовании модульной арифметики следует: у=а mod/M=ic^i=ii modw= (13) {(Г 'mod/ttj mod »;. Здесь Л",- задают /-е двоичные разряды степени .г. В схеме Горнера выражение у вычисляется с меньших но­ меров двоичных разрядов в сторону возрастания степени i. Член г= ^ «"''^'modrnj (i-0, к-I) из (1.3) при .v, = 1 не требуется вы­ числять заново, с самого начала, так как его можно получить сле­ дующим образом: modjwj = ' modw j modm, по значению предыдущего шага. Описание алгоритма работы схе.мы Горпера На вход: числа а, х, т е N. На выходе: у е /V или сообщение о неприменимости алгоритма. 33