Аддитивный подход к определению степени нелинейности дискретной функции на циклической группе примарного порядка | ПДМ. 2013. № 2(20).

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

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

An additive approach to nonlinearity degree of discrete functions on a primary cyclic group.pdf Введение В работе [1] предложен аддитивный подход к определению степени нелинейности функции на основе свойств конечных производных. Его суть заключается в следующем. Для функций F : G ^ H, у которых на множествах G и H заданы структуры абелевых групп, производная по направлению AaF, а Е G, функции F определяется равенствами AaF (x) = F (x + а) — F (x), где x Е G. Степенью нелинейности функции F : G ^ H (обозначается dl F) называется минимальное натуральное число m, такое, что A„1... A„m+1 F (x) = 0 при всех а1,..., ат+1, x Е G. Если такого числа m не существует, то полагаем dl F = то. В [1] показано, что в случае элементарных абелевых р-групп степень нелинейности функции р"-значной логики полностью определяется свойствами операции сложения. Поэтому при любом способе задания на этой группе операции умножения так, чтобы в результате получилось поле из pn элементов, степень нелинейности функций инвариантна по отношению к выбору операции умножения. В случае произвольных абелевых групп вопрос о свойствах параметра dl F остается открытым. В данной работе изучается случай циклических групп. Показано, что параметр dl может принимать конечное значение только в случае, когда циклические группы являются р-группами при некотором р ^ 2 (теорема 1). Для случая примарных циклических групп найдены верхние оценки степени нелинейности (теоремы 2 и 3) и показано, что для полиномиальных функций над кольцом Zpn степень нелинейности функции совпадает с минимальной степенью многочлена, задающего эту функцию (теорема 6). 1. Вспомогательные утверждения В дальнейшем потребуются следующие свойства биномиальных коэффициентов. Лемма 1. Пусть vp{k} —максимальная степень числа р, делящая число k. Тогда при 1 ^ k ^ pn справедливо равенство Vp { ) } = n — ^Р{к}. fpn Доказательство. Рассмотрим числитель и знаменатель выражения для ( n Поэтому Vp ^ ^ = Vp ^ — ^ = Vp{n} — Vp{k} = n — Vp{k}. pn\ _ pn(pn — 1) ■ ... ■ (pn — k + 1) " 1-2-...-k ' Нетрудно видеть, что при 1 ^ i ^ k — 1 выполнено равенство vp{pn — i} = vp{i}. pn\ 1 f р" J = "p т В частности, минимальное значение при 1 ^ k ^ р" — 1 достигается для k = ipn 1, 1 ^ i ^ р — 1, и равно Ч >=Ч Cpn 01=L Лемма 2. При всех 2 ^ k ^ n и 1 ^ i ^ р — 1 справедливо равенство - (Я (mod р'>■ Доказательство. Имеем р' \ _ р'(р' — 1) ■ ... ■ (р' — ра) ■ ... ■ (р' — ip^1 + 1) _ 4ipfc ^ 1 ■ 2 ■ ... ■ ра ■ ... ■ (ip' 1 — 1)ip' 1 _ р(р' — 1)(р' — 2) ■ ... ■ (р'_1 — а) ■ ... ■ (р' — ip^1 + 1) = 1 ■ 2 ■ ... ■ а ■ ... ■ (ipfc_ — 1)i (mod р'). Заметим, что в знаменателе все сомножители, не кратные р, являются обратимыми элементами кольца Zpn. Каждому сомножителю вида ра соответствует в числителе сомножитель вида р' — ра, 1 ^ а < ip^1 — 1. Всего сомножителей, кратных р, ров- • 2 но ip' 2. Представим теперь последнюю дробь в виде произведения двух сомножителей, в первый из которых включим все сомножители числителя и знаменателя, взаимно простые с р, а во второй — все кратные р, разделив каждый из них на р: (р' — 1)(р' — 2) ■ ... ■ (р' — ip' _1 + 1) р' _ 1(р' _1 — 1) ■ ... ■ (р' _1 — ip' _2 + 1) 1 ■ 2 ■ ... ■ (ip' _1 — 1) 1 ■ 2 ■ ... ■ (ip' _2 — 1)ip'_2 . Осталось заметить, что для каждого j, лежащего в интервале 1 ^ j ^ ip' _1 — 1 и взаимно простого с р, выполняется сравнение j = — = —1 (mod р'). jj Таким образом, pk ) _ ("1)(—2> ■ ■ ■ ■ ■ Н^1 + Ц (P'"1 ) = i-iPk—■ (P'"' ) (modpk). ipk 1J 1 ■ 2 ■ ... ■ (ipk 1 — 1) \ipk 2 J \ipk 2 При p > 2 или при p = 2 и k > 2 число ipk-1 — ipk-2 = ipk-2(p — 1) является чётным. При p = k = 2 имеем Г J = \ ) (mod 22). ■ 21 Следствие 1. При всех 2 ^ k ^ n и 1 ^ i ^ p — 1 справедливы сравнения ipt) = (j

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

дискретные функции, степень нелинейности, discrete functions, nonlinearity degree

Авторы

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

Ссылки

Черемушкин А. В. Аддитивный подход к определению степени нелинейности дискретной функции // Прикладная дискретная математика. 2010. №2(8). С. 22-33.
Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. Учебник в 2-х т. Т.Н. М.: Гелиос АРВ, 2003.
Keller G. and Olson F. Counting polynomial functions (mod pn) // Duke Math. J. 1968. V. 35. P. 835-838.
Chen Z. On polynomial functions from Zni x Zn2 x.. Znr to Zm // Discrete Math. 1996. V.162. P. 67-76.
Davio M., Deschamps J. P., and ThayseA. Discrete and switching functions. Budapest: Academiai Kiado, 1974.
 Аддитивный подход к определению степени нелинейности дискретной функции на циклической группе примарного порядка | ПДМ. 2013. № 2(20).

Аддитивный подход к определению степени нелинейности дискретной функции на циклической группе примарного порядка | ПДМ. 2013. № 2(20).

Полнотекстовая версия