Просмотр исходного текста страницы Вычисление порядка элемента в группе

{{Требует доработки
|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>