Проанализировав код, понимаем, что суть таска в том, чтобы максимально быстро посчитать `(a**b)**(c**d)%n`.
В голову сразу приходит бинарное возведение степень, которое позволяет возводить в n-ую степень за log(N). Заметим, что имея работу с остатком от деления, мы можем видоизменить функцию возведения в степень. У меня она вышла такой:
```
def fast_pow(x, y, mod):
if y == 0:
return 1
if y == -1:
return 1. / x
p = fast_pow(x, y // 2, mod)
p *= p
if y % 2:
p *= x
return p % mod
```
~~Берем код бинарного возведения в степень из гугла~~Реализуем бинарное возведение в степень и меняем `(a**b)**(c**d)%n` на `fast_pow(a**b, c**d, n)`.
Попробовав запустить, замечаем, что код все равно выполняется долго, так как `a**b` само по себе требуют значительного времени. Аналогично первой оптимизации мы можем записать `fast_pow(fast_pow(a, b, n), c**d, n)`, но теперь требуется оптимизировать вычисление `c**d`.
А тут приходит идея того, что последовательность, заданная формулой `((a**b%n)**i)%n`, где i - номер числа в ряду, является циклической. Тогда найдем период `t` этого ряда и тогда искомая формула сводится к `fast_pow(fast_pow(a, b, n), fast_pow(c, d, t), n)`.
Для вычисления этой формулы введем `base = fast_pow(a, b, n)`, тогда `t` можно получить так:
```
temp = (base ** 2) % n
t = 1
while t != base:
t += 1
temp *= base
temp %= n
```
Выполняем алгоритм на данном зашифрованном флаге и получаем `ugra_it_is_too_powerful_rsa_right_56c19b679ca`.