On maximal metrically regular sets.pdf Рассмотрим Fn - пространство двоичных векторов длины n. Расстояние Хэммин-га d(x,y) между двумя векторами x,y Е Fn равно количеству координат, в которых эти векторы различаются. Пусть X С Fn - произвольное множество, y Е Fn - произвольный вектор. Расстояние от у до X определяется как d(y,X) = mind(y,x). Максимальным расстоянием x€X от множества X называется d(X) = max d(z,X). Этот параметр множества также известен в теории кодирования как радиус покрытия. Множество X называется покрывающим кодом радиуса d, если d(X) = d. Рассмотрим множество Y = {у Е Fn : d(y,X) = d(X)} векторов, находящихся на максимальном расстоянии от X. Это множество называется метрическим дополнением [1] множества X и обозначается X. Если X = X, то множество X называется метрически регулярным. Задача исследования максимальных и минимальных (по мощности) метрически регулярных множеств возникает на пути изучения бент-функций, множество которых является метрически регулярным [2]. Бент-функции часто используются в криптографии из-за высокой нелинейности, обеспечивающей повышенную устойчивость шифров к криптографическим атакам, однако многие связанные с ними задачи остаются открытыми. Например, неизвестно точное количество бент-функций в общем случае, а существующие верхняя и нижняя оценки значительно разнятся по порядку. В работе задача поиска максимального метрически регулярного множества сведена к задаче поиска минимального покрывающего кода радиуса 1, а также получены нижние оценки мощности метрически регулярных множеств с фиксированным расстоянием. Теорема 1. Пусть A,B - пара метрически регулярных множеств, являющихся метрическими дополнениями друг друга. Тогда существует пара метрически регулярных множеств A1,B1, таких, что A содержится в A1, B содержится в B1, а A1 и B1 являются метрическими дополнениями друг друга и расстояние между ними равно единице. Следствие 1. Максимальное по мощности нетривиальное метрически регулярное множество удалено от своего метрического дополнения на расстояние 1 и совпадает с дополнением минимального по мощности покрывающего кода радиуса 1. Таким образом, задача поиска максимального по мощности метрически регулярного множества эквивалентна задаче поиска наименьшего покрывающего кода радиуса 1. В общем случае это открытая проблема теории кодирования [3]. Однако большинство представляющих интерес для исследования множеств имеет максимальное расстояние, большее единицы, поэтому для последующих результатов зафиксируем расстояние между множествами. Утверждение 1. Пусть A, B - пара метрически регулярных множеств в булевом кубе, являющихся метрическими дополнениями друг друга и отстоящих друг от друга на расстояние d; M, N - мощности этих множеств соответственно. Тогда 2n+1(n - 2) M + N ^ v ; n(n - 1)d-1 + n - 4' где n - размерность булева куба. Выдвинута гипотеза о том, что всякий минимальный по мощности покрывающий код радиуса d является метрически регулярным множеством. При помощи компьютерных вычислений гипотеза проверена для минимальных покрывающих кодов с параметрами d = 2, n ^ 8 и d = 3, n ^ 10, конструкции которых можно найти в [4, 5].

Скачать электронную версию публикации