Классы полиномиальных и вариационно-координатно полиномиальных функций над кольцом Галуа

причём в одной ветви может встретиться только один симметричный многочлен одной степени.

В результате исследования поликвадратичного расширения полей посредством операции А получены следующие свойства этого расширения.

1. Посредством поликвадратичного расширения можно вычислять характеристический многочлен элемента не только из расширенного поля, но и из расширяемого, т. е. движение по дереву возможно как вверх, так и вниз. Для того чтобы «опуститься» по дереву вниз, необходимо применить операцию А, а чтобы «подняться» по дереву вверх — выполнить обратную операцию Л = А-1.

2. Для вычисления расширений необходимо вычислить относительный след корня и записать уравнение, задающееся неприводимым многочленом, коэффициенты которого вычисляются в явном виде [3, 4].

Теорема 1. Если Л,(ж) = г, deg f = п, f (г) = 0, degд = 2п, д(г) = 0, то Тг(г) = = Тг(х), где к(х) = х + х-1 равен относительному следу элемента х.

Теорема 2. Если в поле ОЕ(2т), т > 1, г — корень симметричного многочлена f, то однозначно определён периодический многочлен д, где у = 1/(г + 1) —его корень. И наоборот, если д — периодический, то f — симметричный, где г = 1/у +1.

Таким образом, с помощью операции А построено полное бинарное дерево неприводимых многочленов степени 2П. Изученные в работе свойства такого поликвадратич-ного расширения значительно упрощают процедуру генерации многочленов и дают возможность избежать полного перебора при поиске многочленов больших степеней, что имеет особое значение для криптографии и теории кодирования.

ЛИТЕРАТУРА

1. Информационные технологии и безопасность алгоритмы разделения секрета. Предварительный государственный стандарт республики Беларусь СТБ П 34.101.44. Минск: Госстандарт, 2011.

2. Глуско Кр. Л., Титов С. С. Арифметический алгоритм решения квадратных уравнений в конечных полях характеристики два // Доклады ТУСУРа. 2012. №1(25). Ч.2. С.148-152.

3. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы. М.: КомКнига, 2006.

4. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006.

5. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

6. Геут Кр. Л., Титов С. С. О свойствах поликвадратичных расширений бинарных полей // Проблемы теоретической и прикладной математики: Труды 44-й Всерос. молодежной конф. Екатеринбург: УрО РАН, 2013. С. 17-19.

УДК 512.55

КЛАССЫ ПОЛИНОМИАЛЬНЫХ И ВАРИАЦИОННО-КООРДИНАТНО ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ НАД КОЛЬЦОМ ГАЛУА

М. В. Заец

Рассматривается новый класс функций над кольцом Галуа Я = ОК(дт,рт), получивший название класса функций с вариационно-координатной полиномиальностью (ВКП-функций). Рассматривается соотношение между данным классом и

классом полиномиальных функций над R, даётся верхняя оценка его мощности, а также достаточные условия отсутствия полиномиального представления ВКП-функции.

Ключевые слова: полиномиальные функции, кольцо Галуа, координатное множество, ВКП-функции.

Кольцом Галуа называется конечное коммутативное локальное кольцо R = = GR(qm,pm), нильрадикал J(R) которого имеет вид pR, где p = char R и R = = R/J(R) = GF(q) —поле вычетов данного кольца [1]. При этом char R = pm, |R| = qm и m = ind J(R), m E N, — индекс нильпотентности нильрадикала J(R). Подмножество B = {b0 = 0,... , bq-1} С R называется координатным множеством кольца R, если его элементы образуют полную систему вычетов по нильрадикалу J(R). В таком случае любой элемент a E R однозначно представляется в виде

a = a(0) + p  a(1) +    + pm-1  a(m-1), a(i) E B, i = 0,..., m — 1,

называемом разложением элемента a в координатном множестве B. Функции YB: R ^ B, определяемые по правилу yb(a) = a(i), i = 0,...,m — 1, называются координатными функциями в координатном множестве B, а элементы a(i) = yP(a) — координатами элемента a в координатном множестве B.

Обозначим через Pr(n) класс всех полиномиальных функций от n переменных над кольцом Галуа R = GR(qm,pm). Следующее определение и результаты обобщают полученные ранее в [2] для случая примарного кольца вычетов Z2m.

Определение 1. Функцию f (x): Rn ^ R, R = GR(qm,pm), m > 1, назовём ВКП-функцией в координатном множестве B, если для любого i E {0,... , m — 1} существует полиномиальная функция p*(x) E PR(n), такая, что yT(f (a)) = yb(p*(a)) при всех a E Rn. При этом многочлен p*(x), i = 0,... , m — 1, будем называть i-м координатным многочленом функции f (x).

Класс всех ВКП-функций от n переменных над кольцом R в координатном множестве B обозначим через CP#(n). Следующая теорема устанавливает соотношение между введённым классом и классом полиномиальных функций над тем же кольцом. Теорема 1. Справедливы утверждения:

1) если R = GR(q2,p2), то PR(n) = CPR(n);

2) если R = GR(qm,pm), m ^ 3, то PH(n) С CPR(n).

/ df df \ df

Пусть f (x) E R[x]. Обозначим grad f (x) = ( ——(x),..., —— (x) I, где —— (x) — форУ dx 1 dx^ / dx^

мальная частная производная многочлена f (x) по переменной x*, i = 1,..., n. Приведём достаточное условие того, что при m ^ 3 ВКП-функция не имеет полиномиального представления над R.

Теорема 2. Пусть f (x) E CPR(n), m ^ 3 и для координатных многочленов p*(x), pj(x), i,j E {1,... , m — 1}, i = j, существует a E Bn, такое, что

gradp*(a) ф gradpj(a) (mod J(R)).

Тогда f (x) E PR(n).

Теорема 3. Справедлива следующая оценка мощности класса CPR(n) :

|CPB (n)| ^ qqn+(m-1)n^qn+qn^(qn(m-1)-1)/(qn-1),

при этом если m =2, то в неравенстве достигается равенство.

Класс ВКП-функций во многом обобщает класс полиномиальных функций. В частности, можно показать, что системы уравнений, левые части которых являются такими функциями, могут быть решены методом покоординатной линеаризации, предложенным в работе [3] для полиномиальных функций над кольцом Галуа — Эйзенштейна.

ЛИТЕРАТУРА

1. Елизаров В. П. Конечные кольца. М.: Гелиос-АРВ, 2006.

2. Заец М. В., Никонов В. Г., Шишков А. Б. Функции с вариационно-координатной полиномиальностью и их свойства // Открытое образование. 2012. №3. С. 57-61.

3. Михайлов Д. А., Нечаев А. А. Решение системы полиномиальных уравнений над кольцом Галуа — Эйзенштейна с помощью канонической системы образующих полиномиального идеала // Дискретная математика. 2004. №1. Вып. 1. С. 21-51.

УДК 519.7

ОБ АФФИННОСТИ БУЛЕВЫХ ФУНКЦИЙ НА ПОДПРОСТРАНСТВАХ И ИХ СДВИГАХ1

Н. А. Коломеец

Пусть / — булева функция от п переменных и для любого аффинного подпространства Ь размерности [п/2] функция / аффинна на Ь тогда и только тогда, когда / аффинна на любом сдвиге Ь. Доказано, что тогда либо степень / не превышает 2, либо не существует ни одного аффинного подпространства размерности [п/2], на котором / аффинна.

Ключевые слова: булевы функции, бент-функции, квадратичные функции.

Рассматривается свойство булевых функций, связанное с их аффинностью на аффинных подпространствах.

Введём необходимые определения. Отображение f : ^ Ш2 называется булевой

функцией от п переменных. Алгебраической степенью или просто степенью булевой функции называется степень её алгебраической нормальной формы (полинома Же-галкина). Булева функция называется аффинной, если её алгебраическая степень не больше 1, и квадратичной, если её степень равна 2. Множество Ц С называется аффинным подпространством, если Ц = а ф Ь, где а € и Ь является линейным подпространством в Ш^. Будем называть Ц сдвигом подпространства Ь. Через /п^о обозначим характеристическую функцию множества О С Ш^. Через (и,г>) обозначим скалярное произведение векторов и и V. Булева функция f от п переменных аффинна на множестве О С Ш^, если существуют а € ЩП, с € Ш2, такие, что для любого х € О верно f (х) = (а, х) ф с. Под расстоянием между двумя булевыми функциями подразумевается расстояние Хэмминга между их векторами значений.

Все квадратичные булевы функции обладают следующим свойством.

Утверждение 1. Пусть f — квадратичная булева функция от п переменных. Тогда для любого аффинного подпространства Ь функция f аффинна на Ь, если и только если f аффинна на любом сдвиге Ь.

Доказательство утверждения следует из неравенства deg(f (х) ф f (х ф в)) ^ 1, верного для любого в € ЩП.

1 Исследование выполнено при поддержке РФФИ (проект №12-01-31097).