Дискретное логарифмирование в группе — различия между версиями
Vprisivko (обсуждение | вклад) (Исправление) |
м (rollbackEdits.php mass rollback) |
||
(не показано 7 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
− | + | == Постановка задачи == | |
− | | | + | Рассмотрим [[конечная группа|конечную группу]] <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^m}^x = b a^y</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>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>. | ||
[[Категория: Теория групп]] | [[Категория: Теория групп]] |
Текущая версия на 19:06, 4 сентября 2022
Постановка задачи
Рассмотрим конечную группу . Для заданных необходимо найти такое минимальное , что или сказать, что таких нет.
Алгоритм
Очевидно,
(следует из принципа Дирихле). Пусть . Будем искать в виде , где и (такое представление существует и единственно на основании существования и единственности деления с остатком). Таким образом . Следовательно,Далее мы выписываем все полученные выражения для левой и правой частей при всех допустимых
и (или складываем в удобную структуру данных: отсортированный массив, хеш, дерево и т. д.). После чего ищем пересечение.Время работы алгоритма
Для каждого элемента одной части поиск в структуре данных для другой части (в случае с отсортированным массивом) занимает время
. Учитывая, что время на предварительную обработку , общее время работы алгоритма — .