On a nonlinearity degree definition for a discrete function on a cyclic group.pdf В работе [1] предложен аддитивный подход к определению степени нелинейности функции на основе свойств конечных производных. Его суть заключается в следующем. Для функций F : G ^ H, у которых на множествах G и H заданы структуры абелевых групп, производная по направлению AaF, a Е G, функции F определяется равенствами AaF (x) = F (x + a) — F (x), где x Е G. Степенью нелинейности функции F : G ^ H (обозначается dl F) называется минимальное натуральное число m, такое, что Aai ... A„m+i F (x) = 0 при всех a1,..., am+1, x Е G. Если такого числа m не существует, то полагаем dl F = то. В случае элементарных абелевых p-групп степень нелинейности функции pn-знач-ной логики полностью определяется свойствами операции сложения. Поэтому при любом способе задания на этой группе операции умножения так, чтобы в результате получилось поле из pn элементов, степень нелинейности функций инвариантна по отношению к выбору операции умножения. В случае произвольных абелевых групп вопрос о свойствах параметра dl F остается открытым. В данной работе изучается случай циклических групп. Показано, что параметр dl F в случае, когда на множестве аргументов и значений заданы структуры циклических групп, может принимать конечные значения, только когда порядки групп являются примарными числами. Теорема 1. Если F : Gm ^ H, где G и H — циклические группы порядков g ^ 2 и h ^ 2 соответственно, причем dl F < то, то при некотором простом p ^ 2 выполнены равенства g = pn и h = pk при некоторых n ^ 1 и k ^ 1. Следующая теорема показывает, что введенное выше «аддитивное» определение степени нелинейности корректно и параметр dl F принимает конечное значение для любой функции, заданной на циклических группах примарного порядка. Теорема 2. Если F : Gm ^ HG = Zpn, H = Zpk, p > 2, n ^ 1, k ^ 1, m ^ 1, t ^ 1, и F = (F1,... , Ft), где Fi : Gm ^ H, 1 ^ i ^ t, — соответствующие координатные функции, то dl F = max{dl Fi : 1 ^ i ^ t} ^ m(pn — (k — 1)(p — 1)pn-1 — 1). Преимущество данного подхода к определению степени нелинейности заключается в том, что он полостью определяется свойствами только операции сложения. Вместе с тем в случае циклических групп, в отличие от элементарных абелевых групп, вопрос о способе выбора операции умножения представляется не таким однозначным. Если естественным образом рассматривать циклические группы примарного порядка как аддитивные группы колец вычетов с имеющимися в них операциями умножения, то определение степени нелинейности через степень многочлена является неудобным, так как не всякая функция F может быть задана многочленом (или набором многочленов координатных функций). Полиномиальные функции над кольцом вычетов, то есть функции, которые могут быть заданы многочленом над этим кольцом, составляют относительно малую долю функций [2, 3]. Следует отметить, что для полиномиальных функций над кольцом Zpn степень нелинейности функции совпадает с минимальной степенью многочлена, задающего эту функцию. Теорема 3. Если F : Gm ^ G — полиномиальная функция над кольцом G = Zpn, р > 2, n ^ 1, m ^ 1, и P (x1,... xn) G Zpn [x1,... xn] —многочлен минимальной степени, задающий эту функцию, то степень нелинейности совпадает со степенью многочлена P(x1,.. .xn): dl F = deg P. Из определения степени нелинейности с очевидностью вытекает Теорема 4. Если G и H — циклические р-группы примарного порядка и R — подгруппа в G, то для степеней нелинейности функции F : G ^ H и её ограничения на подгруппу R, F|r : R ^ H, выполнено неравенство dl (F|R) ^ dl F. Подробное изложение представленных результатов можно найти в [4].

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