#дневниклекций
Сегодня на лекции прошли вот что:
- Напоминание: сильно и слабо односторонние функции
- Умножение как предположительно односторонняя функция. Обсуждение, почему её слабая односторонность следует только из предположения о сложности разложения на простые, а сильной может не быть. (Я сомневался, и действительно: на самом деле числа с маленькими делителями занимают экспоненциально малую часть всех чисел, так что алгоритма, раскладывающего даже обратно полиномиальную долю всех чисел, неизвестно. То есть умножение предположительно именно сильно односторонняя. Но это куда более сложные оценки).
- Теорема об усилении: если существует слабо односторонняя функция, то существует и сильно односторонняя.
- Конструкция усиления через параллельное повторение, её устойчивость против наивных обратителей.
- Принцип настоящего доказательства: если новую функцию можно обратить с существенной вероятностью, то исходную с почти единичной.
- Обсуждение идей, как можно построить обратитель старой функции из обратителя новой. Описание конструкции: подставляем аргумент на разные позиции, остальное заполняем случайными, пытаемся обратить, проверяем успешность и так много раз (амплификация).
- Доказательство корректности конструкции: разделение аргументов на простые и сложные, две леммы о вероятности успеха нового обратителя и ошибки старого, подбор параметров, чтобы получилось противоречие.
- Односторонние перестановки. Неизвестность их существования в строгом смысле
- Функция Рабина (возведение в квадрат по модулю): определение, обратимость при известном разложении модуля на множители, определение подмножества, на котором она биективна и (предположительно) необратима (модуль - произведение двух простых вида 2k+3, вычет - квадратичный).
- Общее определение односторонней перестановки. Эффективная генерация равномерного распределения на D_n. Как её сделать для функции Рабина.