CSEDays. Theory 2011

Екатеринбург, 14-17 апреля

News subscription
Share:

Reviews

Часто бывает, что некогда заниматься чем-то, нет желания, просто не знаешь, как подойти к проблеме. На лекциях же получил ответы на многие вопросы, которые у меня были.
Александр Попов / CSEDays. Theory 2011
Home / CSEDays Theory 2011 /

Домашнее задание CSEDays.Theory 2011

Решение домашнего задания не было обязательным условием, но повышало шансы кандидатов на участие и получение гранта от спонсоров. Задачи были предложены Ильей Мироновым.

Задача 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.empty() && 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 на простые сомножители также решается за полиномиальное время. 

Указание: для решения (и понимания условия) можно пользоваться любыми источниками.

Илья Миронов:

"В курсе я собираюсь расказывать про криптографические хэш-функции. Основная задача, стоящая перед авторами таких функций - это устойчивость к коллизиям. Все три задачи посвящены этой теме".

Загрузить файл с заданием.