О линейной сложности обобщенных циклотомических последовательностей Динга-Хеллесета

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


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

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

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

УДК 519. 7
О ЛИНЕЙНОЙ СЛОЖНОСТИ ОБОБЩЕННЫХ ЦИКЛОТОМИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДИНГА-ХЕЛЛЕСЕТА
В.А. Едемский
ON THE LINEAR COMPLEXITY OF DING-HELLESETH GENERALIZED CYCLOTOMIC SEQUENCES
V.A. Edemskii
Институт электронных и информационных систем НовГУ, Vladimir. Edemsky@novsu. ru
Определены достаточные условия существования обобщенных циклотомических последовательностей Динга-Хеллесета с высокой линейной сложностью. Предложен метод вычисления линейной сложности рассматриваемых последовательностей.
Ключевые слова: последовательности, линейная сложность, обобщенные циклотомические классы
We defined sufficient conditions for designing Ding-Helleseth sequences with high linear complexity for generalized cyclotomies. We also discuss the method of computing the linear complexity of Ding-Helleseth sequences in the general case. Keywords: sequences, linear complexity, generalized cyclotomic classes
Введение
Линейная сложность последовательности является ее важной характеристикой [1]. Она может быть определена как длина самого короткого линейного регистра сдвига с обратной связью, который способен генерировать последовательность. «Хорошие» последовательности должны иметь линейную сложность, большую половины периода [1].
Применение классических циклотомических классов и обобщенных циклотомических классов для построения последовательностей, которые называют, соответственно, классическими циклотомическими последовательности и обобщенными циклотомическими последовательностями, является важным методом построения последовательностей [2]. В [3]
С. Динг и Т. Хеллесет ввели новую обобщенную цик-лотомию второго порядка по модулю р^ - р*, которая включает в себя классическую как частный случай, и рассмотрели методы конструирования двоичных последовательностей. Свойства этих последовательностей изучались в ряде работ. В частности, линейная сложность последовательности второго порядка исследовалась в [4−12]. Кроме этого, линейная сложность ряда двоичных последовательностей, сформированных на основе обобщенных циклотоми-ческих классов высших порядков, была вычислена для отдельных модулей (р& quot-, рд) в [10, 13−15].
Целью данной работы является нахождение достаточных условий существования обобщенных цикло-
томических последовательностей Динга-Хеллисета с высокой линейной сложностью, а также разработка метода вычисления линейной сложности упомянутых последовательностей в общем случае.
1. Основные определения и обозначения
В этом разделе кратко напомним определение обобщенных циклотомических последовательностей из [3].
Пусть п = р'- ••• ре'-, где рр…, р (- попарно
различные нечетные простые числа, удовлетворяющие условию:
простых чисел, участвующих в разложении d. В силу (2) и (3) получаем, что
2и{0}= у п^и
d|n, d & gt-1 4
Пусть
C& gt- = U nk'-d) и q = U, dW
h, d)
0 VJ d 0
din, d& gt-1
d|n, d & gt-1
НОд (рe ~рг -1), pfipj -1)) = 2 для всех i Ф J
и e1,…, e — натуральные числа.
Пусть Zn — кольцо классов вычетов по модулю n. Согласно китайской теореме об остатках
Z = Z e х… х Z e (1)
относительно изоморфизма ф (х) = (x modрЦ,…^ modре'-).
Здесь и далее x mod n обозначает наименьшее целое неотрицательное число, что сравнимо с x по модулю n. Хорошо известно, что всегда существует примитивный корень g. по модулю рe, i = 0,1,…, t [1]. Пусть
D,
(Pe)={g 2J
= {g. | J e Z} - подгруппа Z e, порожденная
Тогда пара {C0, C1} образует разбиение Zn, т. е.
Z = C ^ C и C n C = 0.
n 0 1 0 1
Рассмотрим двоичную последовательность sш, определяемую следующим образом [3]:
sг = J тогда и только тогда, когда J mod n e C.
Последовательность sш называется обобщенной циклотомической последовательностью Динга-Хеллисета. Отметим, что чаще всего рассматривается случай, когда ad = (0,…, 0,1) [3].
2. Оценка линейной сложности обобщенных
циклотомических последовательностей
В этом разделе найдем достаточные условия существования обобщенных циклотомических последовательностей с высокой линейной сложностью.
Обозначим через g единственное решение следующего набора сравнений:
2 (pei) (pei) gi, и Dj г = gi D0, здесь умножение выполняется
в кольце Z
i = 1,2,…, t.
g = gi (mod p/), i = 1,2,…, t.
Zm (d)
a '- - нечетное число, то
k=1 k
gD (ad, d) = d Ц d)
для J = 0,1. Здесь действия выполняются в Zd.
Доказательство. Пусть d = р'-1 … р1& quot-, где
J1 Jm
ikak = 0 I I (a, n) = (z)t I (a, n) Jk e {1,2,…, t}, k = 1,2,…, m и целые числа lk удовлетворяют системе неравенств 1 & lt- lk & lt- e., k = 1,2,…, m.
k Jk
Пусть a = (ap…, at) — ненулевой вектор, принадлежащий (Z 2) t и
I0a, n)=) e (Z2)
k=1
По определению, положим [3]
Е («¦& quot-)= П р1) х… х Р'-'- 1 1 1 г1) е1 ^
ВМ= ф-1^Е (а'-п)), 1 = 0,1. Из определения следует, что
2* = ф, п) и д (а, п), ф, п) п д (а, п) = 0. п 0 1 '- 0 1
Очевидно, что существует элемент Ь е 2*, та-
По определению D (a& lt-i, d) и g, получаем, что
ф| gD
к, d'-)) =
Т-Г (р'-1) (р1& quot-)
П gJ-Dj*'-х… хg. DjJm& gt-,
Л. Л., ч -& quot-1. /1 J& quot- Jm
j) eI (ad, d)
(2)
где ф (х) = (x mod р1-,…, xmod рт) или
^ J1 Jm'-
ф№& quot- 71 = П # … х
h, d)) =
кой что D (a, n) = ?D0a, n). Тогда D0a, n) и D,(a& quot-"- назы-
^,(a, n) ¦^0
4(a, n)
(J1,-, Jm) eI0
ваются обобщенными циклотомическими классами 2-го порядка по отношению к a и n. Далее, считаем,
Тогда ^(J + 1) akd) = zm=ad) для
что если J & gt- 1, то D (a, n) совпадает с D (mod 2.
-)(a, n)
Г (ad, d)
(j1,…, Jm) eI0^, следовательно, (j1 +1,… jm +1)eI1
(ad, d)
Справедливо разбиение [3]:
n
(3)
2п{0}= и П2**
?|п, й & gt-1
Если d — натуральное число и d | п, d & gt- 1, то для каждого d зададим ненулевой вектор
ай = (а1(й),…, a^d)) е (22)т, где да — число различных
по условию леммы 1. Тогда из формулы (2) имеем D^l… хD^)e E^d, d).
Таким
образом, gD0ad, d) с D1(ad, d)
а так как их
(ad, d) = D (arf, d)
порядки равны, то gD0 '- = Л*. Утверждение gD^d, d) = л0ай, d) может быть доказано аналогично.
р

Пусть, а — примитивный корень & quot--й степени из единицы в расширении поля GF (2). Тогда для
^ ^ т да
линейной сложности Ь последовательности 5 имеем [1]:
Ь = п — {у ?(ау) = 0, V = 0,1,… ,"- -1}|, (4) где? (х) определяется как? (х) = ^х'-.
геС.
Для того чтобы исследовать значения ?(ау), введем вспомогательный полином. Пусть? а (х) = Ух'-, где, А — подмножество Тп. Тогда для
геЛ
любого v = 1,…, n-1 получаем, что
SC (av) + SC (av) = 0.
(5)
5 =
а- '- - нечетное число, то
к=1 к
для любого V = 1,2,…, п-1 справедливо:
?, №) =? , (ау).
ПЛЫ, '- Л '- & quot-П (а Л, '-Л '-
Доказательство. По лемме 1 g?)1(a'-'-, й) = ?& gt-0*'-, й)
V п п (ай, Л) п «(а*, Л)
в кольце ?., тогда -?Л, '- = --яи'-'- '- в кольце
'- й 1 й 0
2п и утверждение леммы 2 следует из определения
вспомогательного многочлена. Пусть
(1, если ?(1) = 0, [0, иначе,
а так как, по определению последовательности,? (1) = (п +1)/2, то
(1, если п = 3(mod4), [0, иначе.
Теорема 1. Предположим, что для любого целого числа й & gt- 1, й | п, сумма ^ш-1акй) — нечетное число, тогда для линейной сложности Ь последова-
да
тельности 5 справедливо неравенство: Ь & gt- (п +1)/2−5. Доказательство. По определению последова-
да 11
тельности 5 для всех V = 1,…, п -1 получаем:
? (ау)= V? , (ау)+1.
У '- пЛай, '-))
5 =
d |n, d & gt-1 d 1
Тогда по лемме 2
S (agv) = У S, (av)+1.
v '- Z-i nD'-d, d) v '-
din, d& gt-1 d 0
Следовательно, S (agv) = SC (av) +1, в силу (5) полу-
Co
чаем, что S (av) + S (agv) = 1 для всех v = 1,…, n-1. Таким образом, порядок множества
|{v | S (av) = 0, v = 1,2,…, n -1}|& lt- (n -1)/2. Из последнего неравенства по формуле (4) имеем L & gt- (n +1)/2 — 5, что и требовалось доказать.
Следствие. Если 2 = g (mod n) в условиях теоремы 1, то L = n — 5.
Действительно, в этом случае? (ау) +? 2(ау) = 1 и ?(ау) Ф 0 для всех у = 1,2,…, п -1.
Сделаем несколько замечаний к теореме 1. Когда, а л = (0,…, 0,1), т. е. в частном случае обобщенных цик-
лотомических последовательностей Динга-Хеллесета, условия теоремы 1 выполняются автоматически, поэтому для такого рода последовательностей приведенная в теореме 1 оценка линейной сложности всегда справедлива. Легко видеть, что это находится в согласии с уже известными результатами о линейной сложности последовательностей с периодами рп, рд [4−13]. Следует отметить, что не все последовательности, рассмотренные в [4−13], могут быть определены как 5да.
Далее, если НОДр 1(рг -1), ре--1(р. -1)) = г
для I Ф у, то, как и в [10, 13−15], для модуля р. г
можно определить обобщенные циклотомические
р)
классы Н1 '-, к = 0,1,…, г -1 порядка г. Если
=- Лр: <-)=и лж1 и^!. «при
а й = (0,…, 0,1) оценка линейной сложности из теоремы 1 будет справедлива и для обобщенных циклото-мических последовательностей, построенных на новых классах. Это можно показать путем замены элемента g на gг/2 в леммах 1 и 2, что согласуется с результатами [10, 13−15].
Таким образом, теорема 1 определяет достаточные условия существования обобщенных цикло-томических последовательностей с высокой линейной сложности для произвольного периода.
В следующем разделе обсудим метод вычисления линейной сложности обобщенных циклотомиче-ских последовательностей. В частности, покажем, что если среди векторов ай существует хотя бы один с четной суммой координат, то найдется такое п, для которого утверждение теоремы 1 не соответствует действительности.
3. Вычисление линейной сложности обобщенных
циклотомических последовательностей
Здесь подытожим метод вычисления линейной сложности обобщенных циклотомических последовательностей с период рд, предложенный в [16] (см. также [17]). По построению
(6)
S (av)= У S, V)+1.
V '- Z-I nD'-d, d) V '-
din, d& gt-1 d 1
Исследуем слагаемые последней суммы. Если й = р1 ••• р1& quot-, то существуют целые числа Ь., г = 1,…, ш, такие что [1]
, п п п
Ь-Г + … + Ь -?- = -Г,
1 I ш I Л
р 1 р Ш Ы
где каждое число Ь., г = 1,…, ш однозначно определяется по модулю р и Ь. Ф 0(тоё р.).
ъ. п/р)
Пусть Рк = а к к, к = 1,…, ш, тогда Рк —
1к «
примитивный корень рк -й степени из единицы в расширении поля GF (2) и
а = Р1 • …• в. Обобщая теорему 1 из [16], получаем следующее утверждение.
_ 11
тогда для
¦Л
у = 1,…, п -1 имеем:
Лемма 3. Если d = p1 ¦ ¦ ¦ p1& quot-
j1 jm
S
-DKc
,(«'-)=
(jr¦, ОеЧ
у, гj
(?W, d) 1
p JpL)
j1 P
… Sv
P d
('-1)
где Sp^(x)= У X.
j1 V,. Л
геГУ1 J
& amp-
Метод вычисления значений ?. 1к (зу) был
предложен в [8−10]. Таким образом, формула (6), лемма 3 и результаты из [10] позволяют вычислять
да
значения многочлена последовательности 5 и, следовательно, линейную сложность обобщенных цик-лотомических последовательностей. Для примера рассмотрим вариант, когда условия теоремы 1 не выполняются.
Пусть n = p1 p2
pp-
=(1,1):
тогда
(a, pp) T pp r1r2& gt-
?1 1 2
= {(0,1),(1,0)}. Далее, ?1
(a, p) (a, p) p1 1 p2 2
= ?/2
= {(1)}, так как, по определению, a =a =(1).
Если d = p1 p2, то P1 = a
bp?
= «ь2 и P2 = a1.
где
Ъ1 р1 + Ъ2 р2 = 1. Следовательно, а 1 = Р12, а 2 = Р21. Таким образом, по лемме 3 и формуле (6) для
п = р1 р2 и, а = (1,1) получаем, что
1 2 р1р2
S (av) = s0% ^(PP + s1p1)(pv)s0 p2)(P2) +
+ Si p1)(Pip2v) + Si p2)(P2p1v) + 1.
(p),
(7)
Свойства полиномов S, 1 (x), j, i = 0,1 были изучены в [10].
*
Лемма 4. Если v е Z, то
S (av)
= 0 если p1 = 3 (mod 4) и p2 = 3 (mod 4), 1 в ост. случаях.
. случаях.
*
Доказательство. Если у е 2п, тогда из формулы (7) получаем, что
Л p),
Л ^),
Р Кп
P^ AV
S (av) = S^ (Pv) + Sq (P?) + Sr^'-CP!2) + ^'-(p1'-). (8)
Рассмотрим два случая.
1. Если p1 = p2 = 3 (mod 4), тогда, согласно закону взаимности квадратичных вычетов, символы
Лежандра I — I и I — I различны. Без потери общно-
сти можем предположить, что -1- I = 1. Таким обра-
& gt-2)
зом,
~& lt-(Р Кп
Лp),

(p)
s^X2) =) и s^a^) = s-^(P2).
Подставив последние соотношения в формулу (8), получаем, что S (av) = 0 для всех v е Z*.
2. Если p1 = 1 (mod 4) или p2 = 1 (mod 4), то
— I = - I. В этом случае, без потери общности,
p?) I p)
можно считать, что
S1(p1)(Pf2v) = S p1)(Pv) и sj p2)(Pp1v) = sj p2)(P2). Тогда из (8) получаем, что S (av) = 1 для всех v е Z* [18,19].
Из леммы 4 следует, что утверждение теоремы
1 не имеет места при n = p1 p2 и a = (1,1).
1 2 p1p2
Воспользовавшись леммой 3, можно завершить вычисление линейной сложности последовательности
sш и показать, что если n = p, p» и a = (1,1), то:
1 2 p1 p2
1. L = p1 + p2 -1, если p1 = 3 (mod 8) и p2 = 3 (mod 8)
2. L = p1 + (p2 -1)/2, если p1 = 3 (mod8) и p2 = 7 (mod 8)
3. L = p2 + (p1 -1)/2, если p1 = 7 (mod8) и p2 = 3 (mod 8)
4. L = (p1 + p2)/2, если p1 = 7 (mod 8) и p2 = 7 (mod 8).
Заключение
В работе определены достаточные условия существования обобщенных циклотомических последовательностей с произвольным периодом и высокой линейной сложностью. В частности, показано, что в наиболее часто рассматриваемом варианте обобщенные циклотомические последовательности обладают высокой линейной сложностью при любом периоде. Также предложен метод вычисления линейной сложности рассматриваемых последовательностей.
1. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988. 820 с.
2. Cusick T. W, Ding C., Renvall A. Stream Ciphers and Number Theory. Amsterdam: Elsevier, 1998. 474 р.
3. Ding C., Helleseth T. New generalized cyclotomy and its applications // Finite Fields Appl. 1998. V.4. P. 140−166.
4. Ding C. Linear complexity of some generalized cyclotomic sequences. // Int. J. Algebra Comput. 1998. V.8 (4). P. 431−442.
5. Park Y.H., Hong D., Chun E. On the linear complexity of some generalized cyclotomic sequences // Int. J. Algebra Comput. 2004. V. 14 (4). P. 431−439.
6. Bai E., Liu X. Some notes on prime-square sequences. // J. Comput. Sci. Technol. 2007. V. 22 (3). P. 481−486.
7. Kim Y. -J., Jin S. -Y., Song H. -Y. Linear complexity and autocorrelation of prime cube sequences // Lecture Notes in Computer Science. 2007. V. 4851. P. 188−197.
8. Kim Y.J., Song H.Y. Linear complexity of prime n-square sequences // IEEE International Symposium on Information Theory. Toronto, Canada. 2008. P. 2405−2408.
9. Yan T., Li S., Xiao G. On the linear complexity of generalized cyclotomic sequences with the period pnm // Appl. Math. Lett. 2008. V. 21. P. 187−193.
10. Edemskiy V. About computation of the linear complexity of
generalized cyclotomic sequences with period p& quot-+1 // Designs, Codes and Cryptography. 2011. V. 61 (3). P. 251−260.
n
m
m
и
11. Yan T., Sun R., Xiao G. Autocorrelation and linear complexity of the new generalized cyclotomic sequences. // IEICE Trans. Fund. Electron. 2007. V. E90-A. P. 857−864.
12. Yan T., Chen Z., Xiao G. Linear complexity of Ding generalized cyclotomic sequences // Journal of Shanghai University. 2007. V. 11(1). P. 22−26.
13. Bai E, Liu X., Xiao G. Linear complexity of new generalized cyclotomic sequences of order two of length pq // IEEE Transactions on Information Theory. 2005. V. 51(5). P. 1849−1853.
14. Yan T., Hong L., Xiao G. The linear complexity of new generalized cyclotomic binary sequences of order four // Information Sciences. 2008. V. 178(3). P. 807−815.
15. Chen Z.X., Li S.Q. Some notes on generalized cyclotomic sequences of length pq // Journal of Computer Scitnce and Technology. 2008. V. 23(5). P. 843−850.
16. Edemskiy V., Antonova O. About Computation of the Linear Complexity of Generalized Cyclotomic Sequences with Period pq // Proc. of 2011 International Workshop on Signal Design and Its Applications in Communications (IWSDA'-011). China. 2011. P. 9−12.
17. Антонова О. В., Павлова А. В. О линейной сложности последовательностей Уитмена четвертого порядка // Вестник НовГУ. Сер.: Техн. науки. 2012. №№ 68. С. 123−125.
18. Ding C., Helleseth T., Shan W. On the linear complexity of Legendre sequences // IEEE Trans. Inform. Theory. 1998. V. 44. P. 1276−1278.
19. Едемский В. А. Гантмахер В.Е. Синтез двоичных и троичных последовательностей с заданными ограничениями на их характеристики. В. Новгород.: НовГУ, 2009. 189 с.
Bibliography (Transliterated)
1. Lidl R., Niderraiter G. Konechnye polia. M.: Mir, 1988. 820 s.
2. Cusick T. W, Ding C., Renvall A. Stream Ciphers and Number Theory. Amsterdam: Elsevier, 1998. 474 r.
3. Ding C., Helleseth T. New generalized cyclotomy and its applications 11 Finite Fields Appl. 1998. V.4. P. 140−166.
4. Ding C. Linear complexity of some generalized cyclotomic sequences. 11 Int. J. Algebra Comput. 1998. V.8 (4). P. 431−442.
5. Park Y.H., Hong D., Chun E. On the linear complexity of some generalized cyclotomic sequences // Int. J. Algebra Comput. 2004. V. 14 (4). P. 431−439.
6. Bai E., Liu X. Some notes on prime-square sequences. // J. Comput. Sci. Technol. 2007. V. 22 (3). P. 481−486.
7. Kim Y. -J., Jin S. -Y., Song H. -Y. Linear complexity and autocorrelation of prime cube sequences // Lecture Notes in Computer Science. 2007. V. 4851. P. 188−197.
8. Kim Y.J., Song H.Y. Linear complexity of prime n-square sequences // IEEE International Symposium on Information Theory. Toronto, Canada. 2008. P. 2405−2408.
9. Yan T., Li S., Xiao G. On the linear complexity of generalized cyclotomic sequences with the period p^m // Appl. Math. Lett. 2008. V. 21. P. 187−193.
10. Edemskiy V. About computation of the linear complexity
of generalized cyclotomic sequences with period p& quot-+1 // Designs, Codes and Cryptography. 2011. V. 61 (3). P. 251−260.
11. Yan T., Sun R., Xiao G. Autocorrelation and linear complexity of the new generalized cyclotomic sequences. // IEICE Trans. Fund. Electron. 2007. V. E90-A. P. 857−864.
12. Yan T., Chen Z., Xiao G. Linear complexity of Ding generalized cyclotomic sequences // Journal of Shanghai University. 2007. V. 11(1). P. 22−26.
13. Bai E, Liu X., Xiao G. Linear complexity of new generalized cyclotomic sequences of order two of length pq // IEEE Transactions on Information Theory. 2005. V. 51(5). P. 1849−1853.
14. Yan T., Hong L., Xiao G. The linear complexity of new generalized cyclotomic binary sequences of order four // Information Sciences. 2008. V. 178(3). P. 807−815.
15. Chen Z.X., Li S.Q. Some notes on generalized cyclotomic sequences of length pq // Journal of Computer Scitnce and Technology. 2008. V. 23(5). P. 843−850.
16. Edemskiy V., Antonova O. About Computation of the Linear Complexity of Generalized Cyclotomic Sequences with Period pq // Proc. of 2011 International Workshop on Signal Design and Its Applications in Communications (IWSDA'-011). China. 2011. P. 9−12.
17. Antonova O.V., Pavlova A.V. O lineinoi slozhnosti po-sledovatel'-nostei Uitmena chetvertogo poriadka 11 Vestnik NovGU. Ser.: Tekhn. nauki. 2012. № 68. S. 123−125.
18. Ding C., Helleseth T., Shan W. On the linear complexity of Legendre sequences // IEEE Trans. Inform. Theory. 1998. V. 44. P. 1276−1278.
19. Edemskii V.A. Gantmakher V.E. Sintez dvoichnykh i tro-ichnykh posledovatel'-nostei s zadannymi ogranicheniiami na ikh kharakteristiki. V. Novgorod.: NovGU, 2009. 189 s.

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