Number of discrete functions on a primary cyclic group with a given nonlinearity degree.pdf Напомним определения из работы [1]. Будем рассматривать функции F : Gm ^ H, где G и H - циклические группы. Считаем, что циклические группы - это аддитивные группы колец вычетов. Степенью нелинейности функции F (обозначается dl F) называется минимальное натуральное число t, такое, что Да1 ... Aat+1 F(x) = 0 при всех ai,... , at+1, x Е Gm, где Д^(x) = F(x + a) - F(x), a, x E Gm. Пусть Dt - множество функций со степенью нелинейности t. Предлагается подход к описанию классов Dt на основе разложения Ньютона. Теорема 1 даёт точные значения степени нелинейности для базисных функций этого разложения. Лемма 1. Пусть n ^ 2, p простое и 1 ^ i ^ pn - 1. Тогда значения производных фуНКц^,и ВД = (x) mod pn Пр„ 1 < x « pn - 1 удовлетворяют равенствам yx\ И J (m0d p^ если (pn,i) = 1, " 1У{ - 1) - yp-)ypn- 1) (mod pn), если (pn,i) = 1. Теорема 1. Пусть n ^ 1 и p простое. Тогда степень нелинейности функции Fj(x) = mod pn, 1 ^ i ^ pn - 1, равна ,i + (t - 1)(p - 1)pn-i + pn - p*, если p* ^ i ^ pt+1 - 1, 1 ^ t ^ n - 1, dl Fi = < если 1 ^ i ^ p - 1. Следствие 1. В условиях теоремы 1 выполняются равенства (p - 1)pn-i + p* - pt+1, если i = p*, 1 ^ t ^ n - 1, dl Fi - dl Fi-1 = . 1, если i = p, 1 ^ t ^ n - 1. Следствие 2. Пусть m ^ 2, n ^ 1, p ^ 2 и разложение функции F : Z^i ^ Zp имеет вид F(xi,...,xm)= n-1 h(ii,... ,im)( x ) •••(x ) modpn il,...,im=0 V^/ \im/ Тогда следующие условия эквивалентны: 1) функция F имеет максимальную степень нелинейности, равную dlF = m(pn + (k - 1)(p - 1)pn-i - 1); 2) коэффициент h(pn - 1,... ,pn - 1) обратим в кольце Zpn, т. е. (h(pn - 1,...,pn - 1),p) = 1; 3) сумма значений функции F является обратимым элементом в кольце Zpn: Y^ F (xi,..., xm) mod pn, pi =1. X\,...,Xm / Данный подход позволяет подсчитать число функций малой и близкой к максимальной степени нелинейности, а также найти точное распределение числа функций w 2 3 с заданным значением степени нелинейности для циклических групп порядков p и p . Теорема 2. Пусть p ^ 2. Тогда число функций степени нелинейности i среди функций вида F : G ^ H, G = H = Zp2, равно 1 , если i = - 1 , |Di| =

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