Вычисление степени нелинейности функции на циклической группе примарного порядка | ПДМ. 2014. № 2(24).

Вычисление степени нелинейности функции на циклической группе примарного порядка

Предлагается способ вычисления степени нелинейности дискретных функций, заданных на циклической группе примарного порядка, основанный на свойствах разложения Ньютона. Найдены значения степени нелинейности для базисных функций этого разложения. Для циклических групп порядков p и p приводится распределение числа функций с заданным значением степени нелинейности.

Computation of nonlinearity degree for discrete functions on primary cyclic groups.pdf Настоящая работа является продолжением [1]. Напомним определения. Рассмотрим функции F : Gm ^ H, где G и H - циклические группы. Для удобства будем считать, что циклические группы - это аддитивные группы колец вычетов. Всюду ниже запись N mod M обозначает остаток от деления натурального числа N на натуральное число M, а запись (N, M) -их наибольший общий делитель. Производная по направлению A^, a G Gm, функции F определяется равенствами A^ (x) = F (x + a) - F (x), где x G Gm. Степенью нелинейности функции F (обозначается dl F) называется минимальное натуральное число t, такое, что A0i ... Aat+i F (x) = 0 при всех a(,..., at+(, x G Gm. Если такого числа t не существует, то полагаем dl F = то. Если функция F тождественно равна нулю, то для удобства полагаем dl F = - 1. В работе [1] показано, что степень нелинейности у всех функций из этого множества конечна в том и только в том случае, когда |G| = pn, |H| = pk при некотором простом p и натуральных n ^ 1 и k ^ 15, а также dl F ^ m(pn + (k - 1)(p - 1)pn-i - 1) и верхняя граница степени нелинейности достигается для функций, в табличном задании которых имеется одно ненулевое значение равное 1. Пусть Dt - множество функций со степенью нелинейности равной t: Dt = {F : dlF = t}, 1 ^ t ^ tmax. Из работы [1] следует, что Dt С Ker A(+1, в частности Dt = Ker A-+1 \ Ker A(, Ker A' С Ker A( С Ker A( С ■ ■ ■ С Ker A(max С Ker A(max+'. (1) Если F - такая функция, что д1тах f = 0, то функции Д1тах *F = 0 имеют степень нелинейности t. Поэтому классы Dt при всех числах t из интервала 1 ^ t ^ tmax не являются пустыми, и в цепочке (1) все включения являются строгими. В данной работе рассматриваются подходы к описанию классов Dt на основе разложения Ньютона. Пусть n = k ^ 2 и m ^ 1. Как известно, всякую функцию F : Z^, ^ Zpn можно представить в виде п1 F (xb...,xm) = Y, h(ii,...,im) il,...,im=0 xm im mod pn где 0 ^ h(i1,..., im) ^ pn - 1, 0 ^ i1,..., im ^ pn - 1, и x(x - 1)... (x - i + 1) i! при 0 < i ^ pn - 1 и(„ 1=1. Подсчитаем степени нелинейности для базисных функций, входящих в это разложение. Пусть Fj(x) = (Х ) mod pn, x G Zpn, 0 ^ i ^ pn - 1. Для дальнейшего потребуются следующие простые свойства. Свойство 1. Если dl F > dl F', то dl (F ± F') = dl F. Свойство 2. Пусть m ^ 1 и F : Gm ^ H, где G и H - циклические группы порядков pn и соответственно, n ^ 2 и k ^ 2. Если k > s ^ 1 и функция F имеет максимальную степень нелинейности dlF = m(pn + (k - 1)(p - 1)pn-1 - 1), то степень нелинейности функции F' : Gm ^ H вида F'(x) = psF(x) mod не превосходит (3) величины dl F' ^ m(pn + (k - s - 1)(p - 1)pn-1 - 1) Действительно, в силу изоморфизма колец psZ pk - Zpk - s функцию F' можно рассматривать как функцию F' : Gm ^ H', где H' - циклическая группа порядка pk-s. Поэтому степень нелинейности функции F' не превосходит максимальной степени нелинейности для функций такого вида, которая в точности равна указанной величине. (Далее будет показано, что при k = n в (3) выполняется равенство.) Свойство 3. Функция Fpn-1(x) = ( ) mod pn при x G Zpn принимает значеvPn - 1 ние 1 только при x = pn - 1, а в остальных точках равна нулю. Поэтому она имеет максимальную степень нелинейности pn + (n - 1)(p - 1)pn-1 - 1. Это утверждение является прямым следствием способа доказательства теоремы 2 из [1]. Еще одним следствием этой теоремы является Свойство 4. Пусть m ^ 1 и G и H - циклические группы порядков pn и соответственно, 1 ^ s < k ^ n. Тогда функция F : Gm ^ H вида x1 xm mod F (xb...,xm) = vPn - V \pn - 1 имеет степень нелинейности m(pn + (k - s - 1)(p - 1)pn-1 - 1). Действительно, при x 1 = • • • = xm = pn - 1 функция F принимает значение ps, а в остальных точках равна нулю. Если теперь функцию F рассматривать как функцию F' : Gm ^ H', где H' - циклическая группа порядка pk-s, то она будет иметь единственное ненулевое значение равное 1. Поэтому она имеет максимальную степень нелинейности. Лемма 1. Пусть M ^ 2 - натуральное число и Fj(x) = Q mod M, x G ZM, 0 ^ i ^ M - 1. Тогда при 1 ^ i ^ M - 1 и x G ZM выполняется тождество A iFi = Fi-i - Fi(M)Fm- i (mod M). (4) Доказательство. В силу целочисленного тождества Ai(x) = G - 0 • *>' >1 при 0 ^ x < M - 1 имеем A1Fi(x) = Fi((x + 1) mod M) - Fi(x) = Fi(x + 1) - Fi(x) = Fi-1(x) (mod M). Для x = M - 1 получаем AiFi(M - 1) = Fi(0) - Fi(x) = Fi(M) - Fi(M - 1) + Fi(0) - Fi(M) = = Fi-1(M - 1) - Fi(M) (mod M). Так как функция Fm-1 (x) принимает значение 1 только при x = M - 1, а в остальных точках равна нулю, то эти равенства можно переписать в виде (4). ■ Лемма 2. Пусть n ^ 2, p простое и 1 ^ i ^ pn - 1. Тогда значения производных фуНкц^,и ВД = (x) mod pn Пр„ 1 < x « pn - 1 удовлетворяют равенствам yx\ И J (mod P^ если (Pn,i) = 1, [(i - J - (pn) (pn (mod pn), если (pn,i) = 1. fpn\ Доказательство вытекает из того факта, что ( . j mod pn = 0 только при (pn,i) = 1 (см., например, [1, лемма 1]). Теорема 1. Пусть n ^ 1 и p простое. Тогда степень нелинейности функции Fi(x) = f xj mod pn, 1 ^ i ^ pn - 1, равна i + (t - 1)(p - 1)pn 1 + pn - p*, если p* ^ i ^ pt+1 - 1, 1 ^ t ^ n - 1, „n- 1 I „n ■ / -I- I I. - I II II - II/ dl Fi . i, если 1 ^ i ^ p - 1. Доказательство. Определим рекурсивно семейство деревьев Dp(n,k), k = = 1, 2,... При k =1 дерево Dp(n, 1) представляет собой цепь с вершинами, помеченными последовательно числами 0,1,... ,pn - 1, и корнем в вершине c пометкой pn - 1. Если деревья при k = 1, 2,..., t - 1 уже построены, то дерево Dp(n, t) получается из дерева Dp(n, 1) путём присоединения к каждой вершине с пометкой вида psa, (a,p) = 1, при 1 ^ s ^ t - 1 ребра, соединяющего эту вершину с корнем дерева Dp(n, s) (см. рис. 1). D2(3, 3) Ds(2, 2) 7 8 Рис. 1. Деревья D2(3, 3) и Дз(2, 2) В терминах свойств этого дерева удобно интерпретировать значения степеней нелинейности. Поставим в соответствие i-й вершине исходного дерева Dp(n, 1) биномиальный коэффициент ^ . Тогда переходу от вершины i к i - 1 в дереве Dp(n, k) соответствует взятие производной Д^ причём точкам присоединения деревьев соответствует появление дополнительных слагаемых, возникающих в соответствии c формулой Д'(Х) - С: - 1) - (*)(/- 1) (mod Л x , k Нетрудно видеть, что степень нелинейности функции mod p при x Е Zn равна W высоте поддерева с корнем в вершине i, т. е. длине максимального пути от i-й вершины до листьев дерева Dp(n, k). Рассмотрим теперь дерево Dp(n,n) и вычислим значения dl Fi, 1 ^ i ^ pn - 1. Воспользуемся индукцией по t. При t = 0 все значения i из интервала 0 ^ i ^ p - 1 взаимно просты с p, (i,p) = 1. По лемме 2 получаем dl Fi-i = dl F - 1. Так как при i = 1 имеем dl F1 = 1, то для значений i в этом интервале выполнено равенство dl F = i. Предположим, что для значений t, меньших s, равенство выполняется. Докажем его для t = s. В силу лемм 5 и 6 из [1] достаточно рассмотреть случай, когда используется только производная А1, так как остальные производные могут быть выражены через неё. При i = ps имеем n x x ps -1 x pn -1 А^ (x) = Ач s (mod pn). s В силу леммы 1 из [1] и того факта, что умножение на обратимый элемент не изменяет значения степени нелинейности функции, получаем x n x dl dl Р" pn - 1 s pn - 1 Это значение совпадает с высотой дерева Dp(n, s) ив силу свойства 4 равно = pn + (s - 1)(p - 1)pn-1 - 1 x dl Р pn - 1 По предположению индукции ps - 1 + (s - 2)(p - 1)pn-1 + pn - p x s-1 dl ps - 1 Значит, по свойству 1 имеем dl Fps = pn + (s - 1)(p - 1)pn-1. Рассмотрим теперь случай ps < i ^ ps+1 - 1. В этом интервале встречаются только числа вида i = pra, (p, а) = 1, при r ^ s. В графе Dp(n,n) точке i = prа при r ^ 1 соответствует присоединение к дереву Dp(n, 1) дерева Dp(n, r). Так как все такие вершины находятся выше вершины с пометкой ps, а высота дерева Dp(n, r) не превосходит высоты дерева Dp(n, s), то присоединение этих деревьев не изменит длину максимального пути от i-й вершины до листьев дерева Dp(n,n), который будет проходить через вершину с пометкой ps. Значит, dl Fi = dl Fps + i - ps = pn + (s - 1)(p - 1)pn-1 + i - ps. ■ Следствие 1. Пусть n ^ 1, p простое. Тогда для степеней нелинейности функций Fj(x) = ( . j mod pn, 1 ^ i ^ pn - 1, выполняются равенства Следствие 2. Пусть n ^ 1, p ^ 2 и разложение функции F : Zp n -у Zpn имеет вид pn-1 /x\ F(x) = E аЛ ) mod pn. i=0 i Тогда следующие условия эквивалентны: 1) функция F имеет максимальную степень нелинейности; 2) коэффициент apn-1 обратим в кольце Zpn, т.е. (apn-1,p) - 1; 3) сумма значений функции F является обратимым элементом в кольце Zpn: /pn-1 \ ( Е F (x) mod pn, pi =1. V ж=0 J Доказательство. Эквивалентность первого и второго условий вытекает из теоремы 1 и свойства 1. Для доказательства эквивалентности второго и третьего условий воспользуемся следующим свойством суммы биномиальных коэффициентов: x + 1 У + 17' справедливым при всех x ^ y ^ 0. Его доказательство легко проводится индукцией по x: 'i\ X-6/ A /x\ ( x \ (x\ fx + 1N чУ +1 pn-1 / x м x ж=0 \ 1 t= V У С помощью этого равенства получаем pn \_ (0 (mod pn), 0 ^ i ^ pn - 2, i + 1/ l 1 (mod pn), i = pn - 1, pn-1 откуда F(x) = apn-1 (mod pn). ■ ж=0 Следствие 3. Пусть m ^ 2, n ^ 1, p ^ 2 и разложение функции F : Z^n ^ Zpn имеет вид (2). Тогда следующие условия эквивалентны: 1) функция F имеет максимальную степень нелинейности равную dl F = m(pn + (k - 1)(p - 1)pn-1 - 1); 2) коэффициент h(pn - 1,... ,pn - 1) обратим в кольце Zpn, т. е. (h(pn - 1,...,pn - 1),p) = 1; 3) сумма значений функции F является обратимым элементом в кольце Zpn : Y^ F (x1,..., xm) mod pn, pi =1. Доказательство проводится полностью аналогично. Следствие 4. Пусть m ^ 1 и F : Z^n ^ Zpn, где n ^ 2. Если n > s ^ 1 и функция F имеет максимальную степень нелинейности m(pn + (n - 1)(p - 1)pn-1 - 1), то степень нелинейности функции F' : Gm ^ H вида F'(x) = psF(x) mod pn равна dl F' = m(pn + (n - s - 1)(p - 1)pn-1 - 1). Доказательство. Рассмотрим разложение Ньютона функции F вида (2). В силу следствия 3 и свойства 1 можно считать, что функция F имеет в своём задании единственное ненулевое значение, причём оно должно быть взаимно просто с p. Пусть, например, F(0) = 1 (в противном случае можно перейти к функции F'' = = F(0)-1F mod pn). Значит, у функции F'(x) также одно ненулевое значение F(0) = ps. При гомоморфизме Zpn ^ Zpn-s элементу ps соответствует элемент 1 Е Zpn-s. Поэтому для степени нелинейности функции F'(x) в неравенстве (3) на самом деле должно стоять равенство. ■ г5\ У + У + 1 + У УУ t=o V У) \У Следствие 5. При n ^ 1, p ^ 2 число функций максимальной степени нелинейности среди функций вида F : Zp n - Zpn равно I Amax | = ^(pn)pn(pn-1) = (p - 1)pnpn-1 = (1 - p) pnpn Следствие 6. При m ^ 1, n ^ 1, p ^ 2 число функций максимальной степени нелинейности среди функций вида F : Z^n. - Z pn равно iDtmax I = ^(pn)pn(pmn -1) = (p - 1)pnpmn -1 = (1 - p) pnpmn . Следствие 7. Пусть n ^ 2, p ^ 2. Тогда число функций степени нелинейности i при 0 ^ i ^ p - 1 среди функций вида F : Z pn - Zpn равно IА| = (pn - 1)pni. Следствие 8. Пусть n ^ 2, p ^ 2. Тогда число функций степени нелинейности tmax - i при 1 ^ i ^ p - 1 среди функций вида F : Zpn - Z pn равно iDtmax - i| = (p - 1)pnpn-i-1 . Доказательство. В силу следствия 3 при i =1 pn + (n - 2)(p - 1)pn-1 - 1 x ^ pn - 1 dl x ^ pn + (n - 2)(p- 1)pn-1 - 1

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

дискретные функции, степень нелинейности, разложение Ньютона, discrete functions, nonlinearity degree, Newton expansion

Авторы

ФИООрганизацияДополнительноE-mail
Черемушкин Александр ВасильевичИнститут криптографии, связи и информатики, г. Москва, Россия; Академия криптографии РФдоктор физико-математических наук, член-корреспондент; заведующий кафедройavc238@mail.ru
Всего: 1

Ссылки

Черемушкин А. В. Аддитивный подход к определению степени нелинейности дискретной функции на циклической группе примарного порядка // Прикладная дискретная математика. 2013. №2(20). С. 26-38.
Granville A. Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers // Organic Math. (Burnaby, BC, 1995), CMS Conf. Proc., 20, Amer. Math. Soc., Providence, RI, 1997. P. 253-276.
 Вычисление степени нелинейности функции на циклической группе примарного порядка | ПДМ. 2014. № 2(24).

Вычисление степени нелинейности функции на циклической группе примарного порядка | ПДМ. 2014. № 2(24).