С принципом работы алгоритма я и сам ознакомился, спасибо. Что такое функция Эйлера и как ее считать я тоже знаю уже много лет как.

Но я совершенно не понимаю, почему знание того, что такое "функция Эйлера" помогает понять, что бы то ни было. Я не могу ктверждать наверняка, но вполне могло быть, что авторы ни про какую функцию Эйлера не слышали, для того, чтобы понять, что по n=pq трудно вычислить (p-1)(q-1) это совершенно не нужно.

Хотя уж про ф-ю Эйлера я могу поверить, что в каких-нибудь вопросах CS это классика жанра, только в конкретных убедительных примеров я до сих пор, к ожалению, не видел.