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

Эта статья требует доработки!

1. (исправлено)Тут надо написать про алгоритм, который использует теорему Лагранжа. И работает за время [math]O(\mathrm{FactorTime} \cdot \log |G|)[/math].

Если Вы исправили некоторые из указанных выше замечаний, просьба дописать в начало соответствующего пункта (Исправлено).

Пусть [math]G[/math] - группа, [math]a \in G[/math]. По следствию из теоремы Лагранжа порядок элемента является делителем порядка группы. Таким образом достаточно рассмотреть [math]a^n[/math], где [math]n \in X[/math], [math]X[/math] - делители порядка группы.

Алгоритм:

1) Найти все делители [math]|G|[/math] перебором от 1 до [math]\sqrt{|G|}[/math]

2) Для каждого делителя [math]n[/math] проверить значение [math]a^n[/math]. Наименьший n, такой что [math]a^n = e[/math], является порядком элемента [math]a[/math] в группе.

Алгоритмическая сложность: Перебор от 1 до [math]\sqrt{|G|}[/math] выполняется за [math]O(\sqrt{|G|})[/math]. Возведение [math]a[/math] в степень [math]n[/math] выполняется за [math]O(\log n)[/math]. Следовательно время выполнения [math]O(\sqrt{|G|} \cdot \log{|G|})[/math]