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

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

Версия 17:51, 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]