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

Мультипликативность (рункции Эйлера. Ilycii, латл лва натуральных числа а и h. Если они нчаимно проспи, ю функция Эйлера обладает свойством мультип.чика! ивносги: Ц)(ахЬ) = ф(а)хф(/?). Таким образом, эта формула позволяет уменьшить вычисли­ тельную сложность нахождения (piaxh), особенно для больших чи­ сел а, b и ахЬ (применяется в алгоритме шифрования RSA). Пример 1.12. Пусть дано число 660. Найдем для него функ­ цию Эйлера. Число 660 может быть разложено на два взаимно про­ стых числа а = 60 и /j = 11, тогда (р(660) = (р(60х11) = ф(60)хф( I 1). Ранее было вычислено, что для 60 количество взаимно прос гых чисел равно 16. Так как число 11 - простое, то ф( 11) = 11 - 1 = 10, т.е. ф(660) = ф(60)хф(11) = 16x10 = 160. Дополнительные примеры для ре1нення. Вычислите функцию Эйлера для следующих чисел: - 127 (простое); - 210 и 4500 (составные). Вопросы для самопроверки 1. Для решения каких задач используется функция Эйлера? 2. Поясните формулу для вычисления функции Эйлера. 3. Поясните понятия простое и составное числа. 4. Что обозначают понятия кратные сомножители и взаимно простые числа? 5. Поясните алгоритм вычисления функции Эйлера. 6. В чем разница между теоремами Эйлера и Ферма? 7. Что понимается под мультипликативностью функции Эй­ лера? 8. Каким образом можно найти простые и составные сомно­ жители числа ml 31