Викиконспекты - Вклад участника [ru]

Дискретное логарифмирование в группе

2010-07-01T08:50:56Z

Vprisivko: Исправление

{{Требует доработки
|item1= '''(Исправлено)''' Зачем нужен алгоритм с временем работы <tex>O(|G| log |G|)</tex>, если можно просто перебрать все степени за <tex>O(|G|)</tex>?
}}

Рассмотрим конечную группу <tex>G</tex>. Для заданного <tex>a</tex> необходимо найти такое минимальное <tex>n</tex>, что <tex>a^n=e</tex>. 
Теперь рассмотрим '''обобщенную задачу поиска порядка''', также называемую '''задачей дискретного логарифмирования''': для заданных <tex>a</tex> и <tex>b</tex> из группы найти такое минимальное <tex>n</tex>, что <tex>a ^ n = b</tex>. 
Очевидно, <tex>n < |G| </tex> (следует из принципа Дирихле). Пусть <tex>m = \lceil \sqrt{|G|} \rceil</tex>. Будем искать <tex>n</tex> в виде <tex>xm-y</tex>, где <tex>y \in 0 \dots m - 1</tex> и <tex>x \in 1 \dots m</tex> (такое представление существует и единственно на основании существования и единственности деления с остатком). 
<tex>a ^ n = a ^ {xm - y} = b</tex> 
<tex>a ^ {xm} = b a ^ {y}</tex> 
<tex> {a ^ m} ^ x = b a ^ y </tex> 

Далее мы выписываем все полученные выражения для левой и правой частей при всех допустимых <tex>x</tex> и <tex>y</tex> (или складываем в удобную структуру данных: отсортированный массив, хеш, дерево и т. д.). После чего ищем пересечение. Для каждого элемента одной части поиск в структуре данных для другой части (в случае с отсортированным массивом) занимает время <tex>O(log m)</tex>. Учитывая, что время на предварительную обработку <tex>O(m)</tex>, общее время работы алгоритма − <tex>O(m log m) = O(\sqrt{|G|} log \sqrt{|G|})</tex>.

[[Категория: Теория групп]]

Представление групп

2010-06-29T11:22:20Z

Vprisivko: Определяющие соотношения

{{В разработке}}

== Свободная группа ==
Рассмотрим конечный алфавит <math> \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} </math>. 
Рассмотрим множество строк над алфавитом <math> \Sigma \cup \Sigma^{-1} ; \; S = S_1 S_2 \dots S_k , \; символ a \in \Sigma \cup \Sigma^{-1} </math>. 

{{Определение
|definition=
<math>S</math> и <math>S'</math> называются '''эквивалентными''', если они могут быть превращены друг в друга вставками и удалениями из произвольных мест <math>aa^{-1}</math> и <math>a^{-1}a</math>.
}}

Таким образом, <math> \Sigma \cup \Sigma^{-1} </math> с операцией конкатенации будет группой (обратным элементом будет обращение строки с заменой всех символов на «обратные» им).

{{Определение
|definition=
<math> \Sigma \cup \Sigma^{-1} </math> называется '''свободной группой, порожденной алфавитом <math>\Sigma</math>'''.
}}

Рассмотрим строку. Проредуцируем её (будем последовательно удалять <math>aa^{-1}</math> из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: ''правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?''

{{Теорема
|statement=
У одной строки существует лишь одна редуцированная строка
|proof=
Пусть существуют 2 проредуцированные строки <math>\omega_1</math> и <math>\omega_2</math>, заданные одной строкой. Тогда существуют цепочки вставок и удалений 
<math>\omega_1 \rightarrow S_1 \rightarrow S_2 \dots \rightarrow S_k \rightarrow \omega_2 </math>, где <math>\rightarrow</math> − операция вставки или удаления <math>aa^{-1}</math>. (Существование цепочки обеспечено тем, что эти строки образованы одним элементом). 

Среди цепочек рассмотрим такую, у которой минимально <math>\sum |S_i|</math> и пусть <math>S_i</math> − строка наибольшей длины. 
Рассмотрим <math> S_{i - 1} \rightarrow S_i \rightarrow S_{i + 1} </math>, причем мы знаем, что переходы от <math>i</math> к <math>i - 1</math> и <math>i + 1</math> обеспечены за счет удаления (из-за того, что длина <math>S_i</math> максимальна). Эти переходы могут быть обеспечены за счет:
# Двух непересекающихся пар. Тогда пусть <math> S_{i - 1} = L_1 L_2 b b^{-1} L_3, \quad S_i = L_1 a a^{-1} L_2 b b^{-1} L_3, \quad S_{i + 1} = L_1 a a^{-1} L_2 L_3 </math>, где <math>L_1, L_2, L_3</math> − некие строки. Таким образом, у нас есть часть цепочки <math>L_1 L_2 b b^{-1} L_3 \rightarrow L_1 a a^{-1} L_2 b b^{-1} L_3 \rightarrow L_1 a a^{-1} L_2 L_3 </math>. Заменим эту часть цепочки на <math>L_1 L_2 b b^{-1} L_3 \rightarrow L_1 L_2 L_3 \rightarrow L_1 a a^{-1} L_2 L_3 </math>. Заметим, что крайние значения части цепочки от этого не изменятся, но <math>\sum |S_i|</math> уменьшится, а это противоречит нашему предположению о минимальности суммы.
# Пар, пересекающихся по двум позициям. Тогда <math>S_{i-1} = S_{i+1}</math>, и можно избавиться от <math>S_{i}</math> и <math>S_{i + 1}</math>, и от этого сумма длин слов также уменьшится.
# Пар, пересекающихся по одной позиции. Имеем <math>L_1 a L_2 \rightarrow L_1 a a^{-1} a L_2 \rightarrow L_1 a L_2</math>, и в этом случае мы также можем избавиться от <math>S_{i}</math> и <math>S_{i + 1}</math>, что также уменьшит итоговую сумму длин строк.
Таким образом, мы пришли к противоречию во всех случаях, а это значит, что мы доказали теорему.
}}

== Задание группы определяющими соотношениями ==
Пусть также имеем алфавит <math>\Sigma = \{ a_1, \dots a_n \} </math> и набор пар строк <math>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</math>. Разрешается где угодно менять <math>\omega_i</math> на <math>S_i</math> и наоборот.

{{Определение
|definition=
Выражения <math>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</math> называются '''определяющими соотношениями'''.
}}

{{Утверждение
|about=без доказательства
|statement=
Задача проверки эквивалентности строк при заданных определяющих соотношениях алгоритмически неразрешима.
}}

[[Категория:Теория групп]]

Представление групп

2010-06-29T10:45:28Z

Vprisivko: /* Свободная группа */ дописано

Представление групп

2010-06-29T10:12:42Z

Vprisivko: /* Свободная группа */

Представление групп

2010-06-29T10:12:22Z

Vprisivko: Создание статьи

Лемма Бернсайда, задача о числе ожерелий

2010-06-29T09:14:10Z

Vprisivko: Исправлена опечатка

{{В разработке}}

{{Лемма
|id=l1
|about=Бернсайда
|statement=
Число орбит <math> = \frac { \sum_{g \in G} |Fix(g)| } { |G| } </math>
}}

{{Утверждение
|id=s1
|about=1
|statement=
<math> |Orb(x)| = \frac { |G| } { |St(x) } </math>
}}

Преобразуем выражение для числа орбит, полученное из леммы Бернсайда. 
<math>\frac { \sum_{g \in G} |Fix(g)| } { |G| } = \frac { \sum_{ g \in G } \sum_{ x \in X } \{gx = x\} } { |G| } = \frac { \sum_{ x \in X } \sum_{ g \in G } \{gx = x\} } { |G| }
= \frac { \sum_{ x \in X } |St(x)| } { |G| } = \sum_{ x \in X } \frac {1} { |Orb(x)| } </math> 
Последнее преобразование выполнено на основании утверждения 1.

[[Категория:Теория групп]]

Лемма Бернсайда, задача о числе ожерелий

2010-06-29T09:11:09Z

Vprisivko: Создание статьи

{{В разработке}}

{{Лемма
|id=l1
|about=Бернсайда
|statement=
Число орбит <math> = \frac { \sum_{g \in G} |Fix(g)| } { |G| } </math>
}}

{{Утверждение
|id=s1
|about=1
|statement=
<math> |Orb(x)| = \frac { |G| } { |St(x) } </math>
}}

Преобразуем выражение для числа орбит, полученное из леммы Бернсайда. 
<math>\frac { \sum_{g \in G} |Fix(g)| } { |G| } = \frac { \sum_{ g \in G } \sum_{ x \in X } \{gx = x\} } { |G| } = \frac { \sum_{ x \in X } \sum_{ g \in G } \{gx = x\} } { |G| }
= \frac { \sum_{ x \in X } |St(x)| } { |G| } = \sum_{ x \in X } \frac {1} { Orb(x) } </math> 
Последнее преобразование выполнено на основании утверждения 1.

[[Категория:Теория групп]]

Действие группы на множестве

2010-06-29T08:53:42Z

Vprisivko:

{{В разработке}}

Пусть имеется множество <math>X</math>.
{{Определение
|definition=
<math>G</math> действует на <math>X</math>, если
# <math> \forall g \in G , x \in X \quad gx \in X </math>
# <math> \forall g_1, g_2 \in G , x \in X \quad (g_1 g_2)x = g_1(g_2 x) </math>
# <math> \forall x \in X \quad ex = x </math>
}}

{{Определение
|definition=
'''Орбита''' <math>Orb(x)=\{gx \mid g \in G\}</math>
}}

{{Определение
|definition=
'''Стабилизатор''' <math>St(x)=\{g \in G \mid gx = x\}</math>
}}

{{Определение
|definition=
'''Фиксатор''' <math>Fix(g)=\{x \in X \mid gx = x\}</math>
}}

{{Утверждение
|id=th1
|statement=
Стабилизатор замкнут относительно операции в группе (умножения)
|proof=
<math> \forall g_1, g_2 \in G g_1, g_2 \in St(x) \Rightarrow g_1 x = x \And g_2 x = x \Rightarrow (g_1 g_2) x = g_1 (g_2 x) = g_1 x = x </math>
}}

{{Утверждение
|id=th2
|statement=
<math> Orb(x) \cap Orb(y) \neq \varnothing \Rightarrow Orb(x) = Orb(y) </math>
|proof=
<math> Orb(x) \cap Orb(y) \neq \varnothing \Rightarrow \exist g_1, g_2 \in G : g_1 x = g_2 y \Rightarrow x = g_1 ^ {-1} g_2 y \Rightarrow x \in Orb(y) \Rightarrow Orb(x) \subseteq Orb(y) </math>. 

Аналогично доказываем, что <math>Orb(y) \subseteq Orb(x)</math>, откуда следует, что <math>Orb(x) = Orb(y)</math>
}}

Видно, что бинарное отношение <math>x \mathcal R y \Leftrightarrow Orb(x) = Orb(y)</math> является отношением эквивалентности на <math>X</math> и разбивает его на независимые классы эквивалентности − орбиты. Можно поставить задачу о нахождении количества орбит, которая решается с помощью [[Лемма Бернсайда, задача о числе ожерелий|леммы Бернсайда]].

[[Категория: Теория групп]]

Действие группы на множестве

2010-06-29T06:09:40Z

Vprisivko: добавлено 2 утверждения

Действие группы на множестве

2010-06-28T20:55:40Z

Vprisivko: Создание статьи, базовые понятия

Вычисление порядка элемента в группе

2010-06-28T20:22:32Z

Vprisivko: Редирект

#REDIRECT [[Дискретное логарифмирование в группе]]

Дискретное логарифмирование в группе

2010-06-28T20:22:16Z

Vprisivko: Создание статьи (перенесена из Вычисление порядка элемента в группе)

{{В разработке}}

Рассмотрим конечную группу <math>G</math>. Для заданного <math>a</math> необходимо найти такое минимальное <math>n</math>, что <math>a^n=e</math>. 
Теперь рассмотрим '''обобщенную задачу поиска порядка''', также называемую '''задачей дискретного логарифмирования''': для заданных <math>a</math> и <math>b</math> из группы найти такое минимальное <math>n</math>, что <math>a ^ n = b</math>. 
Очевидно, <math>n < |G| </math> (следует из принципа Дирихле). Пусть <math>m = \lceil |G| \rceil</math>. Будем искать <math>n</math> в виде <math>xm-y</math>, где <math>y \in 0 \dots m - 1</math> и <math>x \in 1 \dots m</math>. 
<math>a ^ n = a ^ {xm - y} = b</math> 
<math>a ^ {xm} = b a ^ {y}</math> 
<math> {a ^ m} ^ x = b a ^ y </math> 

Далее мы выписываем все полученные выражения для левой и правой частей при всех допустимых <math>x</math> и <math>y</math> (или складываем в удобную структуру данных: отсортированный массив, хеш, дерево и т. д.). После чего ищем пересечение. Для каждого элемента одной части поиск в структуре данных для другой части (в случае с отсортированным массивом) занимает время <math>O(log |G|)</math>. Учитывая, что время на предварительную обработку <math>O(|G|)</math>, общее время работы алгоритма − <math>O(|G| log |G|)</math>.

Вычисление порядка перестановки в группе перестановок

2010-06-28T20:15:56Z

Vprisivko: Написана статья

{{В разработке}}

Для нахождения порядка перестановки достаточно разложить её в произведение независимых циклов (циклических перестановок). Тогда порядок перестановки будет равен НОК длин всех циклов.
{{Лемма
|statement=
Для того, чтобы при перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы каждый цикл был пройден целое число раз.
|proof=
Для того, чтобы при перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы любой ее элемент перешел сам в себя, что равносильно тому, что цикл, в который он входит, пройден целое число раз (если пройден не целое, то элемент не перейдет сам в себя)
}}
{{Теорема
|statement=
Порядок перестановки равен НОК длин всех её независимых циклов.
|proof=
Поскольку при умножении на себя каждый цикл сдвигается на 1, то для того, чтобы перестановка перешла сама в себя, необходимо и достаточно, в силу леммы, чтобы степень перестановки делилась на все длины циклов. Минимальным таким числом является НОК длин циклов.
}}

Вычисление порядка элемента в группе

2010-06-28T19:59:50Z

Vprisivko:

Вычисление порядка элемента в группе

2010-06-28T19:50:02Z

Vprisivko: Создание статьи

Алгоритмы алгебры и теории чисел

2010-06-28T19:25:24Z

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

== Лекция - Классы чисел и основная теорема арифметики ==
=== Практика - Разложение на множители и длинная арифметика ===
== Лекция - Основные элементы теории чисел ==
=== Практика - Основные алгоритмы теории чисел ===

== Лекция - Основы теории групп ==
=== Практика - Основы теории групп ===
* [[Вычисление порядка элемента в группе]]
* [[Вычисление порядка перестановки в группе перестановок]]
* [[Дискретное логарифмирование в группе]]
* [[Действие группы на множестве]]
* [[Лемма Бернсайда, задача о числе ожерелий]]
* [[Представление групп]]

== Лекция - Основы теории колец ==
=== Практика - Арифметика полиномов от одной переменной над полем ===
== Лекция - Основы теории полей ==
* [[Определение поля и подполя, изоморфизмы полей]]
* [[Примеры полей]]
* [[Мультипликативная группа поля]]
* [[Характеристика поля, простые поля, классификация простых полей]]
* [[Поле как линейное пространство над своим подполем]]
* [[Расширения полей]]
* [[Поле частных кольца, поле Q как поле частных кольца Z]]

== Лекция - Первообразные корни и квадратичные вычеты ==
* [[Теорема о цикличности мультипликативной группы поля Z/pZ|Теорема о цикличности мультипликативной группы поля <tex>\mathbb{Z}/p\mathbb{Z}</tex>]]
* [[Первообразные корни]]
* [[Квадратичные вычеты]]
=== Практика - Первообразные корни и квадратичные вычеты ===

== Лекция - Квадратичные вычеты ==
*[[Квадратичные вычеты часть 2|Квадратичные вычеты]]
*[[Цепные дроби]]
=== Практика - Вероятностные тесты чисел на простоту ===
*[[Тест Ферма проверки чисел на простоту, числа Кармайкла]]
*[[Тест Соловея-Штрассена]]
*[[Тест Миллера-Рабина]]

== Лекция - Аналитическая теория чисел ==
* [[Факты из математического анализа]]
* [[Теорема Чебышёва]]
* [[Постулат Бертрана]]
* [[Уточнение констант в теореме Чебышёва]]
* [[Сумма обратных к простым]]
* [[Асимптотический закон распределения простых чисел]]
=== Практика - Вычисление <math>\pi(x)</math> ===

== Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==
* [[Цепные дроби, рекуррентные формулы для числителей и знаменателей дробей]]
* [[Цепные дроби как приближение к числу]]
* [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]]
* [[Уравнение Пелля]]
=== Практика - Цепные (непрерывные) дроби и уравнение Пелля ===

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