Дискретное логарифмирование в группе — различия между версиями
м |
|||
| Строка 1: | Строка 1: | ||
| − | Рассмотрим [[конечная группа|конечную группу]] <tex>G</tex>. Для | + | == Постановка задачи == |
| − | + | Рассмотрим [[конечная группа|конечную группу]] <tex>G</tex>. Для заданных <tex>a, b \in G</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>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^m}^x = 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>. | + | Далее мы выписываем все полученные выражения для левой и правой частей при всех допустимых <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>. | ||
[[Категория: Теория групп]] | [[Категория: Теория групп]] | ||
Версия 02:03, 18 сентября 2010
Постановка задачи
Рассмотрим конечную группу . Для заданных необходимо найти такое минимальное , что или сказать, что таких нет.
Алгоритм
Очевидно, (следует из принципа Дирихле). Пусть . Будем искать в виде , где и (такое представление существует и единственно на основании существования и единственности деления с остатком). Таким образом . Следовательно,
Далее мы выписываем все полученные выражения для левой и правой частей при всех допустимых и (или складываем в удобную структуру данных: отсортированный массив, хеш, дерево и т. д.). После чего ищем пересечение.
Время работы алгоритма
Для каждого элемента одной части поиск в структуре данных для другой части (в случае с отсортированным массивом) занимает время . Учитывая, что время на предварительную обработку , общее время работы алгоритма — .
