Изменения

{{Требует доработки== Постановка задачи == |item1=(исправлено)Тут надо написать про алгоритмПусть <tex>G</tex> — [[группа]], который использует теорему Лагранжа. И работает за время <tex>O(\mathrm{FactorTime} \cdot a \log |in G|)</tex>.}}Требуется найти [[порядок элемента]] <tex>a</tex>.

Пусть <tex>G</tex> - группа, <tex>a \in G</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> перебором от 1 до . Возведение <tex>a</tex> в степень <tex>n</tex> выполняется за <tex>O(\log n)</tex>. Следовательно время выполнения <tex>O(\sqrt{|G|}\cdot \log{|G|})</tex>.

2) Для каждого делителя <tex>n</tex> проверить значение <tex>a^n</tex>. Наименьший n, такой что <tex>a^n = e</tex>, является порядком элемента <tex>a</tex> в группе.  ''Алгоритмическая сложность[[Категория:'' Перебор от 1 до <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>Теория групп]]