Алгоритмы алгебры и теории чисел — различия между версиями
(→Практика - Вероятностные тесты чисел на простоту) |
м (rollbackEdits.php mass rollback) |
||
| (не показана 71 промежуточная версия 13 участников) | |||
| Строка 1: | Строка 1: | ||
== Лекция - Классы чисел и основная теорема арифметики == | == Лекция - Классы чисел и основная теорема арифметики == | ||
| + | * [[Классы чисел]] | ||
| + | * [[Натуральные числа]] | ||
| + | * [[Простые числа]] | ||
| + | * [[Наибольший общий делитель]] | ||
| + | * [[Основная теорема арифметики]] | ||
| + | * [[Теоремы о простых числах]] | ||
=== Практика - Разложение на множители и длинная арифметика === | === Практика - Разложение на множители и длинная арифметика === | ||
| + | * [[Системы счисления]] | ||
| + | * [[Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]] | ||
| + | * [[Разложение на множители (факторизация)]] | ||
| + | |||
== Лекция - Основные элементы теории чисел == | == Лекция - Основные элементы теории чисел == | ||
| + | * [[Сравнения, система вычетов, решение линейных систем по модулю]] | ||
| + | * [[Китайская теорема об остатках]] | ||
| + | * [[Теорема Ферма]] | ||
| + | * [[Теорема Вильсона]] | ||
| + | * [[Мультипликативность функции, свертка Дирихле]] | ||
| + | * [[Функция Эйлера]] | ||
| + | * [[Количество делителей, сумма делителей]] | ||
| + | * [[Функция Мебиуса]] | ||
| + | |||
=== Практика - Основные алгоритмы теории чисел === | === Практика - Основные алгоритмы теории чисел === | ||
| + | * [[Решето Эратосфена]] | ||
| + | * [[Быстрое возведение в степень]] | ||
| + | * [[Умножение по Монтгомери]] | ||
| + | * [[Дискретное преобразование Фурье]] | ||
| + | * [[Быстрое преобразование Фурье]] | ||
| + | |||
== Лекция - Основы теории групп == | == Лекция - Основы теории групп == | ||
| + | * [[Полугруппа]], [[моноид]], [[группа]] | ||
| + | * [[Абелева группа]], [[Конечная группа]] | ||
| + | * [[Гомоморфизм групп]], [[изоморфизм групп]] | ||
| + | * [[Подгруппа]], [[нормальная подгруппа]] | ||
| + | * [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]] | ||
| + | * [[Регулярное представление группы]] | ||
| + | * [[Теорема о подгруппах циклической группы]] | ||
| + | * [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]] | ||
=== Практика - Основы теории групп === | === Практика - Основы теории групп === | ||
| + | * [[Вычисление порядка элемента в группе]] | ||
| + | * [[Вычисление порядка перестановки в группе перестановок]] | ||
| + | * [[Дискретное логарифмирование в группе]] | ||
| + | * [[Действие группы на множестве]] | ||
| + | * [[Лемма Бернсайда, задача о числе ожерелий]] | ||
| + | * [[Представление групп]] | ||
| + | |||
== Лекция - Основы теории колец == | == Лекция - Основы теории колец == | ||
| + | *[[Определение кольца, подкольца, изоморфизмы колец]] | ||
| + | *[[Делители нуля, области целостности]] | ||
| + | *[[Единицы (обратимые элементы), группа обратимых элементов]] | ||
| + | *[[Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах]] | ||
| + | *[[Евклидовы кольца]] | ||
=== Практика - Арифметика полиномов от одной переменной над полем === | === Практика - Арифметика полиномов от одной переменной над полем === | ||
| + | |||
== Лекция - Основы теории полей == | == Лекция - Основы теории полей == | ||
* [[Определение поля и подполя, изоморфизмы полей]] | * [[Определение поля и подполя, изоморфизмы полей]] | ||
* [[Примеры полей]] | * [[Примеры полей]] | ||
* [[Мультипликативная группа поля]] | * [[Мультипликативная группа поля]] | ||
| − | |||
| − | |||
* [[Расширения полей]] | * [[Расширения полей]] | ||
| − | |||
== Лекция - Первообразные корни и квадратичные вычеты == | == Лекция - Первообразные корни и квадратичные вычеты == | ||
* [[Теорема о цикличности мультипликативной группы поля Z/pZ|Теорема о цикличности мультипликативной группы поля <tex>\mathbb{Z}/p\mathbb{Z}</tex>]] | * [[Теорема о цикличности мультипликативной группы поля Z/pZ|Теорема о цикличности мультипликативной группы поля <tex>\mathbb{Z}/p\mathbb{Z}</tex>]] | ||
* [[Первообразные корни]] | * [[Первообразные корни]] | ||
| − | * [[Квадратичные вычеты]] | + | ** [[Существование первообразных корней по определенным модулям|Теорема о существовании первообразных корней по модулям вида <tex>2,4,p^n,2\cdot p^n</tex>]] |
| + | * [[Квадратичные вычеты|Квадратичные вычеты, количество квадратичных вычетов по простому модулю]] | ||
| + | ** [[Символ Лежандра, критерий Эйлера]] | ||
| + | ** [[Теорема о (((p-1)/2)!)^2=-1(mod p)|Теорема о <tex>((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)</tex> при <tex>p=4\cdot k+1</tex>]] | ||
| + | ** [[Лемма Гаусса для вычисления квадратичного характера числа по простому модулю]] | ||
=== Практика - Первообразные корни и квадратичные вычеты === | === Практика - Первообразные корни и квадратичные вычеты === | ||
== Лекция - Квадратичные вычеты == | == Лекция - Квадратичные вычеты == | ||
| − | *[[ | + | *[[Квадратичный закон взаимности]] |
| − | *[[ | + | *[[Символ Якоби и его свойства]] |
| + | *[[Обобщенный квадратичный закон взаимности]] | ||
| + | *[[Алгоритм вычисления символа Якоби]] | ||
=== Практика - Вероятностные тесты чисел на простоту === | === Практика - Вероятностные тесты чисел на простоту === | ||
*[[Тест Ферма проверки чисел на простоту, числа Кармайкла]] | *[[Тест Ферма проверки чисел на простоту, числа Кармайкла]] | ||
| Строка 37: | Строка 86: | ||
* [[Сумма обратных к простым]] | * [[Сумма обратных к простым]] | ||
* [[Асимптотический закон распределения простых чисел]] | * [[Асимптотический закон распределения простых чисел]] | ||
| + | |||
=== Практика - Вычисление <math>\pi(x)</math> === | === Практика - Вычисление <math>\pi(x)</math> === | ||
== Лекция - Цепные (непрерывные) дроби и уравнение Пелля == | == Лекция - Цепные (непрерывные) дроби и уравнение Пелля == | ||
| − | * [[ | + | * [[Цепная дробь]] |
| − | * [[Цепные дроби как приближение к числу]] | + | ** [[Связь цепных дробей и алгоритма Евклида]] |
| − | * [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]] | + | ** [[Сходимость цепных дробей]] |
| + | ** [[Цепные дроби как приближение к числу]] | ||
| + | ** [[Квадратичная иррациональность]] | ||
| + | ** [[Периодичность цепных дробей]] | ||
| + | ** [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]] | ||
* [[Уравнение Пелля]] | * [[Уравнение Пелля]] | ||
| − | + | * [[Представление простых в виде суммы двух квадратов]] | |
== Лекция - Конечные поля == | == Лекция - Конечные поля == | ||
=== Практика - Методы разложения полиномов на множители над конечными полями === | === Практика - Методы разложения полиномов на множители над конечными полями === | ||
Текущая версия на 19:03, 4 сентября 2022
Содержание
- 1 Лекция - Классы чисел и основная теорема арифметики
- 2 Лекция - Основные элементы теории чисел
- 3 Лекция - Основы теории групп
- 4 Лекция - Основы теории колец
- 5 Лекция - Основы теории полей
- 6 Лекция - Первообразные корни и квадратичные вычеты
- 7 Лекция - Квадратичные вычеты
- 8 Лекция - Аналитическая теория чисел
- 9 Лекция - Цепные (непрерывные) дроби и уравнение Пелля
- 10 Лекция - Конечные поля
Лекция - Классы чисел и основная теорема арифметики
- Классы чисел
- Натуральные числа
- Простые числа
- Наибольший общий делитель
- Основная теорема арифметики
- Теоремы о простых числах
Практика - Разложение на множители и длинная арифметика
- Системы счисления
- Арифметика чисел в b-ичной системе счисления (Длинная арифметика)
- Разложение на множители (факторизация)
Лекция - Основные элементы теории чисел
- Сравнения, система вычетов, решение линейных систем по модулю
- Китайская теорема об остатках
- Теорема Ферма
- Теорема Вильсона
- Мультипликативность функции, свертка Дирихле
- Функция Эйлера
- Количество делителей, сумма делителей
- Функция Мебиуса
Практика - Основные алгоритмы теории чисел
- Решето Эратосфена
- Быстрое возведение в степень
- Умножение по Монтгомери
- Дискретное преобразование Фурье
- Быстрое преобразование Фурье
Лекция - Основы теории групп
- Полугруппа, моноид, группа
- Абелева группа, Конечная группа
- Гомоморфизм групп, изоморфизм групп
- Подгруппа, нормальная подгруппа
- Порядок элемента группы, циклическая группа, конечно порожденная группа
- Регулярное представление группы
- Теорема о подгруппах циклической группы
- Смежные классы, теорема Лагранжа, факторгруппы
Практика - Основы теории групп
- Вычисление порядка элемента в группе
- Вычисление порядка перестановки в группе перестановок
- Дискретное логарифмирование в группе
- Действие группы на множестве
- Лемма Бернсайда, задача о числе ожерелий
- Представление групп
Лекция - Основы теории колец
- Определение кольца, подкольца, изоморфизмы колец
- Делители нуля, области целостности
- Единицы (обратимые элементы), группа обратимых элементов
- Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах
- Евклидовы кольца
Практика - Арифметика полиномов от одной переменной над полем
Лекция - Основы теории полей
- Определение поля и подполя, изоморфизмы полей
- Примеры полей
- Мультипликативная группа поля
- Расширения полей
Лекция - Первообразные корни и квадратичные вычеты
- Теорема о цикличности мультипликативной группы поля
- Первообразные корни
- Квадратичные вычеты, количество квадратичных вычетов по простому модулю
Практика - Первообразные корни и квадратичные вычеты
Лекция - Квадратичные вычеты
- Квадратичный закон взаимности
- Символ Якоби и его свойства
- Обобщенный квадратичный закон взаимности
- Алгоритм вычисления символа Якоби
Практика - Вероятностные тесты чисел на простоту
Лекция - Аналитическая теория чисел
- Факты из математического анализа
- Теорема Чебышёва
- Постулат Бертрана
- Уточнение констант в теореме Чебышёва
- Сумма обратных к простым
- Асимптотический закон распределения простых чисел
