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

Tiifmiiitti !.10 Шаги 1 цикле Условие i < к Значение .v, /• у Д о цикла - 1 2 2 IlJar i = 1 Да 0 4 2 Шаг i = 2 Да 0 16 2 Шаг i = 3 Да 1 256 mod 29 = 24 48 mod 2 9 = 1 9 Шаг i = 4 Да 1 57Ь mod 24 = 25 475 mod 29 = 11 Шаг( = 5 Ист - Выходi n цик'ла Ответ: у = а' mod ni= 11, Дополнительные примеры для решения: 1) с; = 7, .V = 5, = 31. Найти у =а ' mod т ? (5) 2) 0 = 3, Л' = 7, т = 29. Найти >' = а ' mod ml {\ 2) 3) а = 5,.х= 11, т = 14. Найти у = а' mod;/; ? (3) Существует другой вариант схемы Горнера возведеиия целых чисел в большие степени. Степень х также представляется в двоич- A-l НОМ виде: Л" = ^Л',2', х е (О, 1}. В отличие от первого варианта 1=1) схемы Горнера последовательно рассматриваются двоичные разря­ ды числа л- в направлении понижения номера разряда. Тогда возве­ дение в степень можно выполнить по следующей схеме: у~а mo d ; / 2 - = [(--.(((й^' ')" mod/H-a'^' -)" mod;7/-a'^* mod «-fl-^"]mod;«. Пример 1.14. Вычислим у = а ' mod т при а = 9, д- = 5, т = 31. Число Л' в двоичном виде можно представить как л- = Зю = ЮЬ. Тогда: // у = d mod т = mod/n- «'^'j mod/zicz^" mod/j! = mod/?! <;"] modm a mod w = 35