221
правка
Изменения
м
Нет описания правки
== Постановка задачи ==Рассмотрим [[конечная группа|конечную группу]] <tex>G</tex>. Для заданного заданных <tex>a, b \in G</tex> необходимо найти такое минимальное <tex>n</tex>, что <tex>a^n=e</tex>. <br>Теперь рассмотрим '''обобщенную задачу поиска порядка''', также называемую '''задачей дискретного логарифмирования''': для заданных <tex>a</tex> и <tex>b</tex> из группы найти такое минимальное <tex>n</tex>или сказать, что <tex>a ^ n таких нет. == Алгоритм == b</tex>. <br>
Очевидно, <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>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>.
[[Категория: Теория групп]]
