Изменения

== Постановка задачи == Пусть <tex>G</tex> — [[группа]], <tex>a \in G</tex>. Требуется найти [[порядок элемента]] <tex>a</tex>. == Решение ==По следствию из [[теорема Лагранжа|теоремы Лагранжа]] порядок элемента является делителем [[порядок группы|порядка группы]]. Таким образом достаточно рассмотреть <tex>a^n</tex>, где <tex>n \in X</tex>, <tex>X</tex> — делители порядка группы. === Алгоритм ===# Найти все делители <tex>|G|</tex> перебором от 1 до <tex>\sqrt{{Требует доработки|G|}</tex>|item1# Для каждого делителя <tex>n</tex> проверить значение <tex>a^n</tex>. Наименьший <tex>n</tex>, такой что <tex>a^n =Тут надо написать про алгоритмe</tex>, который использует теорему Лагранжаявляется порядком элемента <tex>a</tex> в группе. === Алгоритмическая сложность ===Перебор от <tex>1</tex> до <tex>\sqrt{|G|}</tex> выполняется за <tex>O(\sqrt{|G|})</tex>. И работает Возведение <tex>a</tex> в степень <tex>n</tex> выполняется за <tex>O(\log n)</tex>. Следовательно время выполнения <tex>O(\mathrmsqrt{FactorTime|G|} \cdot \log {|G|})</tex>.}}[[Категория:Теория групп]]