Свойства статистики var на группе перестановок | ПДМ. Приложение. 2013. № 6.

Свойства статистики var на группе перестановок

Рассматриваются некоторые свойства статистики var, определяющей число различных символов слова, полученного поэлементным сложением по mod n перестановки степени n с фиксированной перестановкой — ключом.

Properties of statistics var on group of permutations.pdf Ряд статистик на симметрической группе Sn перестановок а, где а = а1... an — слово над алфавитом {1,..., n}, рассматривался в [1]. В криптографии применяется биекция vp : а М- т перестановки а E Sn на слово т = т1... тп E Tn, определяемая фиксированным ключом к = к1... кп E Sn. Она отображает а E Sn на слово т E Tn по правилу т = а ф к, где тг = аг + кг (mod n), i = 1,...,n, а тг — наименьший положительный вычет, и индуцирует статистику var^, к) = card{ri,... , тп} — число различных символов слова т = vp^). Так как для любого ключа к E Sn статистика var имеет производящий многочлен n Vn(t) = Е Vn,ktk = Е tvar(CT'к), k=1 aeSn то в качестве ключа удобно использовать перестановку v = v1... vn E Sn, где v = = n — i + 1, i = 1,..., n. Многочлен Vn(t) не изменяется и при замене перестановок а на обратные а-1 E Sn. По определению статистики var многочлен Vn(t) имеет коэффициенты Vn,k ^ 0, а их нахождение уже при сравнительно небольших n является трудной задачей. Вычисление даёт V1(t) = V2(t)/2 = t, Va(t)/3 = t+t3, V4(t)/4 = t+t2+4t3, V>(t)/5 = t+20t3+3t5. Теорема 1. Справедливы следующие свойства коэффициентов многочлена Vn(t): а) n|Vn,fc; б) при чётном n все Vn,k > 0, кроме Vn,n = 0; в) при нечётном составном n все Vn,k > 0, кроме Vn,n-1 = 0, а для простого n, кроме того, Vn,2 = 0. Доказательство теоремы 1 основано на применении перманента циркулянта circ(zb ... ,zn) = ( \ Z1 z2 zn z1 z n zn— 1 \ z2 z3 ... z1 у порожденного вектором (z1,... , zn). Каждый член per circ(z1,... , zn) имеет вид n zm1 ... , причём 0 ^ mi ^ n, а сумма imi кратна n. Число различных членов per circ(z1,..., zn) равно [2] i=1 ..,zn) преобразу-zmn на sign(mi) и 1vf2d - Л pfn ndiA d j где

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

перестановка, статистика, производящий многочлен, перманент, циркулянт, permutation, statistics, generating polynomial, permanent, circulant

Авторы

ФИООрганизацияДополнительноE-mail
Бондаренко Леонид НиколаевичПензенский государственный университетдоцент, кандидат технических наук, доцент кафедры дискретной математикиleobond5@mail.ru
Всего: 1

Ссылки

Фоата Д. Распределения типа Эйлера и Макмагона на группе перестановок // Проблемы комбинаторного анализа: сб. статей. М.: Мир, 1980. С. 120-141.
Brualdi R. A. and Newman M. An enumeration problem for a congruence equation // J. Research National Bureau Standards. Math. Sci. 1970. V. 74B. No. 1. P. 37-40.
Риордан Дж. Введение в комбинаторный анализ. М.: ИЛ, 1963.
 Свойства статистики var на группе перестановок | ПДМ. Приложение. 2013. № 6.

Свойства статистики var на группе перестановок | ПДМ. Приложение. 2013. № 6.