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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 1 промежуточная версия 1 участника)
(нет различий)

Текущая версия на 11:44, 1 сентября 2022

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

Пусть [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].