#REDIRECT == Постановка задачи == Пусть <tex>G</tex> — [[группа]], <tex>a \in G</tex>. Требуется найти [[порядок элемента]] <tex>a</tex>. == Решение ==По следствию из [[теорема Лагранжа|теоремы Лагранжа]] порядок элемента является делителем [[Дискретное логарифмирование порядок группы|порядка группы]]. Таким образом достаточно рассмотреть <tex>a^n</tex>, где <tex>n \in X</tex>, <tex>X</tex> — делители порядка группы. === Алгоритм ===# Найти все делители <tex>|G|</tex> перебором от 1 до <tex>\sqrt{|G|}</tex># Для каждого делителя <tex>n</tex> проверить значение <tex>a^n</tex>. Наименьший <tex>n</tex>, такой что <tex>a^n = e</tex>, является порядком элемента <tex>a</tex> в группе. === Алгоритмическая сложность ===Перебор от <tex>1</tex> до <tex>\sqrt{|G|}</tex> выполняется за <tex>O(\sqrt{|G|})</tex>. Возведение <tex>a</tex> в степень <tex>n</tex> выполняется за <tex>O(\log n)</tex>. Следовательно время выполнения <tex>O(\sqrt{|G|} \cdot \log{|G|})</tex>. [[Категория:Теория групп]]
