Изменения
Нет описания правки
|item1=Тут надо написать про алгоритм, который использует теорему Лагранжа. И работает за время <tex>O(\mathrm{FactorTime} \cdot \log |G|)</tex>.
}}
Пусть <tex>G</tex> - группа, <tex>a \in G</tex>.
По следствию из теоремы Лагранжа порядок элемента является делителем порядка группы.
Таким образом достаточно рассмотреть <tex>a^n</tex>, где <tex>n \in X</tex>, <tex>X</tex> - делители порядка группы.
'''Алгоритм:'''
1) Найти все делители <tex>|G|</tex> перебором от 1 до <tex>\sqrt{|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>
