Функция Эйлера может быть использована для возведение больших чисел в большую степень по модулю.
Имеется целое число авозводим его в целое число хи требуется взять модуль – тоже некоторое целое число mи получить остаток от этого числа r.
(a x )mod m º r
Применение теоремы Эйлера позволяет нам достаточно быстро возводить большие числа в большую степень
При определенном навыке на бумаге можно сделать гораздо быстрее, чем на компьютере.
Пример Пусть дано: a=2 х=5432675
m=p=13 Теорема Эйлера (aj(m) )mod m º1
m-целое.a-взаимно простое с m
Теорема Эйлера утверждает, что остаток будет равен 1
Если m простое, то ф(р)=p-1
a p -1 =1mod p
1) Находим функцию Эйлера для числа m=p=13, т.е. ф(р)=p-1=12.
2) Число х представляем черех функцию Эйлера х=5432675=qф(р) +r = 452722*12+11=4352722+11
3) Вычисляем
(24352722*12+11 )mod13 =(24352722*12 *211 )mod13 =
=
(24352722*12 mod13)(211 mod13) mod13 =
(24352722*12+11 )mod13 =7