О примитивности перемешивающих подстановок регистров сдвига

doi:10.17223/2226308X/10/4

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О примитивности перемешивающих подстановок регистров сдвига	524 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/2226308X/10/4

#перемешивающий граф преобразования

#примитивный граф

#экспонент графа

#регистр сдвига

#треугольное преобразование

Title: О примитивности перемешивающих подстановок регистров сдвига
Creator: Григорьев, Виталий Сергеевич
|
Фомичев, Владимир Михайлович
Date: 2017
DOI: 10.17223/2226308X/10/4
Description: Исследованы некоторые вопросы примитивности перемешивающих орграфов композиций регистровых подстановок и связь экспонентов прямой и обратной подстановок. Пусть G(g) —перемешивающий орграф подстановки g регистра левого сдвига длины n и {i,. .., im} — множество номеров существенных переменных функции обратной связи. Установлено, что орграф G(g) примитивный тогда и только тогда, когда примитивен орграф G(g-1). При этом exp G(g) = exp G(g-1), если ik + im+2-k = n + 2 для всех k = 2,... , m. Для подстановки g регистра правого сдвига длины n с обратной связью xn ® ф(х,. . . , xn -i) и подстановки h регистра левого сдвига длины n с обратной связью xi ®ф(х2, ..., xn) показано, что 1) множество дуг перемешивающего орграфа G(gh) состоит из n петель (по одной в каждой вершине) и дуг вида (i,n), где i £ {1,. . ., n — 1}, таких, что xi — существенная переменная функции ф(х1, . . . , xn-1) фф(х1, ... , xn-1); 2) множество дуг перемешивающего орграфа G(hg) состоит из n петель (по одной в каждой вершине) и дуг вида (i, 1), где i £ {2,. . ., n}, таких, что xi — существенная переменная функции ф 2, . . . , xn) ф ф ^ 2, ... , xn). Для преобразования g регистра правого сдвига длины n с обратной связью f(x1, . . . , xn) и треугольной подстановки h множества {0 ,1}n показано, что если орграф G(g) примитивный, то примитивными являются орграфы G(g) ■ G(h) и G(h) ■ G(g) и экспонент каждого из этих орграфов не превосходит exp G(g).