Прикладная дискретная математика. Приложение
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ. Приложение:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Прикладная дискретная математика. Приложение, 2019, выпуск 12, страницы 80–83
DOI: https://doi.org/10.17223/2226308X/12/25
(Mi pdma440)
 

Математические методы криптографии

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

Я. Э. Авезова

АО «Позитив Текнолоджиз», г. Москва
Список литературы:
Аннотация: Для регистра сдвига длины $n$, функция обратной связи которого зависит от двоичного знака управляющей последовательности (на каждом такте реализуется одно из двух регистровых преобразований), исследовано минимальное число $\gamma$ тактов регистра, после которых достигнуто полное перемешивание, то есть существенная зависимость каждой координатной функции композиции преобразований от всех переменных. Эффект полного перемешивания оценен с помощью множества $\hat{\Gamma}$ перемешивающих $n$-вершинных орграфов регистровых преобразований, имеющих общий гамильтонов контур. Дана оценка экспонента $\exp\hat{\Gamma}$ примитивного множества $\hat{\Gamma}$, которая позволяет оценить снизу число $\gamma$:
$$ \exp\hat{\Gamma}\leq 2n-2+\textstyle\sum\limits_{\alpha=0}^1\left(F(n-S(\phi_\alpha))+d_\alpha+s_{m(\alpha)}^\alpha\right), $$
где $S(\phi_\alpha)=\left\{s_1^\alpha,\ldots,s_{m(\alpha)}^\alpha\right\}$ — множество номеров существенных переменных функции обратной связи $\phi_\alpha(x_0,\ldots,x_{n-1})$; $n-S(\phi_\alpha)=\{n-s_j^\alpha: j=1,\ldots,m(\alpha)\}$; $d_\alpha=\text{НОД}\{n-S(\phi_\alpha)\}$; $F(n-S(\phi_\alpha))=d_\alpha\Phi((n-S(\phi_\alpha))/d_\alpha)$; $\Phi((n-S(\phi_\alpha))/d_\alpha)$ — число Фробениуса. Проведён вычислительный эксперимент при $n=6$ и $10$ по вычислению точного значения $\gamma$ с учётом управляющей последовательности. Установлено, что полное перемешивание возможно за число тактов, превышающее значение экспонента менее чем в $2$ раза.
Ключевые слова: гамильтонов контур, примитивность множества орграфов, экспонент орграфа, экспонент множества орграфов.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.1
Образец цитирования: Я. Э. Авезова, “О перемешивающих свойствах нестационарного регистра сдвига”, ПДМ. Приложение, 2019, № 12, 80–83
Цитирование в формате AMSBIB
\RBibitem{Ave19}
\by Я.~Э.~Авезова
\paper О перемешивающих свойствах нестационарного регистра сдвига
\jour ПДМ. Приложение
\yr 2019
\issue 12
\pages 80--83
\mathnet{http://mi.mathnet.ru/pdma440}
\crossref{https://doi.org/10.17223/2226308X/12/25}
\elib{https://elibrary.ru/item.asp?id=41153880}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/pdma440
  • https://www.mathnet.ru/rus/pdma/y2019/i12/p80
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика. Приложение
    Статистика просмотров:
    Страница аннотации:109
    PDF полного текста:32
    Список литературы:15
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024