Линейная сложность обобщенных циклотомических последовательностей с периодом 2mpn

Тип работы:
Реферат
Предмет:
Физико-математические науки


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

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

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

УДК 519. 7
ЛИНЕЙНАЯ СЛОЖНОСТЬ ОБОБЩЁННЫХ ЦИКЛОТОМИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ПЕРИОДОМ 2mpn
В. А. Едемский, О. В. Антонова
Пусть X =? {0,1} -последовательность с периодом N = 2mpn, где p —
нечётное простое число, а m, n — натуральные числа. Её минимальный многочлен m (t) и линейную сложность L над полем GF (2) можно определить по следующим формулам:
m (t) = (tN — 1)/ ((tpn — 1)2m, S (i)), L = N — deg ((tpn — 1)2m, S (i)) ,
где S (t) — производящая функция цикла последовательности. Следовательно, если, а — примитивный корень степени pn из единицы в расширении поля GF (2), то для вычисления минимального многочлена и линейной сложности последовательности X достаточно найти корни многочлена S (t) в множестве {av: v = 0,1,…, pn — 1} и определить их кратность. Метод вычисления значений S (av) для обобщённых циклотомических последовательностей с периодом pn предложен в [1, 2], здесь обобщим его на последовательности с периодом 2mpn.
Пусть Hk = {ek+td (mod pn): t = 1,…, pn-1(p — 1)/d}, k = 0,1,…, d — 1 -циклотомические классы порядка d по модулю pn, где в — первообразный корень по модулю pn, а d — делитель p — 1, d ^ 2. Справедливо разбиение
п-1d-1
Zpn = ^ (JpjHk U{0}. j=0 k=0
Кольцо классов вычетов Zn изоморфно прямому произведению Z2m ®Zpn относительно
/ n-1
изоморфизма & lt-^(a) = (a mod 2m, a mod pn). Пусть Hlk = ^ 1 {1} 0 U Pj Hk для
V j=0)
I = 0,1,…, 2m — 1- k = 0,1,…, d — 1, тогда Hlk и множество {0,pn,…, (2m — 1) pn} образуют разбиение Zn.
Рассмотрим последовательность X, определяемую следующим образом:
= J 1, если i mod N? C,
Xi — 1 П (1)
0 иначе.
2m-1
Здесь C = U (J Hi, k U {0, 2pn,…, 2m-1pn}- /?, I = 0,1,…, 2m — 1 -подмножества l=0 ke/
индексов, элементы которых могут принимать значения от 0 до d — 1.
Пусть Sd (x) = (Sd (x), Sd (x6),…, Sd (x^-1 Л, R (x) = sd (x0k) и Q (x) = ^ Sd (x0fc),
V '- ke/ keJ
где Sd (t) = tu modp, а I, J — множества, состоящие из номеров k, входящих нечётное
«еЯо
число раз в подмножества /?, I = 0,1,…, 2m — 1, с чётными и нечётными номерами соответственно. Обозначим координаты вектор-функций R (x) и Q (x) при x = арП через r, q для i = 0,1,…, d — 1. Пусть? =1 для m =1 и? = 0 при m & gt- 1.
Теорема 1. Если v? pf Hj, f = 0,1,…, n — 1, j = 0,1,…, d — 1, то av — корень многочлена S (t) тогда и только тогда, когда r j + qj = (111 + |J |)f (p — 1)/d+$, и корень av многочлена S (t) кратный тогда и только тогда, когда rj = |1 |f (p — 1)/d + $.
Теорема 1 показывает, что известные значения R (x), Q (x), а фактически Sd (x), позволяют оценить линейную сложность последовательности X. Метод вычисления значений Sd (x) предложен в [1], следовательно, теорема 1 определяет метод анализа линейной сложности последовательностей с периодом 2mpn, сформированных по правилу (1).
Воспользовавшись теоремой 1, несложно получить следующие утверждения.
Лемма 1. Если d = 2 и /0 = 11 = {0}, то для последовательности X, сформированной по правилу (1) при N = 2pn, линейная сложность L = 2pn, а её минимальный многочлен m (t) = - 1.
Лемма 2. Если d = 4 и /0 = {0,1}, то для линейной сложности последовательности X, сформированной по правилу (1) при N = 2pn, справедливо:
1) L = 2pn, если 11 = {0,1}, или 11 = {0, 2} и ^= 1, или 11 = {0, 3} и ^= 1,
(2 (2
где -символ Лежандра, а -символ 4-степенного вычета-
2) L = (3pn + 1)/2, если 11 = {0, 3} и = 1, = 1-
3) L = (5pn + 1)/4, если =1 и 11 = {0, 2} или 11 = {0, 3}.
Аналогично можно получить следующие оценки линейной сложности последовательностей.
Лемма 3. Если d =2 и последовательность X с периодом 4pn определена правилом (1) при /0 = 11 = /2 = {0}, /3 = {1}, то L ^ 4pn — 4.
Лемма 4. Если d = 4 и последовательность X с периодом 8pn определена правилом (1) при /0 = /1 = /2 = /5 = {0}, /3 = {1}, /4 = /6 = {2} и /7 = {3}, то L ^ 8pn — 8,
если = 1, и L ^ 4pn — 8, если = 1.
Таким образом, предложен метод анализа линейной сложности последовательностей с периодом 2mpn, построенных на основе обобщённых циклотомических классов. Метод позволяет как явно рассчитать линейную сложность и минимальный многочлен рассматриваемых последовательностей, так и оценить её, а также определить характеристики последовательностей, обладающих заведомо высокой линейной сложностью. Подробное изложение представленных результатов можно найти в [3].
ЛИТЕРАТУРА
1. Едемский В. А. О линейной сложности двоичных последовательностей на основе классов биквадратичных и шестеричных вычетов // Дискретная математика. 2010. Т. 22. № 1.
С. 74−82.
2. Edemskiy V. А. About computation of the linear complexity of generalized cyclotomic sequences with period pn+1 // Designs, Codes and Cryptography. 2011. V. 61. No. 3. P. 251−260.
3. Едемский В. А., Антонова О. В. Линейная сложность обобщённых циклотомических последовательностей с периодом 2mpn // Прикладная дискретная математика. 2012. № 3 (в печати).

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