Мішатронік - Арифметика и числовые алгоритмы

1	Арифметические алгоритмы Условия задач Теоретический материал: Решето Эратосфена (М.Иванов) Теоретический материал: Функция Эйлера (М.Иванов) Теоретический материал: Бинарное возведение в степень за О(log N) (М.Иванов) Теоретический материал: Обратный элемент в поле по модулю (М.Иванов) Теоретический материал: Дискретное логарифмирование (М.Иванов) Теоретический материал: Линейное модулярное уравнения с одним неизвестным (М.Иванов) Теоретический материал: Китайская теорема об остатках. Алгоритм Гарнера (М.Иванов) Теоретический материал: Нахождение степени делителя факториала (М.Иванов) Теоретический материал: Вычисления факториала по модулю (М.Иванов) Теоретический материал: Первообразный корень. Алгоритм нахождения (М.Иванов) Теоретический материал: Дискретное извлечение корня (М.Иванов)

2	Наибольший общий делитель и алгоритм Евклида Теоретический материал: НОД и НОК, алгоритм Евклида (М.Иванов) Теоретический материал: Расширенный алгоритм Евклида (М.Иванов) Теоретический материал: Диофантовы уравнения с двумя неизвестными: AX+BY=C (М.Иванов) Вычисление НОД 2-х чисел Задачи, сводящиеся к вычислению НОД НОД n чисел, НОК, ... Расширенный алгоритм Евклида. Линейные диофантовы уравнения. Задачи на понимание и модификацию алгоритма Евклида Сложные олимпиадные задачи Теоретический материал: Обратный элемент в поле по модулю (М.Иванов)

3	Системы счисления Целые числа Дроби Теоретический материал: Троичная сбалансированная система счисления (М.Иванов)

4	Битовые операции Условия задач Теоретический материал: Перебор всех подмасок данной маски (М.Иванов)

5	"Длинная" арифметика Просто о "длинных" числах (В. Гуровиц) Теоретический материал (В.Гольдштейн) Теоретический материал (С++, М.Иванов) Реализация Условия задач

6	Более сложные арифметические алгоритмы Теоретический материал: алгоритм Карацубы и быстрое преобразование Фурье (А.Климовский) Умножение двух полиномов или длинных чисел с помощью Быстрого преобразования Фурье за O (N log N) (М.Иванов) Реализация БПФ в поле вычетов по модулю p (А.Ворожцов) Тест BPSW на простоту чисел за O (log N) (М.Иванов) Эффективные алгоритмы факторизации: Полларда p-1, Полларда p, Бента, Полларда Монте-Карло, Ферма (М.Иванов) Задачи на сложные теоретико-числовые алгоритмы