RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2017, выпуск 10, страницы 25–27 (Mi pdma355)

Теоретические основы прикладной дискретной математики

О показателе неизометричности преобразований

Б. А. Погореловa, М. А. Пудовкинаb

a Академия криптографии Российской Федерации, г. Москва
b Кафедра информационной безопасности Московского государственного технического университета им. Н. Э. Баумана, г. Москва

Аннотация: В связи с исследованием линейных и гомоморфных моделей имеется значительное число работ, посвящённых расстояниям преобразований до аффинных и импримитивных групп. Качественные криптографические преобразования должны такие структуры рассеивать. Аналогичные вопросы для групп изометрий метрических пространств практически не рассматривались.
В работе вводится мера, характеризующая степень рассеивания преобразованием разбиения множества биграмм метрического пространства $(\mu,{V_n}(2))$ и названная показателем неизометричности преобразования. Получены верхние оценки показателя неизометричности для некоторых классов преобразований. Показано, что этот показатель выражается через элементы матрицы разностей переходов. Указаны связи: 1) показателей неизометричности в классах аффинно-смежных преобразований; 2) показателей неизометричности преобразований относительно метрики и её подметрик; 3) в терминах метрики Хемминга между подстановками, максимально далёкими от импримитивных групп $S_{2^{n-1}}\wr S_2$, $S_2\wr S_{2^{n - 1}}$, и с подстановками с максимальным показателем неизометричности.

Ключевые слова: метрика Хемминга, группа изометрий, матрица разностей переходов, импримитивная группа.

УДК: 519.7

DOI: 10.17223/2226308X/10/9



© МИАН, 2024