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

5. Иначе: - ncpcii rn к следующему простому числу из А/,,; j = j + 1 ; - если а, ^ О (на шаге 4 был найден сомножитель под номером /) то / = / + 1 (начать поиск следующего сомножителя /), для числа т ) - перейти к п. 3. 6. Если i = 1 и Pi = О, го т - простое число => ф(/«) = т - переход к шагу 9. 7. Если 3i = I, {к ~ число отличных сомножителей числа пг) для которого а/>0, то 9(WO=(a"' переход к шагу 9. 8. Иначе (p{in) = m I Pi Pi Рк 9. Вывести значение ф(/«). Выход. В криптографии часто вычисляются арифметические опера­ ции по некоторому модулю - составному или простому. Например, в алгоритме шифрования RSA вычисляется производное число от составного модуля - функция Эйлера. Теорема Эйлера. Пусть заданы некоторые натуральные числа а и т, где т - составное. Если числа а и т - взаимно про­ стые, то для них справедливо равенство: а'''"'" mod/?z s 1 , Малая теорема Ферма (частный случай теоремы Эйлера). Пусть заданы некоторые натуральные числа а и р, где р ~ простое. Для чисел а и /?, где р | а (а не делится нацело на р), справедливо равенство: а''~' mod р = 1. Эти теоремы находят приложение при вычислении обратных элементов в алгебраической системе «конечное поле». 30