Игры, теория чисел (5 мая 2016)

1. Игры
1. Def: симметричная игра на графе
2. Выигрышность и проигрышность позиций (L → W; W → L)
3. Случай ацикличного графа: динамика за O(V+E)
4. Случай цикличного графа: ретроанализ за O(V+E)
5. Прямая сумма игр (декартово произведение графов). Решение за O((V+E)^k)
6. Функция Гранди, определение и построение за O(V+E), Lm: проигрышность ⇔ grundi(v) = 0. Решение прямой суммы ацикличных игр без док-ва.

1. Базовая теория чисел
1. Остатки по модулю простого p − поле. Умеем складывать, вычитать, умножать, делить.
2. {a : (a, m) = 1} − группа по умножению. Умеем умножать, делить.
3. Возведение в степень за логарифм, умножение через сложение за логарифм.
4. Линейные диофантовы уравнения. Решение.
5. Переполнения. Lm без док-ва: коэффициенты по ходу расширенного Евклида по модулю строго меньше исходных чисел.
6. Код расширенного алгоритма Евклида.
7. Деление и обращение по модулю простого и составного числа через алгоритма Евклида.
8. Деление и обращение по модулю простого и составного числа через теорему Эйлера.
9. Обращение всех чисел от 1 до k за O(k): inv[i] = -inv[p%i] * (p/i)
2. RSA
1. Simple XOR cipher (шифр Вернама, одноразовый). Симметричное кодирование, общий ключ.
2. Концепция "открытый ключ, закрытый ключ".
3. Схема кодирования и декодирования: n = pq, ed ≡ 1(φ(n)), m → m^e → (m^e)^d ≡ m(n)
4. Факторизация ⇔ φ(n) → взлом RSA
5. Практика: коды длины k = 2048 бит → длинная арифметика
6. Время кодирования/декодирования: O(k³). Simple XOR cipher: O(k).
3. Первообразный корень
1. Def: {g⁰, g¹, ..., g^p-2} = {1, 2, ..., p-1}
2. Рандомизированный алгоритм поиска: return random [1,p-1]
3. Вероятность успеха равна φ(p-1) / (p-1) ≥ 1 / lnln p
4. Как проверить? Перебрать все простые делители p-1.
5. Пусть есть задача, решение которой требует первообразный корень и работает за A(n), а проверить корректность ответа можем за B(n),
тогда мы получили вероятностный алгоритм за O(lnlnn)*(A(n)+B(n))