Расстояние единственности семейства координатных последовательностей, полученных усложнением линейных рекуррент над кольцом Галуа

Тип работы:
Реферат
Предмет:
Связь


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
2008 Теоретические основы прикладной дискретной математики № 2(2)
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
УДК 621. 391. 1:004. 7
РАССТОЯНИЕ ЕДИНСТВЕННОСТИ СЕМЕЙСТВА КООРДИНАТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ПОЛУЧЕННЫХ УСЛОЖНЕНИЕМ ЛИНЕЙНЫХ РЕКУРРЕНТ НАД КОЛЬЦОМ ГАЛУА1
Д.Н. Былков
Московский государственный институт радиотехники, электроники и автоматики
E-mail: Bilkov@gmail. com
В настоящей работе обсуждается наличие эквивалентных последовательностей при усложнении координатных ЛРП над кольцом Галуа, а также рассмотрен вопрос о минимальной длине, на которой выходные последовательности будут различимы.
Ключевые слова'-, координатные ЛРП, кольцо Галуа, эквивалентные состояния, расстояние единственности.
Пусть R = GR (qn, pn) — кольцо Галуа характеристики pn, состоящее из qn элементов [1], n & gt- 1, q = pr, e -единица. Для кольца Галуа R поле R = R/pR будем называть полем вычетов. Естественный эпиморфизм R R индуцирует эпиморфизм колец многочленов R[x] R [х]. Образ многочлена A (x) = X a, x е R[x] бу-
дем обозначать А (х): А (х) = X а, х е R[x].
Подмножество B = {b0, …, bq _ 1} называется координатным множеством кольца R, если его элементы образуют полную систему вычетов по модулю идеала pR. В [1] показано, что каждый элемент a е R однозначно представляется в виде a = a0 + pa1 + … + pn- 1an _ 1, as е B, 0 & lt- s & lt- n — 1, называемом разложением элемента a в координатном множестве B.
Пусть l, t е N и t удовлетворяет условиям 1 & lt- t & lt- l. Произвольную функцию h: Rl B от переменных x1, ., xl можно рассматривать как функцию от переменных хг7, 0 & lt- i & lt- n — 1, 1 & lt- j & lt- l, отображающую Bnl в B, где величины х0j, …, хп _ 1 j суть коэффициенты из разложения переменной хj в координатном множестве B. Скажем, что отображение h биективно по переменной хп _ 1 t, если при произвольной фиксации nl — 1 переменных
(х0 1, ¦¦¦, хп — 1 1, ¦¦¦, х0 h ¦ ¦ ^ хп — 2 Ь х0 t + 1, ¦ ¦ ^ хп — 1 t + 1, ¦ ¦ ^ х0 l, ¦ ¦ ^ хп — 1 l) е B
функция h = h (xo 1, ., хп — 2 t, х, хо t + 1, ., хп — 1 l) — биекция.
Всюду далее F (x) — унитарный многочлен над R, через LR (F) будем обозначать множество всех линейных рекуррентных последовательностей над R с характеристическим многочленом F (x). Каждой последовательности и из Lr (F) сопоставим последовательности u0, …, ип- 1, получающиеся из разложения знаков последовательности и в координатном множестве B: u (i) = u0(i) + pu1(i) +. + pn- 1ип — 1(i), us (i) е B, 0 & lt- s & lt- n — 1, i & gt- 0.
Зафиксируем параметры l е N, 1 & lt- t & lt- l, и s1, ., sl е N. Рассмотрим алгоритм A, сопоставляющий каждой из последовательностей u е Lr (F) выходную последовательность u = A (u) по правилу: u = h (u (i + s1), ., u (i + sl)), i & gt- 0, где отображение h биективно по переменной хп — 1 t.
Будем говорить, что алгоритм A не допускает эквивалентных состояний, если существует натуральное L со свойством
V u, v е Lr (F) (u Ф v) =ф ((u (0), ., u (L — 1)) Ф (v (0), ., v (L — 1))). (1)
В этом случае минимум Ud (F, A) значений L со свойством (1) назовем расстоянием единственности алгоритма A. В противном случае будем считать Ud (F, A) = да.
Определим норму элемента a е R и норму последовательности у е R& lt-1>- следующим образом:
||a|| = max{0 & lt- t & lt- n | a е p’R}, jLyjj = max{0 & lt- t & lt- n | у е _ptR& lt-1>-}.
1 Работа выполнена при финансовой поддержке Совета поддержки научных школ при Президенте Р Ф (номер проекта НШ -8564. 2006. 10).
6
Д.Н. Былков
Положим Lr (F)* = {u е Lr (F): ||u|| = 0}. Будем говорить, что многочлен F (x) е R[x] реверсивный, если
F (0) е R*. Назовем многочлен F (x) е R[x] многочленом Галуа, если его образ F (x) е R[x] неприводим над R. При условии T (F) = pn- 1(qm — 1), m = deg F (x), скажем, что F (x) — многочлен максимального периода (ММП) над R.
Теорема 1. Пусть существует натуральное L, такое, что для любой последовательности и е Lr (F) для каждого 0 & lt- k & lt- n — 1 найдется 0 & lt- i0 & lt- L — 1 со свойством
u (i0 + Sj) = 0, для всехj е {1, …, 1} {t},
||u (io + s)|| = k.
Тогда верно неравенство Ud (F, A) & lt- L.
Условия теоремы 1 выполняются, например, если I = 1 и F (x) — многочлен максимального периода. В [1] показано, что на цикле линейной рекурренты максимального периода появятся все элементы кольца R, то
есть справедливо неравенство L & lt- T (F). В случае кольца Z4 можно указать более точные оценки величины L.
Теорема 2. Пусть F (x) = xm — x — 1 е Z4[x], где m & gt- 2. Тогда для любой последовательности и е Lii (F)*, для всех z е {1, 3} существует i0 & lt- 4m — 2, такое, что u (i0) = z. Причем указанная оценка достижима.
Теорема 3. Пусть F (x) = xm — xk — 1 — многочлен Галуа над кольцом Z4, где 1 & lt- k & lt- m. Тогда для любой последовательности u е Lii (F)*, для всех z е {1, 3} существует i0 & lt- 3mk + 2m — 2k — 1, такое, что u (i0) = z. Следующие результаты дают достаточные условия конечности величины Ud (F, A).
Теорема 4. Пусть F (x) — многочлен Галуа степени m над кольцом R, удовлетворяющий условию
T (F) & gt-p2(n- qnl — 1) qm 7 2.
Пусть также, а — корень многочлена F (x) в расширении S = GR (qmn, pn) кольца R. Тогда при условии, что система, а % …, а s линейно независима над R, верно неравенство Ud (F, A) & lt- да.
Нетрудно заметить, что результат теоремы 4 нетривиален при выполнении неравенства m & gt- 2n1(1 + o (1)). Теорема 5. Пусть 1 = t = 1 и F (x) = F1(x) F2(x), где F1(x), F2(x) — унитарные и реверсивные многочлены над R, такие, что (T (F1), T (F2)) = 1. Пусть также для произвольной последовательности u е Lr (Fs), s = 1, 2, для каждого 0 & lt- k & lt- n найдется i0 & lt- T (F) со свойством ||u (i0)|| = k. Тогда верно неравенство Ud (F, A) & lt- да.
Теорема 6. Пусть 1 = t = 1 и F (x) = F1(x) F2(x), где F1(x), F2(x) — взаимно простые, унитарные, реверсивные многочлены Галуа над R, степеней m и k соответственно, такие, что
d0 & gt- p2(n — 1) q m 7 2, d1 & gt- p2(n — 1) q k 7 2,
где ti = T (Fj), di = ti / (t1, t2), i = 1, 2. Пусть также выполнено равенство (T (F1), T (F2)) = 1. Тогда верно неравенство Ud (F, A) & lt- да.
В некоторых случаях удается получить более точные оценки величины Ud (F, A). Всюду далее R = Z4, 1 = t = 1, h (x) = x11 и вместо Ud (F, A) будем писать Ud (F). В [2] показано, что если F (x) — многочлен максимального периода степени m, то для любой u из Lr (F) выполнено равенство rank (u1) = m (m + 3) / 2. И поэтому Ud (F) & lt- m (m + 3) / 2. Ниже приводятся оценки расстояния единственности для трехчленов вида F (x) = xm + axk + b, (a, b) Ф (1, 1).
Вид F (x) Дополнительные условия Теоретически полученная верхняя оценка Ud (F) Точные значения Ud (F) для m & lt- 18
x S 1×1 F (x) примитивный, k & lt- (m2 — m) / (2m — 3) m (3 + k) — 2k + 1 Ud (F) & lt- 3m
F (x) примитивный, k & gt- (m2 — m) / (2m — 3) m (3 + m — k) — m + k + 1
kделит m 4m — 2k + 1
m-kделит m 3m + k + 1
x s 1 x A- 1 F (x) примитивный, k & lt- (m2 — 2m) / (2m — 3) m (3 + k) — k + 1 Ud (F) & lt- 3m
F (x) примитивный, k & gt- (m2 — 2m) / (2m — 3) m (3 + m — k) — 2m + 2k + 1
kделит m 4m — k + 1
m-kделит m 2m + 2k + 1
x s 1 x A- 1 3 F (x) примитивный, k & lt- (m — 1) / 2 m (3 + k) — k + 1 Ud (F) & lt- 4m
F (x) примитивный, k & gt- (m — 1) / 2 m (3 + m — k) — m + k + 1
kделит m 4m — k + 1
m-kделит m 3m + k + 1
Расстояние единственности семейства координатных последовательностей
7
Оказывается, для большого числа трехчленов максимального периода теоретическая оценка расстояния единственности существенно меньше m (m + 3) / 2. Имеющиеся результаты точного вычисления на ПК расстояния единственности для указанных многочленов позволяют выдвинуть гипотезу о том, что для таких многочленов Ud (F) & lt- 4m.
Показано, что если F (x) е {x2 + 2i + x' + 1, x2 + 3i + x + 1, x4 + 3i + x2 + 1}, i & gt- 0, то Ud (F) = да.
В отдельных случаях можно указать точное значение величины Ud (F).
Теорема 7. Пусть R = Z4, 1 = t = 1, h (x) = x11 и F (x) = xm — x — 1. Тогда справедливо равенство Ud (F) = 3m. Автор выражает глубокую благодарность А. А. Нечаеву за помощь в проведении исследования и ценные советы по оформлению данной работы.
ЛИТЕРАТУРА
1. Кузьмин А. С., Куракин В. Л., Нечаев А. А. Кольца Галуа в приложениях к кодам и рекуррентам // Труды Академии криптографии РФ. Тема 26. М., 1998.
2. Нечаев А. А. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 4. № 1. С. 123 — 139.

ПоказатьСвернуть
Заполнить форму текущей работой