Изменения

Рассмотрим конечную группу == Решение ==По следствию из [[теорема Лагранжа|теоремы Лагранжа]] порядок элемента является делителем [[порядок группы|порядка группы]]. Таким образом достаточно рассмотреть <mathtex>Ga^n</mathtex>. Для заданного , где <mathtex>an \in X</mathtex> необходимо найти такое минимальное , <mathtex>nX</mathtex>, что — делители порядка группы. === Алгоритм ===# Найти все делители <mathtex>a^n=e|G|</mathtex>. перебором от 1 до <tex>\sqrt{|G|}<br/tex>Теперь рассмотрим '''обобщенную задачу поиска порядка''', также называемую '''задачей дискретного логарифмирования''': для заданных # Для каждого делителя <mathtex>an</mathtex> и проверить значение <mathtex>ba^n</mathtex> из группы найти такое минимальное . Наименьший <mathtex>n</mathtex>, такой что <mathtex>a ^ n = be</tex>, является порядком элемента <tex>a</mathtex>в группе.  === Алгоритмическая сложность ===Перебор от <brtex>Очевидно, 1<math/tex>n до < tex>\sqrt{|G| }</mathtex> (следует из принципа Дирихле). Пусть выполняется за <mathtex>m = O(\lceil sqrt{|G| \rceil})</mathtex>. Будем искать Возведение <mathtex>na</mathtex> в виде степень <mathtex>xm-yn</mathtex>, где выполняется за <mathtex>y O(\in 0 \dots m - 1log n)</mathtex> и . Следовательно время выполнения <mathtex>x O(\sqrt{|G|} \in 1 cdot \dots mlog{|G|})</mathtex>.<br><math>a ^ n = a ^ {xm - y} = b</math><math>a ^ {xm} = b a ^ {y}[[Категория:Теория групп]]