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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Требует доработки
 
{{Требует доработки
|item1=Тут надо написать про алгоритм, который использует теорему Лагранжа. И работает за время <tex>O(\mathrm{FactorTime} \cdot \log |G|)</tex>.
+
|item1=(исправлено)Тут надо написать про алгоритм, который использует теорему Лагранжа. И работает за время <tex>O(\mathrm{FactorTime} \cdot \log |G|)</tex>.
 
}}
 
}}
  

Версия 19:32, 4 июля 2010

Эта статья требует доработки!
  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]