Теория чисел (25 ноября 2024)

1. Решето Эратосфена
   1. Версия за O(NloglogN), доказательство времени работы, оптимизации
   2. Алгоритм за O(N)
   3. O(N^1/2) памяти (решето на окне)
   4. Вычисление мультипликативных функций (phi, число делителей)
   
   
2. Обратные числа
   1. Возведение в степень за logp (теоремы малая Ферма, Эйлера)
   2. Расширенный Евклид (рекурсивная версия)
   3. Сравнение способов обращения: Евклид быстрее и без переполнений
   4. Обратные к числам 1..k за O(k)
   
   
3. Шифрование
   1. Закрытый ключ, передача данных XOR-ом
   2. Взлом закрытого ключа: частотный анализ
   3. Открытый ключ. Протокол Диффи-Хеллмана обмена закрытыми ключами.
   4. Открытый ключ. RSA.
   
   
4. КТО
   1. Теорема. Вычисления.
   2. Случай невзаимнопростых модулей.
   3. Использование в длинной арифметике.
   
   
5. ПервообрАзный корень
   1. Поиск за O(loglogn), проверка за O(FACT+log²n)
   2. Применение для решения уравнения x^k = a(m)
   3. Использование первообразного корня без проверки
   
   
6. Дискретное логарифмирование за n^1/2