Восстановление полиномиально усложнённой линейной рекурренты максимального периода над кольцом Галуа по старшей координатной последовательности | ПДМ. 2014. № 2(24).

Восстановление полиномиально усложнённой линейной рекурренты максимального периода над кольцом Галуа по старшей координатной последовательности

Рассматриваются усложнения линейной рекуррентной последовательности (ЛРП) максимального периода над кольцом Галуа GR(q ,p ) с помощью некоторого многочлена E(x) над этим кольцом, а также приводится алгоритм восстановления исходной рекурренты по старшей координатной последовательности полиномиально усложнённой ЛРП.

Recovery of a polynomially complicated linear recurring sequence over Galois ring by its senior coordinate.pdf Введение В криптографии актуальным остается вопрос о восстановлении линейной рекуррентной последовательности максимального периода (в частности, её начального отрезка) над кольцом Галуа по её старшей координатной последовательности. Ранее рядом авторов исследовалась старшая координатная последовательность un-1 ЛРП максимального периода u и приводились соответствующие алгоритмы восстановления u по un-1. А. А. Нечаевым предложен алгоритм восстановления ЛРП максимального периода u над кольцом вычетов R = Z2n по её старшей координатной последовательности, впоследствии А. С. Кузьминым приведён алгоритм восстановления ЛРП максимального периода u над кольцом R = Zpn для произвольного p ^ 3. В ряде работ отечественных [1, 2] и зарубежных авторов [3-6] уже исследовалась возможность восстановления усложнённой последовательности, причём усложнения задавались с помощью «инъективных отображений», то есть отображений, которые допускают однозначное восстановление исходной ЛРП по её усложнению. Цель этой работы - для полиномиального усложнения ЛРП максимального периода u над кольцом Галуа GR(qn,pn) произвольным многочленом E(x) Е R[x] степени k ^ 1 построить алгоритм восстановления начального отрезка исходной рекурренты по значениям старшей координатной последовательности усложнённой ЛРП. 1. Постановка задачи Всюду далее R = GR(qn,pn) -кольцо Галуа характеристики pn, состоящее из qn элементов, где n Е N, p простое, q = рг. Согласно [7], множество pR всех делителей нуля есть идеал кольца R. Обозначим через R = R/pR = GF(q) поле вычетов кольца R. Эпиморфизм ^ : R ^ R, действующий по правилу ^(а) = а для всех а Е R, естественным образом можно продолжить на кольцо многочленов R[x]. Образ любого многочлена F (x) Е R [x] при таком эпиморфизме будем обозначать через F (x) Е R [x]. Подмножество K кольца R называется координатным множеством кольца R, если его элементы образуют полную систему вычетов по модулю идеала pR. Примером координатного множества является p-адическое координатное множество (координатное множество Тейхмюллера) Г(Я) = {a G R : aq = а}. Для R = GR(pn,pn) = Zpn ещё одним интересным примером координатного множества является p-ичное координатное множество $(R) = {0,1,... ,p - 1}. Известно [8], что любой элемент a G R однозначно представляется в виде a = ao + pai + ... + pra-1ara_b (1) где at G K, t = 0,1,... , n-1. Для всех t G {0,... , n- 1} определим функции YtK : R ^ K следующим образом: yk(a) = at, где at определяется равенством (1). Функция YtK называется t-й координатной функцией в координатном множестве K. Естественным образом введём на множестве K операции, положив для любых a, b G K a 0 b = yk (a + b) , a 0 b = yk (ab). Тогда (K; 0, 0) = GF(q) - поле, изоморфное R, причём изоморфизм ф : K ^ R задаётся соотношением "0(a) = а, где a G K. Изоморфизм ф также естественным образом продолжается на множество всех последовательностей Kнад множеством K. Образ любой последовательности v G Kпри таком изоморфизме будем обозначать через v G R . Стоит отметить, что по последовательности v G R можно однозначно восстановить последовательность v G K В качестве результата умножения многочлена F (x) = frxr G R [x] на последовательность u G R^ определим последовательность v = F(x)u из множества R^, знаки которой определяются следующим образом: v(i) = fru(i + r), i ^ 0. Пусть F (x) G R [x] - многочлен максимального периода, имеющий степень m и период T(F) = (qm - 1)pn-i [9]. Обозначим LR(F) = {u G : F(x)u = (0)} множество последовательностей, аннулируемых многочленом F (x). Из работы [9] известно, что период любой рекурренты из LR(F) удовлетворяет неравенству T(u) ^ (qm - 1)pn-i. Последовательность с периодом T(u) = (qm - 1)pn-i назовём ЛРП максимального периода (МП). Пусть всюду далее u G Lr(F) -ЛРП максимального периода. Для любого много-j члена E(x) = ejxJ G R[x] определим последовательность z = E(u) G R^ со знаками J=0 z(i) = eju(i)J для всех i ^ 0. Последовательность E(u) назовем полиномиальным J=0 усложнением рекурренты u с помощью многочлена E(x) над кольцом R. Для любой ЛРП v G R^ определим последовательность vt = yk(v) = (yk(v(0)), YtK(v(1)),...), которая называется t-й координатной последовательностью рекуррен-ты v в координатном множестве K. Последовательность vt является ЛРП над K, так как она периодическая. Последовательность vn-1 назовём старшей координатной последовательностью ЛРП v. В данной работе будем решать следующую задачу: по известной старшей координатной последовательности zn-1 = y^-i(z) полиномиально усложнённой рекурренты восстановить исходную ЛРП максимального периода u. Отметим, что в работе [10] эта задача решена для произвольного кольца Галуа R = GR(qn,pn) и координатного множества K с некоторыми естественными ограничениями при E(x) = x. Усложнения ЛРП u можно задавать с помощью функций Ф : Rn ^ K следующим образом: v(i) = Ф(зд(г),... ,un-i(i)). Такие отображения индуцируют отображения семейств последовательностей Ф : Lr(F) ^ Kкоторые называются «сжимающими отображениями». Как уже отмечалось, некоторые из таких отображений позволяют однозначно восстановить исходную ЛРП по её усложнению. Поставленную задачу можно свести к отображениям такого вида с помощью следующей леммы. Лемма 1. Знак координатной последовательности полиномиально усложнённой ЛРП z = E(u) представляется в виде zt(i) = Ф(и0(г),... , ut(i)), i ^ 0, t G {1,..., n - 1}, где Ф(Х0,Х1,... ,xt) = E'(x0)xt + n(x0,xi,... ,xt-i), n(x0,xi,... , xt-i) G K[x0,xi,... , xt-i]. Доказательство. Рассмотрим E(x) над кольцом R/pt+iR, где x = x0 + pxi + + ... + p*xt (mod pt+i): pt+i j f t \ j . E(x) P= E es £ px,- = £ es £ -^_pj1+2j2+...+tjtx0°... xj. s=0 y=0 у s=0 jo+...+jt=s j0! ...jt! В этой сумме нас интересуют ненулевые слагаемые при pt. Очевидно, что этому условию удовлетворяют лишь те слагаемые, у которых либо jt = 0, либо jt = 1, j0 = s - 1, ji = ... = jt-i = 0. Разбивая таким образом по jt внутреннюю сумму на две части, Ф^о,... , xt) можно представить в виде Ф^0,..., xt) = £ es ( sptx0-ixt + £ s!.--pJ'i+2j'2+...+(t-i)jt-1 x00... j1 s=0 у Jo+...+Jt-i=s j0! . . . jt-i! Значит, YtK(Ф^0,..., xt)) = E'(x0)xt + n(x0,..., xt-i). ■ Заметим, что в [2] доказана принципиальная возможность восстановления исходной рекурренты, усложнённой с помощью функции Ф^о,... , xn-i), полученной в лемме 1, однако нет конструктивного алгоритма восстановления. 2. Сечения Одним из подходов к изучению свойств координатных последовательностей является метод сечений. Определим умножение элемента a G K на элемент f G R равенством fa = yk (ra). Тогда K есть R-алгебра и можно умножать любую последовательность над K на многочлен из R[x], а также рассматривать любую периодическую последовательность w над K как ЛРП над полем R. Под сечением будем понимать умножение последовательности на некоторый многочлен, в результате чего получается более простая рекуррента. Обозначим Tt = pt(qm - 1), t = 0,1,... , n - 1, т0 = т. В работе [11] доказана следующая лемма. Лемма 2. Пусть F(x) G R[x] -многочлен максимального периода. Тогда существуют многочлены Ф^+^x) G R[x], t G {0,... , n - 1}, такие, что xTt - e = pt+i^(t+i) (x) (mod F(x)), t G{0,...,n - 1}, ¥(t+i) (x) = 0, deg Ф(^ (x) < m, (2) причём, если p ^ 3, t ^ 1, то Ф^^) = Ф(t+1)(x) (mod pt+i). Очевидно, что многочлены Ф(^(х), где t Е {1 ,...,n}, определены неоднозначно, поэтому выберем их и зафиксируем. Последовательность u(t) = Ф(*)(ж)м назовём t-й производной последовательностью рекурренты u. Нетрудно видеть, что u(t) - ЛРП максимального периода [8]. В работе [11] также доказано, что u(1) = u(t) t > 1 u0 = u0 , 1 > 1, fr>\ u(°2) = u1t), t > 2. (3) Далее считаем, что элементы координатных множеств K = {a1,...,aq} и r(R) = = {в1,... ,вд} упорядочены так, что at = в (mod p), t = 0,... , q - 1. Известно [12], что существует единственный многочлен Фк (х) = фд-1хд-1 + ... + + ф0 Е R[x], такой, что Фк (et) = at, t Е {0,...,q - 1}, при этом Фк (х) = = х (mod p) и ф0 = 0. Многочлен Фк(х) называется интерполяционным многочленом координатного множества K. Обозначим через ФК(х) = хд-1 + ... + Е R[x] такой многочлен, что Фк(х) = х + рФК (х). dF Пусть F(х1,...,хк) Е Д[х1,...,хк]. Тогда через -- будем обозначать формальdxj ную частную производную многочлена F по переменной Xj для всех j Е {1,... , k}. dF Эти производные являются многочленами из Д[х1,... , ]. Через -- (а1,... , ) будхj дем обозначать значение частной производной в точке (а1,..., ак) Е Rk. В работе [12] доказана следующая лемма. Лемма 3. Для любого F(х1,...,хк) Е R^,...,хк] существует такой многочлен F*(х1,... , хк), что F(х1,... , хк)д = F(xf,... , хк) + pF*(х1,..., хк), и для любых a1, . . . , ak Е K к dF yK(F(a1,..., ак)) = -F;(аь ..., ак) + E т^К ..., ак)ФК(ai)- m i= 1 ^ (4) - ФК (F (а1,...,ак)) (mod p), в частности, для любых а, b Е K p-1 1 7К (а + b) = -ггт ahj bh(p-j) + ФК (а) + ФК (b) - ФК (а + b) (mod p). (5) j=1 j!(p - j)! Для любого s Е {1,... ,n} обозначим b(s) = E'(u)u(s) Е R^, где E'(x) -производная многочлена E(х). Пусть также b(s) = yK(b(s)), s Е {1,... , n}, t = 0,1. Исследуем некоторые свойства последовательности b(s). Так как b0s) (i + т) = b0s)(i) для всех i > 0, то T(b0s)) | т для всех s Е {1,... , n}. Лемма 4. При всех t Е {2,...,n + 1} для координатной последовательности bf 1) = yK(E'(u)u(t-1)) верно следующее равенство: b(1t-1) = E '(зд)ФК (u0t-1)) - ФК (E'(u0 )u0t-1)) - E; (u0)u0t-1)+ (6) +E''ЫФК(u0)u0t-1) + E''(u0)u0t-1)u1 + E'(u0)uSt-1) (mod p), где E;(х) Е R[x] -такой многочлен, что E'(x)g = E'(xg)+ pE;(х); E''(x) -производная многочлена E'(x). Доказательство. Обозначим v = E'(и), w = u(t i), Vj = 7K(v), wj = 7K(w), j = 0,1. Тогда имеем &it-i) = (vw) = 7f ((vo + pvi )(wo + pwi)) = = 7f (vowo + p(viwo + vowi)) = yk(vowo) + viwo + vowi (mod p). Заметим, что vowi = E/(uo)uit i) (mod p). (8) Найдём yk(vowo). Возьмём в условиях леммы 3 в качестве F(xi,x2) многочлен xix2 Е Е R[xi,x2], тогда из равенства (4) имеем (9) (vowo) = WoФK(vo) + voФК(wo) - ФК(vowo) = = «?-1)ФК(E'(uo)) + ^ЫФ^(uot-i)) - ФК(E'(uo)uot-i)) (mod p). k Так как E'(x) = E Jejxj-i, то j=1 k k . k v = E'(u) = E jej(uo + p«i)j-i = E uo-1 + p«i E j(j - 1)ejuo-2 = j=i j=i j=2 (10) = E'(uo) + pE//(uo)u1 (mod p2). Теперь, используя соотношения (10) и взяв в (4) в качестве F(x1,...,xk) многочлен E'(x), получаем f11) f12) vi = 7f (E '(uo)) + E ''(uo)ui = = -E;(uo)+E"(«o^K(uo) - ФК(E'(uo)) + E"(uo)«i (mod p). Умножая (11) на wo = 1), находим viwo = -E;(uo)«ot-1) + E"(uo^K(uo)«ot-1) - ФК(E/(uo))4*-1) + + E//(uo)«ot-1)u1 (mod p). Подставляя (8), (9) и (12) в соотношение (7), получаем (6). ■ Для r, t Е N обозначим I 1, если r = t, £(r = t) = < 0, если r = t. Обозначим h = pr-i. Перейдём к построению сечений координатных последовательностей. Теорема 1. Для координатных последовательностей ЛРП z = E(и) справедливы следующие соотношения: для t = 1,... , n - 1 (xTt-1 - e)zt = E/(u)«ot) (mod p); (13) для t = 2,... , n - 1 (xTt-2 - e)zt = 7f (zt-i + b(t-1)) + 15(t = 2)E//(u)(«ot-1))2 (mod p); (14) для j = 1,... , p - 1, t = 1,... , n - 1 (xTt-1 - e)jzj = j! (b0t})j = j! (e'Mu?)j (mod p); (15) для j = 1 , . . . , p - 1 , t = 1 , . . . , n - 1 (xTt-1 - e)j-izj = j!z, (60t})j-i + ~j! (&0?)' (mod p); (16) для t = 2, . . . , n - 1 (xT - e)p"-p"z, = (z,-! (b0-))p-i)h + (b0-))ph - q-i s! / ,, -,N\s-ji (17) - e # E -T-гzj-1 (b0t-iM + e(p,t) (modp), s=p-i jl+...+jp=s, ji! ...jp! V 7 jl>0,j2>0,...,jp>0 где e(p t) = |e'(м0)Ф(1)(х)м0!) + E''(U0) (u0!^2 , если p = 3,t = 2, I 0 в остальных случаях. Доказательство. Докажем равенство (13). Учитывая, что T(ut) = т, [8], по лемме 1 получим T (zt) | т,. Тогда (xTt-1 - e)z = pt(xTt-1 - e)zt (mod pt+i). (18) С другой стороны, из соотношения (2) следует, что (xTt-1 - e)u = ptu0t) (mod pt+i), или u(i + Tt-i) = u(i) + ptu0t)(i) (mod pt+i). (19) Теперь, используя равенство (19), имеем для всех i ^ 0 (20) k (xTt-1 - e)z(i) = z(i + T,-i) - z(i) = E ej (u(i + т,-)-7 - u(i)j) = j=0 k = E j'eju(i)j-iptu0t)(i) = ptE'(M(i))u0t)(i) (mod pt+i). j=0 0 0 Сравнивая соотношения (18) и (20), получаем равенство (13). Докажем равенство (14). Используя (2), получаем (xTt-2 - e)u = pt-iu(t-i) = pt-iu0t-i) + ptu(it-i) (mod pt+i). Тогда для всех i ^ 0 u(i + т,-2)j = (u(i) + pt-iu0t-i)(i) + ptuit-i)(i^j = u(i)j + ju(i)j-i (pt-iu0t-i)(i)+ + p4t-i)(i)) + ju(i)j-2 (pt-iu0t-i)(i) + Ptuf-i)(i))2 = u(i)j + (21) +ju(i)j-i (pt-iu0t-i )(i) + P'u it-i )«) + 0,j2>0,...,js+2>0 Подставляя s = p - 2 в равенства (27) и (29) и используя теорему Вильсона, получаем (xT-2 - e)P-2A = (z,-1 (b°'_())P_()" + p " 2 + (b°'_())g (mod p), д-1 r! / / \ \ r-ji (xTt-2 - e)p-2D = - E # E . ! ! . ! zj-1 (b0t-1M (mod p). r=p-1 jl+...+jp =r, j1! ...jP! ^ ' jl>0,j2>0,...,jp>0 Таким образом, (x-2 - e)P-2yK (z,-1 + bf1)) = (z'-1 (b°'-())P-1)" + ^ (Г1^f - Пользуясь равенствами (3) и соотношениями T(«') |t( и (xT - e)u1 = «oi) (mod p) получаем .«(1) (xTt 2 - e)u1 0, если t > 2. Так как T(«oi)) | to, имеем (xTt-2 - e)P-2«i = { «oi), если p =3,t = 2, (32) 0 в противном случае. (33) В итоге из равенств (32) вытекает E//(uo)«ot-1)(xTt-2 - e)P-2«i = (E//(uo)(«oi))2, если p = 3,t = 2, o 0 в противном случае. Рассмотрим (xTt-2 - e)u(1t 1): (xTt-2 - e)u(lt-1) = (xTt-2 - e)7f (u(t-1)) = (xTt-2 - e)7f (Ф('-1)(x)u) = = (xTt-2 - e)7f (Ф(1) (x)u) = (xTt-2 - e)7f (Ф(1)(x)(uo + p«i)) = = (xTt-2 - ebf (Ф( 1 ) (x)uo + pФ( 1 ) (x)u 1) = (xTt-2 - ebf (Ф( 1 )(x)uo) + + (xTt-2 - e) (Ф( 1 )(x)u ') (mod p). Так как период последовательности yk (Ф( 1 )(x)u^ делит т, то, используя соотношения T(и 1) | т( и (xT - e)u 1 = «o' ) (mod p), получаем (34) , T . (t_-i ) , T ,т(-i ^ . I Ф( 1 )(x)«o ), если t = 2, (xTt-2 - e)uf 1 ) = (xTt-2 - e^( 1 ) (x)ui = ^ v ; o ' 10 в противном случае. Пользуясь (34) и соотношением T(«o' )) | т, получаем E/(«o)(xTt-2 - e)P-2«f-') = ( E/(U0)Ф( 1)(x)«oi ), если p = 3,t = 2, (35) I 0 в противном случае. С учётом (33) и (35) равенство (31) примет вид (xTt-2 - e)P-2b(t- 1 ) = fE/(uo)Ф( 1 )(x)«oi) + E//(«o)(«oi ))2, если t = 2, p = 3, (36) 1 0 в противном случае. Таким образом, с использованием сравнения (26) имеем (xTt-2 - e)P-'z* = (xTt-2 - e)P-27f (z* + bot-1)) + (xTt-2 - e)P-2b1t-1) (mod p). (37) Объединяя результаты (30), (36) и (37), получаем Pt-1-Pt-2. = L (,(t-1))P-')2, p-2 + 22-1 ^(t-1))P2 (xT - e)P 1-P zt = ( zt-1 ( bot- 1 )) ) + " ( b q-1 r1 • / /i i\\ r-л - E # E zj- 1 (bot-'M + e(p,t), r=P-1 j1+...+jp = r, j1! ...jP! v 7 j1^o,j2>o,...,jp>o где . E/(uo)Ф(1)(x)«oi) + E//(uo)(«oi))2, если t = 2,p = 3, e(p,t) = \ „ «o ), если t = 2, 0 в противном случае. Теорема доказана. 3. Алгоритм восстановления Прежде чем перейти к алгоритму восстановления, приведем еще несколько результатов. Для всех t Е N обозначим t =Е Vi(t)pi, Vi(t) Е {0,... ,p - 1}, wp(t) = Е Vi(t), i>0 i>0 t = E Pi(t)qi, Pi(t) Е {0,.. . , q - 1}, wq(t) = £ pi(t), i>0 i>0 где vi(t) -коэффициент при pi в p-ичном разложении; pi(t) - коэффициент при qi в q-ичном разложении; wp(t) - p-ичный вес числа t; w(t) - q-ичный вес числа t. Для доказательства основного результата потребуется ещё одна лемма. Лемма 5 [13]. Пусть a Е N, k1,..., ka Е N0, k = k1 + ... + ka, e - максимальная k! степень простого числа p, делящая полиномиальный коэффициент -----. Тогда k1!... ka! _ Wp(k1) + ... + Wp(ka) - Wp(k) а) e = p-1 ; б) TT^-Tl = (-p)£ П (k V"(k)! (k )! (mod p^1). k1! ...ka! m>0 V"(k1)! ...Vm(ka)! Так как F? (x) Е R [x] -примитивный многочлен, то существует корень ш этого многочлена в расширении Галуа S = GF(qm) поля R. Известно, что любая последовательность из Lr (F?) представляется в виде линейной комбинации биномиальных последовательностей с корнями из множества корней многочлена F?(x) Е R[x]. к Лемма 6. Пусть E(х) = Е erxr и deg E(x) = k' Е {1,..., q - 1}. Тогда последоxr r=0 7 (1) вательность b0 представляется в виде b01) = (s + 1)es+1u0 0 u01) 0l, s E{0,...,k' - 1}, (pi(x),ps(x)) = e, где l Е Kрг(х) -минимальный многочлен ЛРП l; ps(x) -минимальный многочлен ЛРП u0u01). Доказательство. Из определения b01) получаем к'-1 b01) = E'(u0) 0 u01) = Е 0(r + 1)er+1u0 0 u01). r=0 Для доказательства леммы достаточно показать, что для двух разных r1,r2 Е {0, ... , k' - 1} выполняется (prl (х), pr2 (х)) = e, где pri (х) - минимальный многочлен последовательности u0® u01), i = 1, 2. Воспользуемся биномиальным представлением ли- (1) нейных рекуррент u 0 и u 0 : "-1 m-1 u0(i)= Е (Сш^ (mod p), u)(i)=E (^ш^)^ (mod p), j=0 0 j=0 где ш - корень F(x) в поле S?; £ Е S?; d Е {0,...,т - 1} - такое, что xd = = Ф(1)(х) (mod -?(х)). Для любого r Е {0,... , k' - 1} представим ЛРП u0 0 u01) в виде сумм биномиальных последовательностей: m - l /m - l r! E ^д'+д4 , , i £ ^д'+д4 u0(i) 0 u01)(i) = E -^-j-Сa=° " шд^ш ^ " ) (mod p), i > 0. jo+...+jm -l=r, j0! . . . jm-1! t€{0,...,m-1} /m-1 \ о Отсюда следует, что I Е -«q" + q* ) = r +1. Значит, uo 0 u ) представляется в виде \«=o / линейной комбинации биномиальных последовательностей с коэффициентами из S и корнями вида ш*, где t G {0,... , т - 1}, (t) = r +1. Таким образом, множества корней в поле разложения многочленов (x) и ^r2 (x) не пересекаются при г- = r2; значит, они взаимно просты. ■ Лемма 7. Пусть знаки последовательности uo представляются в виде функции след uo(i) = tr(£wl) (mod p), где £ G S?, i ^ 0. Тогда для любого s G {0,... , q - 2} последовательность uo 0 ^^ над координатным множеством K представляется в виде uo 0 Uo-) = ll ® l2, где l',l2 G K(x) -минимальный многочлен последовательности l(; (x) - минимальный многочлен последовательности l2; = tr(£s+1wi(s+1)+d) (mod p) и (x),^i2(x)) = Доказательство. Из доказательства леммы 6 следует, что для любого s G {0, ... , q - 2} последовательность uo 0 ^^ представляется в виде m - 1 /m - 1 \ с / s пь s ^ s! ^ 12 t, ц J2 iaq^+q' . , . uo(i) 0 uo )(i) = E -j-:-^a=0 Va=o ) (mod p), i ^ 0. jo+...+jm-1=s, -o! . . -m-1! te{o,...,m-1} С другой стороны, период последовательности uo 0 ^^ делит to = qm - 1. Так как эта последовательность над полем K и q взаимно просто с to, то её минимальный многочлен ^(x) есть произведение попарно различных унитарных неприводимых многочленов, степени которых делят m, а сама последовательность представляется в виде суммы o(i) 0 uo rec где C - множество минимальных представителей q-циклотомических классов, на которые разбивается множество {0,... , to - 1}. Слагаемое вида аш(5+1)г появляется в (38) при условии q* + -o + q-1 + ... + qm-'-m-i = S + 1 (mod qm - 1). Такое возможно тогда и только тогда, когда t = 0, -o = s, - ( = ... = -m-( = 0. Значит, а = ■ Индексом нелинейности ненулевого одночлена lx* будем называть число ind lx* = = wp(t) [10]. Для нулевого многочлена индекс нелинейности положим равным -то. Индексом нелинейности ind^(x) ненулевого многочлена ^(x) будем называть максимум индексов нелинейности его мономов. Поскольку интерполяционный многочлен произвольного координатного множества K имеет степень, не превышающую q - 1, то 1 ^ ind Фк(x) ^ (p - 1)r. Отметим, что, согласно [14], многочлен E?(x) как функция над конечным полем R из q элементов может быть представлен многочленом E(x) над этим же полем, степень которого не превышает q - 1. Поэтому в дальнейшем считаем, что deg E?(x) ^ q - 1. Получим теперь основной результат. uo(i) 0 uo-)(i) = E tr(arw") (mod p), i ^ 0, (38) k Теорема 2. Пусть E(ж) = £ G R[x], u G ) -ЛРП максимального периs=0 ода, z = E(u) и выполнены следующие условия: E'(ж) не имеет корней в поле R; (39) ind Фк (ж) ^ p - 1; (40) существует такое s G {0,..., k - 1}, что (s + 1, qm - 1) = 1 и es+1 = 0. Тогда по последовательности zn-1 = y^L 1(E(u)) однозначно восстанавливается начальный отрезок u(0),..., u(m - 1). Доказательство. Приведём конструктивный алгоритм восстановления u(0),..., u(m - 1) по zn-1. Этап I. Полагая в соотношении (13) t = n - 1, находим последовательность b01). По условию существует такое s G {0,... , k - 1}, что коэффициент многочлена es+1 = 0. Согласно лемме 6, ЛРП ь01) представляется в виде b01) = (s + 1)es+1u0 0 u01) ф l, причём минимальный многочлен рг (ж) ЛРП l взаимно прост с минимальным многочленом ЛРП u0 0 u01). Отсюда по известной последовательности b0 ) однозначно восстанавливается последовательность u0 0 u01). Согласно лемме 7, по ЛРП u0 0 u01) можно восстановить последовательность tr(£s+1wdw(s+1)i), i ^ 0, а по ней £s+1. Пользуясь тем, что (s + 1,qm - 1) = 1, находим величину £. Таким образом, последовательность u0 восстановлена. Этап II. Поскольку u0 - ЛРП МП, то последовательность u01) -её сдвиг, и она также является рекуррентой максимального периода с периодом т0 = qm - 1. Тогда существует такое i0 G N0, что u01)(i0 + j) = 0 для всех j G {0,..., m - 1}. Этап III. Из условия (40) следует, что ind ФК(ж) ^ Р - 1, т. е. -* = 0 только при wp(s) ^ p - 1. Согласно лемме 5, полиномиальный коэффициент во внутренней сумме сечения (17) не равен 0 по модулю p при условии wp(j\) + ... + wp(jp) = wp(s). Это возможно только при j\ = 0, j2 = 1, ..., jp = 1. Тогда в двойной сумме в (17) остаются только слагаемые вида s!-* . Пользуясь тем, что для всех t G {2,...,n - 1} и j G {0,... , m - 1} верно b0t)(i0 + j) = = b01)(i0+j) = E' (u0(i0 + j)) u01) (i0+j) = 0, так как E'(u0(i0 +j)) = 0 в силу условия (39) теоремы и u01)(i0 + j) = 0 по выбору i0, и полагая в сечении (17) последовательно t = n - 1, n - 2,..., 2, находим zs(i0 + j) для всех s G {1,..., n - 2} и j G {0,..., m - 1}. Знаки последовательности £(p, t) и двойной суммы однозначно вычисляются по из- (1) вестным знакам последовательностей u0 и u0 . Находим z0 = E(u0). Таким образом, узнаем значения ЛРП z над кольцом R в тактах i0, i0 + 1,..., i0 + m - 1. Этап IV. Теперь для каждого j G {0,... , m - 1} по известным знакам zt(i0 + j), t G {1,... , n - 1}, используя результат леммы 1 и условие (39), находим знаки последовательностей ut(i0 + j), t G {1,..., n - 1}. Этап V. Начальный вектор (u(0),... , u(m - 1)) вычисляется по известному вектору (u(i0), u(i0 + 1),..., u(i0 + m - 1)) с использованием закона рекурсии. ■ Заметим, что условие u01)(i0 + j) = 0 для всех j G {0,... ,m - 1}, введённое на этапе II алгоритма, можно ослабить: для восстановления начального вектора ЛРП u достаточно найти знаки u(i) в тактах i1,...,im, таких, что система вычетов по модулю F(x) многочленов жп,.. .,xim линейно независима над R. Поэтому в последовательности u^ достаточно найти m ненулевых значений uo-)(ij), j = 0,... ,m - 1, для которых система вычетов по модулю F(x) многочленов xn,.. .,xim линейно независима над R. При этом на этапе V начальный вектор («(0),... , u(m - 1)) вычисляется по известному вектору (u(i'), u(i2),... , u(im)) следующим образом: (u(0),..., u(m - 1)) = (u(i'), u(i2),..., u(im))A-1, где A = (S(Fe,... , S(F)ime); S(F) -сопровождающая матрица многочлена F(x); e = (e, 0,... 0). Матрица A обратима в указанных условиях. k Следствие 1. Пусть K = r(R), E(x) = Е esxs G R[x], u G LR(F) - ЛРП максиs=o мального периода, z = E(u) и выполнены следующие условия: 1) E'(x) не имеет корней в поле R; 2) существует такое s G {0,..., k - 1}, что (s + 1, qm - 1) = 1 и es+1 = 0. Тогда по последовательности zn-1 = yk ((E(«)) однозначно восстанавливается начальный отрезок «(0),..., u(m - 1). Следствие 2. Пусть R = Zpn, K - произвольное координатное множество коль-k ца R, E(x) = Е esxs G R[x], u G (F) - ЛРП максимального периода, z = E(u) и s=o выполнены следующие условия: 1) E'(x) не имеет корней в поле R; 2) существует такое s G {0,..., k - 1}, что (s + 1, qm - 1) = 1 и es+1 = 0. Тогда по последовательности zn-1 = yk ((E(u)) однозначно восстанавливается начальный отрезок u(0),..., u(m - 1). Отметим, что при дополнительных требованиях ограничение (39) на E'(x) в условиях теоремы 2 можно ослабить. Для любого i ^ 0 знак производной последовательности можно представить в виде uoi)(i) = tr(f Ф(1)(ш)^) = tr(£wV), где d G {0,... ,т - 1}. Найдём такие d G{0,... ,т - 1}, при которых wd G R. Очевидно, что это включение выполняется только при условии (qm - 1) | d(q - 1). Этому соотношению удовлетворяют только числа вида d = y(1 + +q + ... + qm-i), y G {1,... , q - 1}. Для таких d можно воспользоваться свойством линейности функции след и представить рекурренту uo') в виде uo') = cuo, где c - некоторая константа из R. Таким образом, верно следующее следствие. Следствие 3. Пусть в условиях теоремы 2 для многочлена максимального периода F(x) G R[x] определено число d G {0,..., т - 1}, такое, что Ф(1)(x) = xd (mod F(x)), и выполнены следующие условия: 1) существует такое r G R, что E'(f) = 0; 2) d представляется в виде d = y(1 + q + ... + qm-i), y G {1,... , q - 1}; 3) ind Фк (x) ^ p - 1; 4) существует такое s G {0,..., k - 1}, что (s + 1, qm - 1) = 1 и es+1 = 0. Тогда по последовательности zn-1 = yk -(E(u)) однозначно восстанавливается начальный отрезок u(0),..., u(m - 1). Автор выражает благодарность Д. Н. Былкову за помощь в написании статьи и уточнении некоторых результатов.

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

ЛРП максимального периода, полиномиальное усложнение, старшая координатная последовательность, восстановление начального вектора, LRS of maximal period, complicated polynomial, senior coordinate sequence, recovery of initial vector

Авторы

ФИООрганизацияДополнительноE-mail
Серебряков Евгений МихайловичЦентр специальных разработок, г. Москва, Россияryback_casey@mail.ru
Всего: 1

Ссылки

Кузьмин А. С., Маршалко Г. Б., Нечаев А. А. Восстановление линейной рекурренты над примарным кольцом вычетов по её усложнению // Математические вопросы криптографии. 2010. Т.1. №2. С. 31-56.
Былков Д. Н. Класс усложнений линейных рекуррент над кольцом Галуа, не приводящий к потере информации // Проблемы передачи информации. 2010. Т. 46. №3. С. 51-59.
Tian T. and Wen-Feng Q. Injectivity of compressing map on primitive sequences over Z/(pe) // IEEE Trans. Inform. Theory. 2007. V. 53. No. 8. P. 2960-2966.
Xuan-Yong Z. and Wen-Feng Q. Uniqueness of the distribution of zeros of primitive level sequences over Z/(pe) // Finite Fields Their Appl. 2005. V. 11. No. 1. P. 30-44.
Xuan-Yong Z. and Wen-Feng Q. Compression mappings on primitive sequences over Z/ (pe) // IEEE Trans. Inform. Theory. 2004. V. 50. No. 10. P. 2442-2448.
Xuan-Yong Z. and Wen-Feng Q. Further result of compressing maps on primitive sequences modulo odd prime powers // IEEE Trans. Inform. Theory. 2007. V53. No. 8. P. 2985-2990.
Нечаев А. А. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 4. №1. С. 123-139.
Кузьмин А. С., Нечаев А. А. Линейные рекуррентные последовательности над кольцами Галуа // Алгебра и логика. 1995. Т.3. №2. С. 169-189.
Нечаев А. А. Цикловые типы линейных подстановок над конечными коммутативными локальными кольцами // Математич. сб. 1993. Т. 184. №3. С. 21-56.
Кузьмин А. С., Нечаев А. А. Восстановление линейной рекуррентной последовательности над кольцом Галуа по её старшей координатной последовательности // Дискретная математика. 2011. Т.23. №2. С.3-31.
Кузьмин А. С., Куракин В. Л., Нечаев А. А. Псевдослучайные и полилинейные последовательности // Труды по дискретной математике. 1997. Т. 1. С. 139-202.
Куракин В. Л. Функция переноса в первый разряд в кольце Галуа // Дискретная математика. 2012. Т. 24. №2. С. 21-36.
Куракин В. Л. Представления над кольцом Zpn линейной рекуррентной последовательности максимального периода над полем GF(p) // Дискретная математика. 1992. Т. 4. №4. С. 96-116.
Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. Т. 2. М.: Гелиос, 2003.
 Восстановление полиномиально усложнённой линейной рекурренты максимального периода над кольцом Галуа по старшей координатной последовательности | ПДМ. 2014. № 2(24).

Восстановление полиномиально усложнённой линейной рекурренты максимального периода над кольцом Галуа по старшей координатной последовательности | ПДМ. 2014. № 2(24).