Алгоритмы алгебры и теории чисел — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 87 промежуточных версий 14 участников)
Строка 1: Строка 1:
 
== Лекция - Классы чисел и основная теорема арифметики ==
 
== Лекция - Классы чисел и основная теорема арифметики ==
−
=== Классы чисел: натуральные, целые, рациональные, вещественные, комплексные ===
+
* [[Классы чисел]]
−
==== Определения натуральных чисел ====
+
* [[Натуральные числа]]
−
===== Неформальное определение =====
+
* [[Простые числа]]
−
===== Аксиомы Пеано =====
+
* [[Наибольший общий делитель]]
−
===== Теоретико-множественное определение =====
+
* [[Основная теорема арифметики]]
−
==== Определение целых, рациональных, вещественных и комплексных чисел ====
+
* [[Теоремы о простых числах]]
−
==== Операции сложения, вычитания, умножения, деления, извлечение корня ====
+
=== Практика - Разложение на множители и длинная арифметика ===
−
=== Натуральные и целые числа ===
+
* [[Системы счисления]]
−
==== Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел ====
+
* [[Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]]
−
==== Деление чисел с остатком ====
+
* [[Разложение на множители (факторизация)]]
−
=== Простые числа ===
+
 
−
==== Существование разложения на простые ====
 
−
=== Наибольший общий делитель ===
 
−
==== Наибольший общий делитель как максимальное число, делящее два данных числа ====
 
−
==== Алгоритм Евклида (обычный и расширенный) ====
 
−
==== Наибольший общий делитель как общий делитель, делящий все остальные общие делители ====
 
−
=== Основная теорема арифметики ===
 
−
==== Теорема о том, что если произведение двух чисел делится на простое, то одно из них на него делится ====
 
−
==== Основная теорема арифметики ====
 
−
=== Теоремы о простых числах ===
 
−
==== Теорема о существовании бесконечного числа простых чисел ====
 
−
==== Теорема о расходимости ряда <math>\sum \frac{1}{n}</math> ====
 
−
==== Теорема о сходимости ряда <math>\sum \frac{1}{n^2}</math> ====
 
−
==== Теорема о расходимости ряда <math>\sum \frac{1}{p}</math> ====
 
−
== Практика - Разложение на множители и длинная арифметика ==
 
−
=== Системы счисления ===
 
−
==== Позиционные системы счисления, запись числа в b-ичной системе счисления ====
 
−
==== Смешанные системы счисления ====
 
−
==== Фибоначчиева система счисления ====
 
−
=== Арифметика чисел в b-ичной системе счисления (Длинная арифметика) ===
 
−
==== Представление в памяти ====
 
−
==== Сложение, вычитание, умножение, деление на короткое, деление на длинное ====
 
−
==== Подбор значения очередной цифры в алгоритме деления в столбик ====
 
−
=== Разложение на множители (факторизация) ===
 
−
==== Проверка числа на простоту за <math>O(\sqrt{n})</math> ====
 
−
==== Разложение на множители за <math>O(\sqrt{n})</math> ====
 
−
=== Алгоритм Евклида ===
 
−
==== Числа Фибоначчи, формула Бине, асимптотика роста ====
 
−
==== Время работы алгоритма Евклида ====
 
−
==== Двоичный алгоритм Евклида, расширенный двоичный алгоритм Евклида ====
 
 
== Лекция - Основные элементы теории чисел ==
 
== Лекция - Основные элементы теории чисел ==
−
== Практика - Основные алгоритмы теории чисел ==
+
* [[Сравнения, система вычетов, решение линейных систем по модулю]]
 +
* [[Китайская теорема об остатках]]
 +
* [[Теорема Ферма]]
 +
* [[Теорема Вильсона]]
 +
* [[Мультипликативность функции, свертка Дирихле]]
 +
* [[Функция Эйлера]]
 +
* [[Количество делителей, сумма делителей]]
 +
* [[Функция Мебиуса]]
 +
 
 +
=== Практика - Основные алгоритмы теории чисел ===
 +
* [[Решето Эратосфена]]
 +
* [[Быстрое возведение в степень]]
 +
* [[Умножение по Монтгомери]]
 +
* [[Дискретное преобразование Фурье]]
 +
* [[Быстрое преобразование Фурье]]
 +
 
 
== Лекция - Основы теории групп ==
 
== Лекция - Основы теории групп ==
−
== Практика - Основы теории групп ==
+
* [[Полугруппа]], [[моноид]], [[группа]]
 +
* [[Абелева группа]], [[Конечная группа]]
 +
* [[Гомоморфизм групп]], [[изоморфизм групп]]
 +
* [[Подгруппа]], [[нормальная подгруппа]]
 +
* [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]
 +
* [[Регулярное представление группы]]
 +
* [[Теорема о подгруппах циклической группы]]
 +
* [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]
 +
=== Практика - Основы теории групп ===
 +
* [[Вычисление порядка элемента в группе]]
 +
* [[Вычисление порядка перестановки в группе перестановок]]
 +
* [[Дискретное логарифмирование в группе]]
 +
* [[Действие группы на множестве]]
 +
* [[Лемма Бернсайда, задача о числе ожерелий]]
 +
* [[Представление групп]]
 +
 
 
== Лекция - Основы теории колец ==
 
== Лекция - Основы теории колец ==
−
== Практика - Арифметика полиномов от одной переменной над полем ==
+
*[[Определение кольца, подкольца, изоморфизмы колец]]
 +
*[[Делители нуля, области целостности]]
 +
*[[Единицы (обратимые элементы), группа обратимых элементов]]
 +
*[[Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах]]
 +
*[[Евклидовы кольца]]
 +
=== Практика - Арифметика полиномов от одной переменной над полем ===
 +
 
 
== Лекция - Основы теории полей ==
 
== Лекция - Основы теории полей ==
 +
* [[Определение поля и подполя, изоморфизмы полей]]
 +
* [[Примеры полей]]
 +
* [[Мультипликативная группа поля]]
 +
* [[Расширения полей]]
 +
 
== Лекция - Первообразные корни и квадратичные вычеты ==
 
== Лекция - Первообразные корни и квадратичные вычеты ==
−
== Практика - Первообразные корни и квадратичные вычеты ==
+
* [[Теорема о цикличности мультипликативной группы поля 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>]]
 +
** [[Лемма Гаусса для вычисления квадратичного характера числа по простому модулю]]
 +
=== Практика - Первообразные корни и квадратичные вычеты ===
 +
 
 
== Лекция - Квадратичные вычеты ==
 
== Лекция - Квадратичные вычеты ==
−
== Практика - Вероятностные тесты чисел на простоту ==
+
*[[Квадратичный закон взаимности]]
 +
*[[Символ Якоби и его свойства]]
 +
*[[Обобщенный квадратичный закон взаимности]]
 +
*[[Алгоритм вычисления символа Якоби]]
 +
=== Практика - Вероятностные тесты чисел на простоту ===
 +
*[[Тест Ферма проверки чисел на простоту, числа Кармайкла]]
 +
*[[Тест Соловея-Штрассена]]
 +
*[[Тест Миллера-Рабина]]
 +
 
 
== Лекция - Аналитическая теория чисел ==
 
== Лекция - Аналитическая теория чисел ==
−
== Практика - Вычисление <math>\pi(x)</math> ==
+
* [[Факты из математического анализа]]
 +
* [[Теорема Чебышёва]]
 +
* [[Постулат Бертрана]]
 +
* [[Уточнение констант в теореме Чебышёва]]
 +
* [[Сумма обратных к простым]]
 +
* [[Асимптотический закон распределения простых чисел]]
 +
 
 +
=== Практика - Вычисление <math>\pi(x)</math> ===
 +
 
 
== Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==
 
== Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==
−
== Практика - Цепные (непрерывные) дроби и уравнение Пелля ==
+
* [[Цепная дробь]]
 +
** [[Связь цепных дробей и алгоритма Евклида]]
 +
** [[Сходимость цепных дробей]]
 +
** [[Цепные дроби как приближение к числу]]
 +
** [[Квадратичная иррациональность]]
 +
** [[Периодичность цепных дробей]]
 +
** [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]]
 +
* [[Уравнение Пелля]]
 +
* [[Представление простых в виде суммы двух квадратов]]
 +
 
 
== Лекция - Конечные поля ==
 
== Лекция - Конечные поля ==
−
== Практика - Методы разложения полиномов на множители над конечными полями ==
+
=== Практика - Методы разложения полиномов на множители над конечными полями ===

Текущая версия на 19:03, 4 сентября 2022

Лекция - Классы чисел и основная теорема арифметики

Практика - Разложение на множители и длинная арифметика

Лекция - Основные элементы теории чисел

Практика - Основные алгоритмы теории чисел

Лекция - Основы теории групп

Практика - Основы теории групп

Лекция - Основы теории колец

Практика - Арифметика полиномов от одной переменной над полем

Лекция - Основы теории полей

Лекция - Первообразные корни и квадратичные вычеты

Практика - Первообразные корни и квадратичные вычеты

Лекция - Квадратичные вычеты

Практика - Вероятностные тесты чисел на простоту

Лекция - Аналитическая теория чисел

Практика - Вычисление [math]\pi(x)[/math]

Лекция - Цепные (непрерывные) дроби и уравнение Пелля

Лекция - Конечные поля

Практика - Методы разложения полиномов на множители над конечными полями

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_алгебры_и_теории_чисел&oldid=84320»