|
Прикладная дискретная математика. Приложение, 2014, выпуск 7, страницы 64–67
(Mi pdma143)
|
|
|
|
Псевдослучайные генераторы
Алгоритм построения системы представителей циклов максимальной длины полиномиальных подстановок над кольцом Галуа
Д. М. Ермилов Лаборатория ТВП, г. Москва
Аннотация:
В отличие от полей и колец вычетов, над кольцами Галуа не существует транзитивных полиномов, то есть биективных полиномов, которые реализуют полноцикловую подстановку. Максимальная длина цикла полиномиального преобразования над кольцом Галуа равна $q(q-1)p^{n-2},$ где $q^n$ – мощность кольца, а $p^n$ – его характеристика. Предлагается алгоритм построения системы представителей всех циклов полиномиальных преобразований колец Галуа, имеющих максимальную длину. Сложность построенного алгоритма, выраженная в количестве операций умножения в кольце Галуа, равна $\mathrm O(lq^{n-1})$ при $n$, стремящемся к бесконечности, где $l$ – степень многочлена полиномиального преобразования.
Ключевые слова:
кольца Галуа, нелинейные рекуррентные последовательности.
Образец цитирования:
Д. М. Ермилов, “Алгоритм построения системы представителей циклов максимальной длины полиномиальных подстановок над кольцом Галуа”, ПДМ. Приложение, 2014, № 7, 64–67
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma143 https://www.mathnet.ru/rus/pdma/y2014/i7/p64
|
Статистика просмотров: |
Страница аннотации: | 181 | PDF полного текста: | 68 | Список литературы: | 39 |
|