|
Прикладная дискретная математика, 2015, номер 1(27), страницы 52–61
(Mi pdm488)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Псевдослучайные генераторы
Свойства полиномиальных генераторов с выходной последовательностью наибольшего периода над кольцом Галуа
Д. М. Ермилов Лаборатория ТВП, г. Москва, Россия
Аннотация:
Пусть $R=\mathrm{GR}(q^n,p^n)$ – кольцо Галуа мощности $q^n$ и характеристики $p^n$, где $q=p^m$, и $G_{f,R}$ – граф биективного преобразования кольца $R$, задаваемого полиномом $f(x)\in R[x]$. Если $n>1$ или $q\not=p$, то граф $G_{f,R}$ не может быть циклом. Максимальная длина цикла в таком графе не превосходит $q(q-1)p^{n-2}$. Полиномы, для которых граф $G_{f,R}$ содержит цикл указанной длины, назовём полиномами с максимальной длиной цикла. Для таких полиномов предложен алгоритм проверки, лежит ли заданный элемент кольца на каком-либо цикле длины $q(q-1)p^{n-2}$ графа $G_{f,R}$. Алгоритм требует выполнения порядка $dq$ операций умножения и порядка $dq$ операций сложения в кольце $R$, $d=\deg{f(x)}$, $d<|R|$. Предложен также алгоритм построения системы представителей различных циклов графа $G_{f,R}$, имеющих длину $q(q-1)p^{n-2}$. Алгоритм построения представителей всех циклов длины $q(q-1)p^{n-2}$ требует выполнения порядка $d(q-1)q^{n-1}$ операций умножения и порядка $d(q-1)q^{n-1}$ операций сложения в кольце $R$. Алгоритм построения представителей $M$ различных циклов длины $q(q-1)p^{n-2}$ требует выполнения порядка $d(q-1)q^{k-1}$ операций умножения и порядка $d(q-1)q^{k-1}$ операций сложения в кольце $R$, где $k=\lceil\log_{q/p}M\rceil+1$.
Ключевые слова:
кольца Галуа, нелинейные генераторы, псевдослучайные последовательности, полиномиальный конгруэнтный генератор.
Образец цитирования:
Д. М. Ермилов, “Свойства полиномиальных генераторов с выходной последовательностью наибольшего периода над кольцом Галуа”, ПДМ, 2015, № 1(27), 52–61
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm488 https://www.mathnet.ru/rus/pdm/y2015/i1/p52
|
Статистика просмотров: |
Страница аннотации: | 210 | PDF полного текста: | 93 | Список литературы: | 30 |
|