Linear complexity of generalized cyclotomic sequences with period 2p.pdf Пусть X = { x i } , x i . {0,1} -последовательность c периодом N = 2mpn, где p -нечётное простое число, а m, n - натуральные числа. Её минимальный многочлен m(t)и линейную сложность L над полем GF(2) можно определить по следующим фор-мулам:m(t) = (tN - 1)/ ((tpn - 1)2m, S(t)) , L = N - deg ( ( ^ - 1)2m, S(t)) ,где S(t) - производящая функция цикла последовательности. Следовательно, если a -примитивный корень степени pn из единицы в расширении поля GF(2), то для вычис-ления минимального многочлена и линейной сложности последовательности X доста-точно найти корни многочлена S(t) в множестве { a v : v = 0 , 1 , . . . ,pn - 1} и определитьих кратность. Метод вычисления значений S(av ) для обобщённых циклотомическихпоследовательностей с периодом pn предложен в [1, 2], здесь обобщим его на последо-вательности с периодом 2mpn.Пусть Hk = {ek+td (mod pn) : t = 1 , . . . , p n - 1 ( p - 1)/d}, k = 0 , 1 , . . . , d - 1 - циклото-мические классы порядка d по модулю pn, где в - первообразный корень по модулю pn,а d - делитель p - 1, d ^ 2. Справедливо разбиениеn-1d-1ZpUnp n =- и I J p j H k u { 0 } .j = 0 k=0Кольцо классов вычетов ZN изоморфно прямому произведению Z2m ®Z pn относительно/ n-1 \изоморфизма 1.Теорема 1. Если v . pf Hj, f = 0 , 1 , . . . , n - 1, j = 0 , 1 , . . . , d - 1, то av - кореньмногочлена S(t) тогда и только тогда, когда rj + qj = (111 +1J|)f (p - 1)/d+6, и корень avмногочлена S(t) кратный тогда и только тогда, когда rj = |I|f (p - 1)/d + 6.Теорема 1 показывает, что известные значения R(x), Q(x), а фактически Sd(x),позволяют оценить линейную сложность последовательности X. Метод вычислениязначений Sd(x) предложен в [1], следовательно, теорема 1 определяет метод анали-за линейной сложности последовательностей с периодом 2mpn, сформированных поправилу (1).Воспользовавшись теоремой 1, несложно получить следующие утверждения.Лемма 1. Если d = 2 и /0 = Ii = {0}, то для последовательности X, сформиро-ванной по правилу (1) при N = 2pn, линейная сложность L = 2pn, а её минимальныймногочлен m(t) = t2p" - 1.Лемма 2. Если d = 4 и /0 = {0,1}, то для линейной сложности последовательно-сти X, сформированной по правилу (1) при N = 2pn, справедливо:1) L = 2pn, если /1 = {0,1}, или /1 = {0, 2} и ^= 1, или /1 = {0, 3} и ^^ = 1,( 2 А (2 А 4 „где -символ Лежандра, а -символ 4-степенного вычета;2) L = (3pn + 1)/2, если /1 = {0, 3} и (^j = 1, ^ =1;3) L = (5pn + 1)/4, если =1 и /1 = {0, 2} или /1 = {0, 3}.Аналогично можно получить следующие оценки линейной сложности последова-тельностей.Лемма 3. Если d =2 и последовательность X с периодом 4pn определена прави-лом (1) при / 0 = / 1 = / 2 = {0}, / 3 = {1}, то L ^ 4pn - 4.Лемма 4. Если d = 4 и последовательность X с периодом 8pn определена прави-лом (1) при / о = / 1 = / 2 = / 5 = {0}, / 3 = {1}, / 4 = / б = {2} и / 7 = {3}, то L ^ 8pn - 8,если = 1, и L ^ 4pn - 8, если = 1.Таким образом, предложен метод анализа линейной сложности последовательно-стей с периодом 2mpn, построенных на основе обобщённых циклотомических классов.Метод позволяет как явно рассчитать линейную сложность и минимальный многочленрассматриваемых последовательностей, так и оценить её, а также определить характе-ристики последовательностей, обладающих заведомо высокой линейной сложностью.Подробное изложение представленных результатов можно найти в [3].

Скачать электронную версию публикации