Алгоритм построения системы представителей циклов максимальной длины полиномиальных подстановок над кольцом Галуа | Прикладная дискретная математика. 2014. № 7 (Приложение).

В отличие от полей и колец вычетов, над кольцами Галуа не существует транзитивных полиномов, то есть биективных полиномов, которые реализуют полноцикловую подстановку. Максимальная длина цикла полиномиального преобразования над кольцом Галуа равна q(q - 1)p , где q - мощность кольца, а p - его характеристика. Предлагается алгоритм построения системы представителей всех циклов полиномиальных преобразований колец Галуа, имеющих максимальную длину. Сложность построенного алгоритма, выраженная в количестве операций умножения в кольце Галуа, равна O(lq ) при n, стремящемся к бесконечности, где l - степень многочлена полиномиального преобразования.