A classic would be quickly computing such big numbers under a modulus. You just compute the carmichael totient recursively till it hits 1, disregard higher orders and then going backwards calculate the powers, reducing by the modulo of the current order (this way it never gets large enough to be a pain to calculate). The totients reduce in logn time and each step is logn so it’s merely logn^2 to calculate.
alt Hacker News
A classic would be quickly computing such big numbers under a modulus. You just compute the carmichael totient recursively till it hits 1, disregard higher orders and then going backwards calculate the powers, reducing by the modulo of the current order (this way it never gets large enough to be a pain to calculate). The totients reduce in logn time and each step is logn so it’s merely logn^2 to calculate.