Оценки числа появлений элементов на отрезках линейных рекуррентных последовательностей | ПДМ. 2013. № 1(19).

Оценки числа появлений элементов на отрезках линейных рекуррентных последовательностей

Рассмотрен некоторый класс тригонометрических сумм от линейных рекуррентных последовательностей. Эти суммы исследуются с использованием метода В. М. Сидельникова. Получены оценки числа появлений элементов на отрезках линейных рекуррент, которые в некоторых случаях уточняют ранее известные результаты.

Estimates for the number of element appearances in segments of linear recurrent sequences.pdf Введение Изучение числа появлений элементов в линейных рекуррентных последовательностях (ЛРП) над кольцами является одной из важных математических задач. Интерес к этой задаче связан прежде всего с построением на основе ЛРП генераторов псевдослучайных чисел, использующих различные способы усложнения аналитического строения линейных рекуррент (см., например, [1]). Пусть GF(q) —конечное поле из q элементов, f (x) = xm — am-1xm-1 —... — a\x — a0 — реверсивный (a0 = 0) неприводимый многочлен степени m над этим полем. Линейной рекуррентной последовательностью над полем GF(q) с характеристическим многочленом f (x) будем называть последовательность u = u(0)u(1)u(2) ... элементов этого поля, удовлетворяющую соотношению u(i + m) = a0u(i) + a^(i + 1) + ... + am-iu(i + m — 1), i ^ 0. Каждая такая ненулевая ЛРП u является чисто периодической последовательностью, при этом её период T(u) равен периоду T(f) многочлена f(x) и делит qm — 1 (см., например, [2]). Рассмотрим линейные рекуррентные последовательности u1, u2, ..., ur с характеристическим многочленом f (x). Назовём эти последовательности линейно независимыми над полем GF(q), если для всех ненулевых векторов с = (c1 , c2,... ,cr) Е GF(q)r последовательность c1u1 + c2u2 + ... + crur является ненулевой. Обозначим через Ni(z, u1,... , ur) количество целых чисел i Е {0,1,... , I — 1}, удовлетворяющих условиям u1(i) = z1, u2(i) = z2, ..., ur(i) = zr, где z = (z1,z2,..., zr) Е GF(q)r. Таким образом, величина Ni (z, u1,... , ur) равна количеству появлений r-граммы z на отрезке длины I последовательности векторов, элементы которой имеют вид (u1(i), u2(i),... ,ur(i)) для всех i ^ 0. Всюду в дальнейшем будем считать, что u1, u2,... ,ur —линейно независимая система ЛРП над полем GF(q) с реверсивным неприводимым характеристическим многочленом f (x). В работах В. И. Нечаева [3] и И. Е. Шпарлинского [4] доказано, что для произвольной r-граммы z Е GF(q)r при всех l, не превосходящих период T = T(f) многочлена f (x), справедлива следующая оценка: N (z,ui, . . . ,Ur) - -1q ^ (Lz! q f in t. qr Величина l/qr представляет собой «естественное» среднее значение для количества появлений r-граммы на отрезке длины l в последовательности векторов. Таким образом, неравенство (1) можно рассматривать как верхнюю оценку модуля отклонения количества появлений r-граммы на отрезке ЛРП векторов от средней величины. Из этого неравенства следуют верхняя и нижняя оценки числа Ni(z,u1}... ,ur). При условии l ^ qm/2+r in т нижняя оценка рассматриваемой величины больше нуля, а верхняя — меньше l, т. е. оценка (1) нетривиальна. Впервые она была получена Н. М. Коробовым в [5] для простого поля и случая, когда ЛРП u1,u2,... ,ur — сдвиги одной последовательности. В этой работе впервые был применен аппарат тригонометрических сумм для получения оценок количества появлений элементов в ЛРП. В. М. Сидельниковым в работе [6] в случае, когда q — простое число, доказано неравенство ' l Ni(z,ui,... ,u-)--qr ^ ^ (3(qml - l2)) Оценка (2) является нетривиальной и улучшает оценку (1) при ^3q(m+3r)/2 ^ l ^ 1((т + 3r)inq)3qm/2. В данной работе доказано, что в условиях, сформулированных для результата (1), и при дополнительном условии l ^ min{T/2, T/(T, q — 1)} справедлива следующая оценка: Ni(z,ui,... ,u-) - -lqr qr - 1 3q 3 q ((q - i)qml -12) (3) qr (q - 1Ц2 Оценка (3) является нетривиальной и улучшает оценку (1) при значениях l, удовлетворяющих условию V3q — 3 2 ^ l ^ q f ln3 т, л/hCq) где h(q) = 2(q - 1)2/q. Правые части неравенств (2) и (3) совпадают, если q = 2. Оценка (3) улучшает также оценку (2) при q ^ 3 и ^ < l < 10«Л vm 13 q Кроме того, при q ^ 3 правая часть неравенства (3) меньше правой части неравенства (2) в у/2(q - 1)/q раз. 1. Оценка тригонометрической суммы Для изучения количества появлений элементов на отрезках ЛРП докажем вспомогательные результаты о тригонометрических суммах. Обозначим через х аддитивный характер поля GF(q), определённый на элементах поля равенством x(x) = = exp{trp(x)2ni/p}, где p — характеристика поля GF(q); trp(x) — функция следа из поля GF(q) в поле GF(p); i — мнимая единица. Пусть L(f (x)) —множество всех ЛРП над полем GF(q) с характеристическим многочленом f (x), а L(f (x))* —множество всех ненулевых ЛРП из множества L(f(x)). Период каждой ЛРП из множества L(f (x))* равен периоду T многочлена f (x) и порядку корня а многочлена f (x) в мультипликативной группе поля GF(qm) (см., например, [2]). Определим величину vi(z,u) следующим равенством: i-i vi(z,u) = Е X(—cz) Е X(cu(i)) cgGF(q)* i=0 где GF(q)* —мультипликативная группа поля GF(q), а z — произвольный элемент этого поля. Сформулируем и докажем некоторые свойства этой величины. Лемма 1. Пусть f (x) —реверсивный неприводимый многочлен степени m над полем GF(q), T — его период, а l —натуральное число, не превосходящее величину T/(T, q — 1). Тогда для любого элемента z поля GF(q) справедливо соотношение 2 _ Г (q — 1)qml — l2, если z = 0, u^))*|vi(z,u)| I (q — i)(qmi — (q — i)i2), если z = 0.' (4) Доказательство. Левую часть (4) можно представить в виде _I-1 _ Е Е х(—cz)x(—bz) Е x(cu(i))x(bu(j^ ueb(f (x))* b,ceGF(q)* i,j=0 где черта обозначает комплексное сопряжение. Очевидно, что x(x) = X 1(x) = х(—x). Воспользуемся этим в (5) и получим Е Mz,u)|2 = Е Е х(—cz + bz)Ei-=o x(cu(i) — bu(j)). (6) ueb(f (x))* ueb(f(x))* b,c€GF(q)* Для нулевой последовательности u из определения величины v(z,u) следует, что при z = 0 она принимает значение -l, а при z = 0 —значение (q -1)l. Таким образом, получим 22 Е |vl(z,u)|2 — l2, если z = 0, 22 lvi (z,u)i — (q — 1) ueb(f (x)) ue£(x))* |Vi(z,u)|2 =i ^E^ ivi(z,u)|2 — (q — 1)2l2, если z = 0 Для любой ЛРП из множества L(f (x)) найдётся единственный элемент y из поля GF(qm), такой, что u(i) = trq (Yai) для всех i ^ 0, где trqm (x) — функция следа из поля GF(qm) в поле GF(q) (см. [2, Теорема 8.24]). Далее, с использованием этого представления знаков ЛРП, из выражения (6) получим Е |v(z,u)|2 = Е х(—cz + bz) Е Е Xm(Y(cai — baj)). (8) ueb(f (x)) b,c€GF(q)* i,j=0 7eGF(qm) где Хт — аддитивный характер поля GF(qm), определённый на элементах этого поля равенством xm(x) = x(trqm (x)). Воспользуемся соотношением ортогональности для характеров и получим Е xm(7(ca' - Ь*)) = f' ^ g = . (9) 7eGF(qm) I 0, если ca = ba. Если для некоторых элементов Ь и с поля GF(q) выполняется соотношение ca: = baj, то элемент a:-j является элементом поля GF(q). Далее получим a(:-j)(q-1) = e и, следовательно, T(f) = ord a|(j - i)(q - 1), T(f)/(T(f), q - 1)|(j - i). Элементы i и j всегда меньше T(f )/(T(f ),q - 1), значит, соотношение ca: = baj выполняется тогда и только тогда, когда i = j и Ь = с, откуда, используя (8) и (9), получим Е |v (z,u)|2 = Е 1-1 qm = (q - 1)qml. (10) u€L(/(ж)) cgGF(q)» :=0 Для завершения доказательства остаётся подставить равенство (10) в равенство (7). ■ Лемма 2. Пусть u — ЛРП периода T над полем GF(q), j — целое число из отрезка -T, T, z — произвольный элемент поля GF(q). Тогда |v(z,xTu) - Vi(z,xT+ju)| ^ q|j|. Доказательство. Пусть x(x) = exp{trp(x)2ni/p} для всех элементов x поля GF(q). Воспользуемся соотношением ортогональности для характеров i-1 Е Е x(c(u(i) - z)) = qNi(z,u), :=0 cgGF(q) где Ni(z,u) —число появлений z среди элементов u(0), u(1),... , u(l - 1). Так как |Ni(z,xTu) - Ni(z,xT+ju)| ^ |j| для всех j Е -T, T, то |vi(z,xTu) - vi(z,xT+ju)| = = q|Ni(z,xTu) - Ni(z,xT+ju)| ^ q|j|. ■ Лемма 3 [7]. Пусть q — натуральное число, тогда для всех действительных чисел v ^ 0 справедливо неравенство v2 + 2£ (v - qj)2 ^ j=1 3q Теорема 1. Пусть f (x) — реверсивный неприводимый многочлен степени m над полем GF(q), T — его период, u — ненулевая ЛРП над полем GF(q) c характеристическим многочленом f (x), z — элемент поля GF(q), а l — натуральное число. Тогда при l ^ min{T/2, T/(T, q - 1)} справедлива оценка |vi(z,u)| ^ (3- ((q - 1)qml - l2) Доказательство. Рассмотрим в множестве L(f (x))* ЛРП u0, для которой величина v = | Vi(z, u0) | равна максимально возможному значению. Пусть j — произвольное целое число из интервала - [v/q], [v/q]. Через uj обозначим ЛРП, определённую равенством uj (i) = u0(i + T + j) для всех i ^ 0. Покажем, что среди uj, где j Е — [v/q], [v/q], нет одинаковых. Если найдутся целые числа j1 и j2, такие, что uj-1 = uj2, то для корня а многочлена f (x) будет справедливо соотношение aj1-j2 = e. Это равенство может выполняться лишь при условии, что T делит ji — j2. Как показано при доказательстве леммы 2, справедливо соотношение v = |qNi (z,u0) — l|, поэтому v < ql ив условиях теоремы справедливы неравенства |ji — j2| ^ 2[v/q] < 2l ^ T. Значит, uj1 = uj2 тогда и только тогда, когда ji = j2. Теперь с использованием лемм 1-3 имеем [v/q] [v/q] 2v 3 (q — 1)qml — l2 ^ E |vi(z,uj)|2 ^ v2 + 2£ (v — qj)2 ^ —. 3 j = E[v/q\ i 4 j j=1 4 3q Окончательно получим |vi(z,u)| ^ v ^ ((q — 1)qml — l2)) Теорема доказана. Заметим, что полученная оценка справедлива для произвольного z Е GF(q). Далее сформулируем результат, доказанный О. В. Камловским для случая z = 0. Теорема 2 [7]. Пусть f (x) —реверсивный неприводимый многочлен степени m над полем GF(q), T — его период, u — ненулевая ЛРП над полем GF(q) c характеристическим многочленом f (x), а l —натуральное число. Тогда при условии l ^ t/2, где t = T/ (T, q — 1), справедлива оценка i |vi(0,u)| ^(qml — (q — 1)l2)4 3 2. Оценка числа появлений r-грамм в ЛРП векторов Сформулируем и докажем основной результат работы. Теорема 3. Пусть f (x) —реверсивный неприводимый многочлен степени m над полем GF(q), T — его период, u1, u2,..., ur — линейно независимая система ЛРП над полем GF(q) с характеристическим многочленом f (x), l —натуральное число, не превосходящее значения min{T/2, T/(T, q — 1)}, z — произвольный элемент множества GF(q)r. Тогда справедлива следующая оценка: Ni(z,u1,... ,ur) — qr 1 < ^(f (qml—l2)N 3 Доказательство. Пусть x(x) = exp{tr^(x)2ni/p} — аддитивный характер поля GF(q), где p — характеристика поля. Используя соотношения ортогональности для характеров, представим N (z, u1,... , ur) в виде i-1 r 1 Ni (z,u1,'.',ur ) = ЕП" E X (cj (uj(i) — zj)). i=0 j=1 q Cj €GF(q) Тогда справедливо соотношение _ 1 ( r \ Ni(z,u1 ,'..,ur) = — E E х Ecj(uj(i) — zj) . (11) q i=0(ci,C2,...,cr)€GF(q)r \j=1 / 1) Пусть z = 0. Тогда воспользуемся результатом теоремы 2: qr 1 ^3q(qml - (q - 1)l2) Ni(0,u1,...,ur) - qr 3 qr (q - 1) V 2 2) Пусть далее z = 0. Для каждого вектора с = (с1, с2,..., cr) через u обозначим такую последовательность, элементы которой определены равенствами uc(i) = £ cjuj (i) для всех i ^ 0, j=1 и обозначим £ cj zj. j=1 Последовательность u — ЛРП с характеристическим многочленом f (x), причём из условия линейной независимости системы u1, u2, ..., ur следует, что для всех с = с ЛРП u является ненулевой. В равенстве (11) выделим слагаемое, соответствующее нулевому набору (с1, с2,... , cr), тогда получим соотношение _ l 1 i-1 Ni(z,u1,...,ur ) = — + — £ £ x(uc(i) - zc). q q :=0 c€GF(q)r\{0} Для любого а Е GF(q)*справедливо соотношение au = ua5, az5 = za5, следовательно, получим _ l 11 i-1 Ni(z,u1,...,ur) - — = — —— £ £ £ x(auc(i) - ^c^ q q q 1 a£GF(q)* :=0 c€GF(q)r\{0} z а значит, ni(z,u1,... ,u-) - -lqr qr (q 1) c€GF(q)r\{0} Из соотношения (12) следует неравенство 1 £ vi(zc,uc). f12) qr - 1 ^ —;-г max |vi(z6,uc) |. qr(q - 1) c=o 1 Д c' 1 ni(z,u1,... ,u-) - -г Используя теоремы 1 и 2, получим qr 1 ^(qml(q - 1) - l2) ni(z,u1,... ,u-) - -lqr 3 13) qr (q - 1Ц2 В силу того, что при z = 0 оценка является более точной, можем применить оценку (13) для любого z. ■ Если ограничиться случаем с = 0, то при некоторых ограничениях на l возможно доказать более сильную оценку, чем в теореме 3. T _ - Теорема 4. Пусть дополнительно, в условиях теоремы 3, l ^ ---т- и z = 0. 2(T, q - 1) Тогда справедлива следующая оценка: Ni(z,u1,... ,u-) - —r qr r-1 1 q ^ (qml - (q - 1)l2) 3q qr (q - 1Ц2 qr - qr 1 / 3q qr(q- 1) V2 q ((q - 1)qml -l2) + Доказательство. Разобьем правую часть равенства (12) на две суммы: r r/ -,4 E v (zc,uc)+——-—- ^ qr qr (q — 1) ce{GF(q)r\0:zc=0} ^(q — 1) c€(GF(q)r\0:zc=0} л,/- ч l 1 N(z,u1,... ,ur)—- = Y, v (zc,uc). Очевидно, что |{c Е GF(q)r \ 0: zc = 0} |{c Е GF(q)r \ 0: zc = 0}| = qr-1 — 1 r r—1 q — q , Отсюда получим r r— 1 r— 1 qr - qr-1 qr-1 n(z,u1,... ,u-) — -lqr 1 max |vi (0, u6)|. ^ -:-г max |vi (z6,u6)| + qr (q — 1) c=0 qr (q — 1) c=0,z=0 Применив теоремы 1 и 2, получим необходимый результат. ■ Сформулируем и докажем утверждение, вытекающее из теоремы 3. Утверждение 1. Пусть выполнено условие теоремы 3. Тогда среди элементов u(0), u(1),... , u Г [^3qm+2rL/\/Щ где h(q) = 2(q — 1)2/q, появляются все r-граммы. Доказательство. Для произвольного z Е GF(q)r справедливо соотношение qr Ш(«'"i(q—1} -l2))'

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

тригонометрические суммы, линейные рекуррентные последовательности, число появлений элементов, exponential sums, linear recurrences, the number of element appearences

Авторы

ФИООрганизацияДополнительноE-mail
Биляк Иван Богдановичг. Москваbil-ib@mail.ru
Всего: 1

Ссылки

Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии: учеб. пособие. М.: Гелиос АРВ, 2001. 480с.
Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1, 2. М.: Мир, 1988. 824 с.
Нечаев В. И. Распределение знаков в последовательности прямоугольных матриц над конечным полем // Труды матем. института им. В. А. Стеклова. 1997. Т. 218. С. 335-342.
Шпарлинский И. Е. О распределении значений рекуррентных последовательностей // Проблемы передачи информации. 1989. Т. 25. №2. С. 46-53.
Коробов Н. М. Распределение невычетов и первообразных корней в рекуррентных рядах // Докл. Акад. наук СССР. 1953. Т.88. №4. С.603-606.
Сидельников В. М. Оценки для числа появлений знаков на отрезке рекуррентной последовательности над конечным полем // Дискретная математика. 1991. Т. 3. №2. С. 87-95.
Камловский О. В. Оценки частот появления нулей в линейных рекуррентных последовательностях векторов // Чебышевский сборник. 2005. Т. 6. №1. С. 135-144.
 Оценки числа появлений элементов на отрезках линейных рекуррентных последовательностей | ПДМ. 2013. № 1(19).

Оценки числа появлений элементов на отрезках линейных рекуррентных последовательностей | ПДМ. 2013. № 1(19).

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