Задания пронумерованы от простого к сложному.

Задача 1. 
Что находит следующий фрагмент кода?

int f(int x); //  функция f определена в другом месте программы

typedef pair <int, int> Pair;
stack<Pair> s;
int n = 0;
int x = 0;
s.push(Pair(x, n));
for(;;)
{
x = f(x); n++;
while(!s.empty() && s.top().first < x)
s.pop();
if(s.top().first == x)
return n - s.top().second;
s.push(Pair(x, n));
}

Задача 2. 
Предположим, что функция f есть случайная функция, отображающая интервал [0..N-1] в себя. 
Оцените среднее время работы кода из предыдущего пункта и его требование к памяти.

Задача 3. 
Покажите, что если задача нахождения коллизий в функции f(x) = g^x mod N, 
где g - генератор группы квадратичных вычетов по модулю N, а N - произведение двух простых чисел, 
решается за полиномиальное время от длины N, то задача разложения числа N на простые сомножители также решается за полиномиальное время. 
Указание: для решения (и понимания условия) можно пользоваться любыми источниками.