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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Практика - Разложение на множители и длинная арифметика)
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 8 участников)
Строка 1: Строка 1:
 
== Лекция - Классы чисел и основная теорема арифметики ==
 
== Лекция - Классы чисел и основная теорема арифметики ==
 
* [[Классы чисел]]
 
* [[Классы чисел]]
* [[Натуральные и целые числа]]
+
* [[Натуральные числа]]
 
* [[Простые числа]]
 
* [[Простые числа]]
 
* [[Наибольший общий делитель]]
 
* [[Наибольший общий делитель]]
Строка 12: Строка 12:
  
 
== Лекция - Основные элементы теории чисел ==
 
== Лекция - Основные элементы теории чисел ==
* [[Сравнения, вычеты, остатки]]
+
* [[Сравнения, система вычетов, решение линейных систем по модулю]]
* [[Теоретико-числовые функции]]
+
* [[Китайская теорема об остатках]]
 +
* [[Теорема Ферма]]
 +
* [[Теорема Вильсона]]
 +
* [[Мультипликативность функции, свертка Дирихле]]
 +
* [[Функция Эйлера]]
 +
* [[Количество делителей, сумма делителей]]
 +
* [[Функция Мебиуса]]
  
 
=== Практика - Основные алгоритмы теории чисел ===
 
=== Практика - Основные алгоритмы теории чисел ===
 +
* [[Решето Эратосфена]]
 +
* [[Быстрое возведение в степень]]
 +
* [[Умножение по Монтгомери]]
 +
* [[Дискретное преобразование Фурье]]
 +
* [[Быстрое преобразование Фурье]]
  
 
== Лекция - Основы теории групп ==
 
== Лекция - Основы теории групп ==
Строка 23: Строка 34:
 
* [[Подгруппа]], [[нормальная подгруппа]]
 
* [[Подгруппа]], [[нормальная подгруппа]]
 
* [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]
 
* [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]
 +
* [[Регулярное представление группы]]
 
* [[Теорема о подгруппах циклической группы]]
 
* [[Теорема о подгруппах циклической группы]]
 
* [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]
 
* [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]
Строка 50: Строка 62:
 
* [[Теорема о цикличности мультипликативной группы поля 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>]]
 +
** [[Лемма Гаусса для вычисления квадратичного характера числа по простому модулю]]
 
=== Практика - Первообразные корни и квадратичные вычеты ===
 
=== Практика - Первообразные корни и квадратичные вычеты ===
  
Строка 70: Строка 86:
 
* [[Сумма обратных к простым]]
 
* [[Сумма обратных к простым]]
 
* [[Асимптотический закон распределения простых чисел]]
 
* [[Асимптотический закон распределения простых чисел]]
 +
 
=== Практика - Вычисление <math>\pi(x)</math> ===
 
=== Практика - Вычисление <math>\pi(x)</math> ===
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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