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

Постановка задачи

Пусть [math]G[/math] — группа, [math]a \in G[/math]. Требуется найти порядок элемента [math]a[/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]. Наименьший [math]n[/math], такой что [math]a^n = e[/math], является порядком элемента [math]a[/math] в группе.

Алгоритмическая сложность

Перебор от [math]1[/math] до [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].