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

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


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

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

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

2012 Теоретические основы прикладной дискретной математики № 3(17)
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
УДК 519. 7
ЛИНЕЙНАЯ СЛОЖНОСТЬ ОБОБЩЁННЫХ ЦИКЛОТОМИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ПЕРИОДОМ 2mpn
В. А. Едемский, О. В. Антонова Новгородский государственный университет, г. Великий Новгород, Россия E-mail: Vladimir. Edemsky@novsu. ru
Предлагается метод анализа линейной сложности обобщённых циклотомических последовательностей с периодом 2mpn, позволяющий выделять последовательности с высокой линейной сложностью. Вычисляется линейная сложность ряда последовательностей на основе классов квадратичных и биквадратичных вычетов.
Ключевые слова: обобщённые циклотомические последовательности, линейная сложность.
Введение
Линейная сложность бинарной последовательности является важным показателем её качества и определяется как длина самого короткого линейного регистра сдвига с обратной связью, который может воссоздать последовательность, т. е. если X = {Xi: i = 0,1,…} -последовательность с периодом N над полем GF (2), то её линейная сложность определяется как наименьшее натуральное L, для которого существуют константы c1,…, cL G GF (2), такие, что xi = CiXi-i + c2xi-2 + … + cLxi-L для всех i, L ^ i & lt- N [1]. Последовательности, обладающие высокой линейной сложностью, важны для криптографических приложений. Известны алгоритмы определения линейной сложности последовательности, например алгоритм Берлекэмпа — Месси [1]. В то же время для ряда периодических последовательностей, сформированных на основе классов степенных вычетов, линейная сложность определяется видом периода последовательности [2].
Построение последовательностей на основе классов степенных вычетов (циклотомических классов) по модулю N является одним из широко применяемых методов выработки последовательностей. Такие последовательности называются обобщёнными циклотомическими, если N составное [2]. В настоящей работе предлагается метод анализа линейной сложности ряда обобщённых циклотомических последовательностей с периодом N = 2mpn, где p — нечётное простое число, а m, n — натуральные числа. Вычисляется линейная сложность последовательностей на основе классов квадратичных и биквадратичных вычетов. Приведённые примеры показывают, что разработанный метод позволяет выделять последовательности с высокой линейной сложностью. Ранее линейная сложность отдельных последовательностей на основе классов квадратичных вычетов с периодом 2pn и биквадратичных вычетов с периодом 2p исследовалась в [3−6].
1. Основные определения
Пусть p — нечётное простое число и d — натуральный делитель p — 1, d ^ 2. Хорошо известно, что всегда существует первообразный корень 9 по модулю pn [7]. Обозначим через H0 = {9td mod pn: t = 0,…, pn-1(p — 1)/d — 1} класс вычетов степени d по модулю pn. Если A — подмножество Zpn, то через tA будем обозначать множество tA = {ta mod pn: a G A}, где t G Z.
Пусть = 9k Ho для k = 0,1,…, d — 1. Классы вычетов Hk образуют разбиение множества обратимых элементов кольца Zpn и являются обобщёнными циклотомическими классами.
n- 1
Положим Ck = U p7 Hk, тогда j=o
d-1
Zpn = U Ck и{0}. (1)
k=0
Кольцо классов вычетов Zn, N = 2mpn, изоморфно прямому произведению Z2m 0 Zpn относительно изоморфизма & lt-^(a) = (a mod2m, a mod pn) [7]. Пусть
Hz, k =-1 ({1} 0 Ck) для I = 0,1,…, 2m — 1, k = 0,1,…, d — 1, тогда, согласно (1), справедливо разбиение
2m -1 d-1
Zn = u U Hi, ku{0,pn,… ,(2m — 1) pn}. l=0 k=0
Цель работы заключается в исследовании линейной сложности характеристических последовательностей различных объединений классов вычетов Hi, k. Для каждого I = 0,1,…, 2m — 1 зададим -подмножества индексов, элементы которых могут
принимать значения от 0 до d — 1, то есть /^ С {0,1,…, d — 1}. Введем множество 2m -1
C = U У Hj, k U {0, 2pn,…, (2m — 2) pn} и рассмотрим последовательность X, опре-l=0 keli
деляемую следующим образом:
= J 1, если i mod N G C, (2)
Xi [0 иначе. (2)
Так как, согласно определению, xi = xi mod n, то N является периодом последовательности X.
Далее рассмотрим метод вычисления линейной сложности последовательностей, определяемых формулой (2), и проиллюстрируем его на примерах.
2. Метод анализа линейной сложности последовательностей
с периодом 2mpn
Хорошо известно (см., например, [1]), что если S (t) -производящая функция цикла последовательности, то есть S (t) = x0 + x11 + … + xN-1tN-1, S (t) G GF (2)[t], то её минимальный многочлен m (t) и линейную сложность L можно определить по следующим формулам:
m (t) = (tN — 1)/НОД (^ - 1, S (t)), L = N — deg[НОД (tN — 1, S (t))]. (3)
В нашем случае, в кольце GF (2)[t], справедливо разложение t2mрП — 1 = (tpn — 1)2m,
то есть
L = N — deg[H (^ ((f — 1)2″, S (t))]. (4)
Обозначим через, а примитивный корень степени рп из единицы в расширении поля СЕ (2) — тогда, согласно формулам (3) и (4), для вычисления минимального многочлена и линейной сложности последовательности X достаточно найти корни многочлена ?(і) в множестве |а^: V = 0,1,…, рп — 1} и определить их кратность.
Согласно определению последовательности, имеем
2m -1 2m-1−1
S (а*)= E E E a*u + E ajv2pn. (5)
1=0 hell ueHi, k j=0
Лемма 1. Для любых l = 0,1,…, 2m — 1 и k = 0,1,…, d — 1 справедливо равенство E = E aw. ueHik weCk
Доказательство. По определению, а имеем, что au = au mod pn, а так как {u mod pn: u G H1h} = Ch, то это и доказывает лемму 1. ¦
Из леммы 1 и формулы (5) видно, что если один и тот же индекс k принадлежит
двум разным подмножествам и //, то соответствующий вклад классов вычетов Hs, h и Hf, h при вычислении значений S (а*) будет нулевой. Введём два новых подмножества
2m — 1 — 1
индексов I = {k: k = 0,1,…, d — 1 и Е |{k} П /2j-1 — нечётное число} и J = {k:
j=0
2m-1−1
k = 0,1,…, d — 1 и E |{k} П I2j+1| - нечётное число}.
j=0
Далее, метод вычисления значений производящей функции последовательности с периодом pn, то есть сумм Е aw, предложен в [8]. Введём дополнительно следу-
weCi
ющие обозначения. Пусть в = ap -первообразный корень степени p из единицы
в расширении поля GF (2) и Sd (t) = Е tu modp, то есть Sd (t) -многочлен, соответ-
«еНо
ствующий классу вычетов степени d по модулю p. Тогда, согласно [8], если v G pf Hj,
то E auv = Sd (e0J+k) + f (p — 1)/d.
«eCk
Отсюда, воспользовавшись леммой 1, формулой (5) и определением множеств I, J, получаем следующее утверждение (если I или J — пустое множество, то соответствующую сумму считаем равной нулю).
Лемма 2. Если v G pf Hj для f = 0,1,…, n — 1 и j = 0,1,…, d — 1, то
S (a*) =? Sd (e& quot-'+k) + E) + (|11 + | J|)f (p — 1)/d + (6)
ke1 heJ
где
^ = f 1, если m =1,
[ 0, если m & gt- 1.
Таким образом, задача вычисления значений S (a*) свелась к расчёту значений многочлена Sd (t). Исследуем вопрос о кратных корнях многочлена S (t).
Лемма 3. Если v G pf Hj для f = 0,1,…, n — 1 и j = 0,1,…, d — 1, то a* - кратный корень многочлена S (t) тогда и только тогда, когда
ESd (e& quot-'+k) = f|1 |(p — 1)/d +? Sd (e& quot-'+k) = f|J|(p — 1)/d.
ke1 heJ
Доказательство. Исследуем производную многочлена S (t). Если u Є Hj, k, то для l = О (mod 2) всегда u = О (mod 2), следовательно, в кольце GF (2)[t]
'- О, если l — чётное,
^ t / = Е tu-1, если l — нечётное.
KueHi, k J ^ иЄН^, —
Таким образом, S'-(t) имеем
2m-1−1
Е Е Е tu-1. Тогда по формуле (б) и лемме І
l=0 fc€/2J+1 u€H2i+1,fc
2m -1 / ч
S'-(a& quot-) = a-& quot- E E) + f (p — 1)/d)
7-П teL, V /
l=0 fc€/2i+1
fcGJ
a-M E Sd (fl& quot-'-+k) + ЕЕ,& quot-'--11 121+1 If (p — 1)/d) ,
или
S'- (a& quot-)
a
E Sd (e *J+fc) + IJ If (p — 1)/d).
fceJ
Таким образом, если а® — кратный корень многочлена Б (?), то Б (а®) = Б (а®) = 0 и утверждение леммы 3 следует из формул (7) и (8). Наоборот, если выполняется условие леммы 3, то по (7) и (8) имеем, что Б (а®) = Б (а®) = 0, то есть а® — кратный корень многочлена Б (?). ¦
Леммы 2 и 3 показывают, что для определения корней многочлена Б (?) в множестве {а®: V = 0,1,…, N — 1} и выделения среди них кратных достаточно знать числа Б^в^), I = 0,1,…, д — 1. При этом если V, и € р^ Н, то Б (а®) = Б (аи) и Б& quot- (а®) = Б& quot- (аи) для любых значений f = 0,1,…, п — 1, ] = 0,1,…, д — 1.
Пусть 8& lt-*(х) = (б^(х), Бй (х6),…, Бй (х^-1)), К (х) = Е 8^(ж^) и д (ж) = Е 8^(ж0к).
Обозначим координаты вектор-функций К (х) и Q (x) при х = в через г*,% для г = = 0,1,…, д — 1.
Непосредственно из лемм 2 и 3 получаем следующее утверждение.
Теорема 1. Если V € р^Я, f = 0,1,…, п — 1, ] = 0,1,…, д — 1, то а® — корень многочлена Б (?) тогда и только тогда, когда г, + д, = (111 +131) f (р — 1) /д+8, и корень а® многочлена Б (?) кратный тогда и только тогда, когда г, = |1 |f (р — 1)/д + 8.
Таким образом, теорема 1 и формулы (3), (4) показывают, что известные значения к (в), Q (в), а фактически Э^(в), позволяют оценить линейную сложность последовательности X. Метод вычисления значений 8^(х) предложен в [9] и развит в [10], там же найдены значения 8^(в) при д =2, 4, 6,8. Следовательно, теорема 1 и результаты, представленные в [10], определяют метод анализа линейной сложности последовательностей с периодом 2трп, сформированных по правилу (2). Причём если т = 1, то можно явно рассчитать линейную сложность любой последовательности при д = 2, 3, 4, 6, 8, а если т & gt- 1 или д отлично от перечисленных, то можно подобрать такое правило построения последовательностей, при котором они заведомо будут обладать высокой линейной сложностью. Более того, вычисленные значения Б (а®), V = 0,1,…, рп — 1, позволяют рассчитать минимальный многочлен последовательности по формуле (3).
Далее проиллюстрируем предложенный метод на примерах.
3. Линейная сложность последовательностей с периодом 2pn
Исследуем линейную сложность ряда обобщённых циклотомических последовательностей с периодом 2pn, ограничившись при этом вариантом, когда число нулей и единиц на периоде последовательности одинаково, то есть последовательности являются сбалансированными. В этом случае S (1) = pn, то есть S (1) mod 2 = 1.
Не нарушая общности, всегда можно считать, что 0 Е /0 и ноль является общим элементом пересечения множеств /о, /1, если оно непусто. Рассмотрим возможные варианты для множеств /0,/1 при d =2, 4. Для m =1 всегда / = /0, J = /1, по определению множеств /, J, и 8 =1.
Пусть d =2, тогда, как это показано в [3] (см. также [10]), справедливо соотношение
S (в) = / (1,0), если p = ±1 (mod 8), (8)
d (e) (^,^ + 1), если p = ±3 (mod 8). ()
Здесь ^ - корень уравнения x2 + x + 1 = 0 в расширении поля GF (2).
Лемма 4. Если /0 = /1 = {0}, то для последовательности X, сформированной по правилу (2), линейная сложность L = 2pn, а её минимальный многочлен m (t) = t2pn — 1.
Доказательство. По условию / = {0}, J = {0}, тогда R (e) = QC$) = S2(e). Следовательно, R (5) + QC$) = (0, 0) и rj + qj = 0 для любого j = 0,1. А так как (|/1 + | J|)(p — 1)/2 — чётное число и 8 = 1, то по теореме 1 S (av) = 0 при всех значениях v = 0,1,…, 2pn — 1. Утверждение леммы 4 следует из формул (3) и (4). ¦
Лемма 5. Если /0 = {0},/1 = {1}, то для последовательности X, сформированной по правилу (2), линейная сложность
г _, pn + 1, если p = ±3 (mod 8),
L
(tpn — 1)(t-1), если p = ±3 (mod 8),
(t — 1)2 П (t — ¦), если p = 1 (mod 8),

(t — 1)2 n (t —), если p = - 1 (mod 8),

-1H n mod 2.
(pn + 3)/2, если p = ±1 (mod 8),
а её минимальный многочлен
m (t)
где D = H U pH U … U pn
Доказательство. В условиях леммы 5 R (5) = S2(e), а Q (5) = S2(в6), следовательно, R (e) + Q (e) = (1,1) и rj + qj = 1 для j = 0,1. А так как (|/1 + | J|)(p — 1)/2 — четное число и 8 = 1, то по теореме 1 S (av) = 0 при всех значениях v Е C0 U C1, то есть при v = 1,…, pn — 1.
Далее, если v Е pf Hj и — корень многочлена S (x), то по теореме 1 он кратный корень, если rj = f (p — 1)/2 + 1.
Таким образом, если p = ±3 (mod 8), то по формуле (9) для v = 1,…, pn — 1 не является кратным корнем многочлена S (t) и L = 2pn — (pn — 1) = pn + 1, а m (t) = = (t2pn — 1)/((tpn — 1)(t — 1)) = (tpn — 1)(t — 1).
Пусть p = ±1 (mod 8), тогда R (5) = (1, 0) по формуле (9). Если p = 1 (mod 8), то f (p — 1)/2 + 8 = 1 (mod 2), то есть — кратный корень многочлена S (t) для любого v Е C0. Если же p = - 1 (mod 8), то соответственно получаем, что — кратный корень многочлена S (t), когда rj = f + 1, то есть при v Е H0 U pH1 U … U pn-1H (n-1) mod 2.
В обоих случаях L = 2pn — (pn — 1) — (pn -1)/2 = (pn+3)/2, но минимальные многочлены последовательностей, вычисленные по формуле (З), различаются. ¦
В частном случае, когда 2 Е H0, утверждения лемм 4 и 5 были получены в [5, 6] другим способом.
Пусть d = 4, тогда справедливо разложение p = x2 + 4y2, где x = 1 (mod 4), x и y — целые числа [7]. Обозначим через (-) символ Лежандра, а через (-) -символ
pj pj4
4-степенного вычета [7], I —) =1 тогда и только тогда, когда сравнение z4 = - (mod p)
p4
разрешимо в целых числах. Согласно [9, 10], имеем
1) если = 1, то S4(e) = (1,1, 0,1) для x = 5 (mod 8) и S4(e) = (1, 0, 0, 0) для
x = 1 (mod 8) —
2) если =1 и = 1, то S4(e) = (^, 0,^ + 1,0) для x = 5 (mod 8) и
S4(e) = (^, 1,^ + 1,1) для x = 1 (mod 8), где ^ - корень уравнения t2 + t +1 = 0 в расширении поля GF (2) —
3) если (p) = 1 то S4(в) = (Z, Z2, Z4,Z8) или S4(в) = (z, z8, z4,с2), где С удовлетворяет условию Z8 + Z4 + Z2 + Z + 1 = 0.
Воспользуемся этими соотношениями для расчёта линейной сложности последовательностей, сформированных на основе классов биквадратичных вычетов.
Лемма 6. Если /0 = {0,1}, то для линейной сложности последовательности X, сформированной по правилу (2), справедливо следующее:
1) L = 2pn, если /1 = {0,1}, или /1 = {0, 2} и ^= 1, или /1 = {0, 3} и = 1-
2) L = (3pn + 1)/2, если /1 = {0, 3} и = 1, = 1-
3) L = (5pn + 1)/4, если =1 и /1 = {0, 2} или /1 = {0, 3}.
Доказательство. Докажем лемму только для /1 = {0, 3}, другие два варианта исследуются аналогично. Так как по условию | /| = | J| = 2, то, согласно теореме 1, S (av) = 0 при всех значениях v Е Ck тогда и только тогда, когда r^ + = 1 и при
этом — кратный корень для любого v Е Ck тогда и только тогда, когда r^ = 1. Если
/0 = {0,1} и /1 = {0,3}, то R (e) = S4 (в) + S4 (в ^), а R (e) + Q (e) = S4C56) + S4(e& quot-3).
Из приведённых выше соотношений для S4(e) получаем, что r^ + q^ = 1 для k = = 0,1, 2, 3 при (^ = 1, следовательно, L = 2pn. Когда же (-) = 1, то R (e) + Q (^) =
p/ w
= (0,1, 0,1), кроме этого, rk = 1, k = 0,1, 2, 3, при I — I = 1, то есть в этом варианте
p/4
нет кратных корней и L = 2pn — 2|C0| = (3pn + 1)/2. В то же время если I —) = 1, то
Vp/4
R (e) = (0,1,1, 0) ((1, 0, 0,1)), тогда являются кратными корнями при v Е C1(C0) и L = 2pn — 3|C0| = (5pn + 3)/4. ¦
В частном случае, для n = 1 и /0 = {0,1}, /1 = {0, 2}, линейная сложность последовательности X была исследована в [4].
Лемма 7. Если /0 = {0, 2}, Д = {0, 3}, то для линейной сложности последовательности X, сформированной по правилу (2), справедливы следующие равенства:
1) Ь = 2рп, если (2) =1-
Р/4
2) Ь = рп + 1, если (2) = 1.
Р/4
Лемма 7 доказывается подобно лемме 6. Все другие варианты для /0,/1 сводятся к уже рассмотренным.
4. Примеры оценки линейной сложности последовательностей
с периодом 2трп
Рассмотрим три примера оценки линейной сложности последовательности. В [10, 11] предложено несколько правил построения последовательностей с периодами 4р, 8р, обладающих хорошей периодической автокорреляционной функцией. Оценим линейную сложность этих последовательностей в общем случае. Предварительно отметим, что для всех рассматриваемых последовательностей единица является корнем многочлена Б (ж) при т & gt- 1 и её кратность не превосходит т.
Лемма 8. Если d =2 и последовательность X с периодом 4рп определена правилом (2) при /0 = /1 = /2 = {0}, /3 = {1}, то Ь ^ 4рп — 4.
Доказательство. Согласно условию леммы и определению множеств / и 3,
й-1
имеем / = 0, 3 = {0,1}, тогда г, + ^ = 1, ] = 0,1, так как сумма Е Б^(в6& quot-) = 1 [10],
г=0
то есть, по теореме 1, Б (а) = 1 для V = 1,…, рп — 1. Таким образом, утверждение леммы следует из формулы (4). И
Лемма 9. Если d = 4 и последовательность X с периодом 4рп определена правилом (2) при /0 = /1 = {0,1} и /2 = {0, 3},/3 = {1, 2} или /2 = {1, 2},/3 = {0, 3}, то Ь ^ 4рп — 4.
Лемма 9 доказывается аналогично лемме 8.
Лемма 10. Если d =4 и последовательность X с периодом 8рп определена правилом (2) при /0 = /1 = /2 = /5 = {0}, /3 = {1}, /4 = /6 = {2} и /7 = {3}, то Ь ^ 8рп — 8,
если = 1, и Ь ^ 4рп — 8, если = 1.
Доказательство. В условиях леммы Б (1) = 0 и / = 0, 3 = {1,3}, тогда К (в) = 0. Если (-) =1, то ^ =1, следовательно, по теореме 1 Б (а) = 0 для
Р/
V = 1,…, рп — 1. Если же = 1, то Q (в) = (0,1, 0,1) и по теореме 1 Б (а) = 0
для V Е С0 и С2, причём каждый корень является кратным. Применение формулы (4) завершает доказательство леммы 10. ¦
Заключение
Предложен метод анализа линейной сложности последовательностей с периодом 2трп, построенных на основе обобщённых циклотомических классов. Метод позволяет как явно рассчитать линейную сложность и минимальный многочлен рассматриваемых последовательностей, так и оценить её, а также определить характеристики последовательностей, обладающих заведомо высокой линейной сложностью. Вычисле-
на линейная сложность ряда последовательностей на основе классов квадратичных и биквадратичных вычетов.
ЛИТЕРАТУРА
1. ЛидлР., Нидеррайтер Г. Конечные поля. М.: Мир, 1988. 820 с.
2. Cusick T. W., Ding C., and Renvall A. Stream Ciphers and Number Theory. North-Holland Mathematical Library. V. 55. Amsterdam: Elsevier, 1998.
3. Ding C., Helleseth T., and Shan W. On the Linear Complexity of Legendre Sequences // IEEE Trans. Info Theory. 1998. V. IT-44. P. 1276−1278.
4. Ding C., Helleseth T., and Martinsen H. New families of binary sequences with optimal three-level autocorrelation // IEEE Trans. Info Theory. 2001. V. 47. P. 428−433.
5. Zhang J, Zhao C. -A., and Ma X. Linear complexity of generalized cyclotomic binary sequences of length 2pm //Appl. Algebra Eng. Commun. Comput. 2010. V. 21. No. 2. P. 93−108.
6. Zhang J., Zhao C. -A., and Ma X. On the Linear Complexity of Generalized Cyclotomic Binary Sequences with Length 2p2 // IEICE Trans. Fundament. Electron., Commun. Comput. Sci. 2010. V. E93.A. Iss. 1. P. 302−308.
7. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987. 416 с.
8. 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.
9. Едемский В. А. О линейной сложности двоичных последовательностей на основе классов биквадратичных и шестеричных вычетов // Дискретная математика. 2010. Т. 22. № 1.
С. 74−82.
10. Едемский В. А, Гантмахер В. Е. Синтез двоичных и троичных последовательностей с заданными ограничениями на их характеристики. Великий Новгород: НовГУ, 2009. 189 с.
11. Zhang Y., LeiJ.G., and Zhang S. P. A new family of almost differences sets and some necessary conditions // IEEE Trans. Info. Theory. 2006. V. 52. P. 2052−2061.

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