Преломляющие биекции в тройках Штейнера | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/1

Преломляющие биекции в тройках Штейнера

Исследованы преломляющие биекции в тройках Штейнера, применяемые при построении матроидов и схем разделения секрета. Под преломляющими понимаются отображения F квазигруппы в себя, удовлетворяющие условию F(x * y) = = F(x) * F(y) при любых x = y. Предложены преломляющие биекции квазигрупп Штейнера с N = 9, 13 и 2п - 1 элементами при нечётных n, не делящихся на три, а также необходимые условия существования APN-биекций в GF(2n). При помощи наборов преломляющих биекций построены матроиды, являющиеся контрпримерами к гипотезе, что каждый однородный матроид определяет некоторую блок-схему.

Refractive bijections in Steiner triples.pdf Исследуются биекции квазигрупп, которые по аналогии с геометрическими преобразованиями, не переводящими никакую прямую в другую прямую, названы преломляющими. Преломляющие биекции применимы при построении APN-функций и как контрпример к гипотезе в теории схем разделения секрета: оказалось, что не каждый однородный матроид определяет некоторую блок-схему [1]. APN-биекции неоднократно изучались, в том числе вопросу существования взаимно однозначных APN-функ-ций от чётного числа переменных посвящены работы [2, 3]. Итеративные конструкции APN-функций исследованы в [4]. Построение систем троек Штейнера S, S', S'' на множестве G = {1, 2,..., N}, таких, что никакие две из них не содержат ни одной общей тройки [5], выглядит следующим образом: тройка {u,v,w} преобразуется в тройку {f (u),f (v),f (w)}, где 1) {f(u),f(v),f (w)}e S'; 2) {g(u),g(v),g(w)}E S" . Утверждение 1. Если существуют три биекции F(x) = f (x), F(x) = g(x) и F(x) = fg-1(x) квазигруппы Штейнера (S, *), являющиеся преломляющими, т.е. удовлетворяющие условию F(x * y) = F(x) * F(y) при любых x = y, то соответствующие им системы S, S', S'' не содержат ни одной общей тройки. Системы S, S', S'' образуются в результате применения преломляющих биекций к стандартным тройкам Штейнера [5]. Рассмотрим на множестве E = {a, b,c} U G = {a, b,c, 1, 2,..., N} семейство H че-тырёхэлементных подмножеств четырёх видов: 1) H = {a, u, v, w}, где {u, v, w} E S; 2) H = {b,i,j,k}, где {i,j,k}E S'; 3) H" = {c, x, y, z}, где {x,y,z}e S''; 4) H'' = {a, b, c, t}, где t E G. Утверждение 2. Семейство H удовлетворяет аксиомам гиперплоскостей матро-ида, оно не является семейством блоков никакой блок-схемы, причём двойственный матроид - однородный с мощностью циклов, равной n = N - 1. Таким образом описывается конструкция контрпримера. На данный момент рассмотрены линейные системы с N = 2n - 1, а также системы с N = 9 и нелинейные с N = 13. Оказалось, что при N = 7 таких S, S , S нет, при N = 9, 13 и 31 такие системы существуют, при N = 15 - пока неизвестно. Системы троек Штейнера на N элементах существуют тогда и только тогда, когда N = 1 (mod 6) или N = 3 (mod 6) [5]. Утверждение 3. При N = 9 существуют системы троек Штейнера S9, S'9, Sg без общих троек. Доказательство и построение преобразований, преломляющих прямые, производится методом решения задачи блокировки прямых [6], поскольку система троек S9 есть семейство прямых на аффинной плоскости порядка три. Утверждение 4. Биекции f = 9 = f (9-1) преобразующие стандартные тройки S13 первого типа [5], являются преломляющими. Пусть f (u ф v) = f (u) ф f (v) для любых различных ненулевых u и v из Fn, при этом в линейных системах троек Штейнера F(0) = 0. Это равносильно тому, что f преобразует любое двумерное подпространство пространства Fn в четырёхэлементное подмножество, содержащее нуль, но не являющееся двумерным подпространством, и является необходимым условием для APN-биекции f, сохраняющей нуль. Если A и B - линейные невырожденные преобразования пространства Fn, то для суперпозиции биекций AfB имеем A(f (B(u ф v))) = A(f (Bu ф Bv)) = A(f (Bu) ф ф f(Bv)) = Af(Bu) ф Af(Bv), A(f(B(0))) = 0, то есть AfB тоже обладает этим свойством. Нетрудно проверить, что в GF(2n) при n =3 (т. е. N = 7) суперпозиция любых двух преломляющих биекций не является преломляющей. Поэтому представляет интерес случай n > 3. Утверждение 5. Функция F(u) = u-3 не сохраняет двумерные линейные подпространства в GF(2n) при нечётном n, т.е. является преломляющей, тогда и только тогда, когда GF(2n) не содержит GF(23), то есть n не делится на 3. Утверждение 6. При нечётном n, где n не делится на 3, функции f (u) = u3 и F(u) = u-3 являются преломляющими вместе с функцией g(u) = u-1. Это утверждение вместе с утверждениями 1 и 2 позволяет строить однородные матроиды мощности 2n + 2, удобные для использования в схемах разделения секрета, не сводящиеся к блок-схемам, для нечётных n ^ 5 при помощи систем линейных троек Штейнера с квазигрупповой операцией ф. 1 2 3 4 5 6 7 8 9 10 11 12 13 ' 13 1 2 4 8 12 11 10 7 6 9 5 3 1 2 3 4 5 6 7 8 9 10 11 12 13 \\ 8 6 10 2 11 3 1 12 4 5 7 13 9 у ( 1 2 3 4 5 6 78 9 10 11 12 13 12 7 4 9 1 8 53 11 2 13 10 6 Однако поскольку APN-биекции, сохраняющие нуль, являются преломляющими, стоит отметить отрицательный результат. Утверждение 7. Биекция F(u) = u-3 не является APN-функцией.

Ключевые слова

преломляющие биекции, квазигруппы Штейнера, матроиды, refracting bijections, Steiner quasigroups, matroids

Авторы

ФИООрганизацияДополнительноE-mail
Ведунова Марина ВикторовнаУральский государственный университет путей сообщениястуденткаmarina.vedunova.13.99@gmail.com
Геут Кристина ЛеонидовнаУральский государственный университет путей сообщениястарший преподаватель кафедры естественнонаучных дисциплинgeutkrl@yandex.ru
Игнатова Анастасия ОлеговнаУральский государственный университет путей сообщениястуденткаanastasiaignatova101@gmail.com
Титов Сергей СергеевичУральский государственный университет путей сообщениядоктор физико-математических наук, профессорsergey.titov@usaaa.ru
Всего: 4

Ссылки

Медведев Н. В., Титов С. С. Об однородных матроидах и блок-схемах // Прикладная дискретная математика. Приложение. 2017. №10. C. 21-23.
Идрисова В. А. Векторные 2-в-1 функции как подфункции взаимно однозначных APN-функций // Прикладная дискретная математика. Приложение. 2018. №11. С. 39-41.
Виткуп В. А. О специальном подклассе векторных булевых функций и проблеме существования APN-перестановок // Прикладная дискретная математика. Приложение. 2016. №9. С. 19-21.
Фролова А. А. Итеративная конструкция APN-функций // Прикладная дискретная математика. Приложение. 2013. №6. С. 24-25.
Холл М. Комбинаторика: пер. с англ. М.: Мир, 1970. 424с.
Ведунова М. В., Игнатова А. О., Геут К. Л. Блокировка линейных многообразий и тройки Штейнера // Прикладная дискретная математика. Приложение. 2019. №12. C. 93-95.
 Преломляющие биекции в тройках Штейнера | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/1

Преломляющие биекции в тройках Штейнера | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/1