Линейной сложности последовательностей с периодом 2 pn на основе классов квадратичных вычетов

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


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

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

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

УДК 512. 628. 4
О ЛИНЕЙНОЙ СЛОЖНОСТИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ПЕРИОДОМ 2 рп НА ОСНОВЕ КЛАССОВ КВАДРАТИЧНЫХ ВЫЧЕТОВ
В. А. Едемский, О.В. Антонова
Институт электронных и информационных систем НовГУ, Vladimir. Edemsky@novsu. ru
Предложен метод расчета линейной сложности и минимального многочлена двоичных последовательностей с периодом 2рп, сформированных на основе классов квадратичных вычетов. Выделены последовательности, обладающие высокой линейной сложностью.
Ключевые слова: двоичные последовательности, линейная сложность, квадратичные вычеты
We propose the method of computing the linear complexity and the minimal polynomial of the quadratic residue binary sequences of period 2pn. Also we determine the sequences with high linear complexity.
Keywords: binary sequences, linear complexity, quadratic residues
1. Введение
Линейная сложность последовательности определяется как длина самого короткого линейного регистра сдвига с обратными связями, который может воссоздать последовательность и является ее важным показателем [1]. Обратная функция регистра сдвига может быть получена, когда известно по крайней мере 2L идущих подряд значений последовательности. Таким образом, можно считать, что для «хороших» последовательностей L & gt- N /2 (где N обозначает период последовательности) [1]. Последовательности, обладающие высокой линейной сложностью, важны для криптографических приложений [2].
В [3] был предложен метод расчета линейной сложности обобщенных циклотомических последовательностей с периодом рп. Целью этой статьи является его обобщение на последовательности с периодом 2рп, сформированные на основе классов квадратичных вычетов.
2. Основные определения
Пусть р — нечетное простое число. Хорошо известно, что всегда существует число g — общий первообразный корень по модулям рп и 2рп, где п
— натуральное число [4]. Обозначим через Н0 и G0 подгруппы, порожденные g2, в группах 1 * «и 1 * п
2 р р
соответственно. Если, А — подмножество кольца 1 п и / е 1, то через tA и t + А будем обозначать
2 р
следующие множества: tA = {ta (mod2рп)| а е А} и t + А = ДО + a)(mod2рп) | а е А}. Аналогично, если А
— подмножество 1 п.
Пусть Н1 = gH0 и G1 = gG0, тогда
Gk ={a (modрп)|а еНк}, к _ 0,1 (1)
и справедливы разбиения
к=0
(2)
к=0
Пусть Ц _ 0'-0,… Л-1) и Ц2 = (10,…, 1п-1) —
векторы, координаты которых равны нулю или единице. Введем множество
п-1
С = и ркНч и 2ркНк и {0}
к=0
и рассмотрим последовательность X, определяемую следующим образом:
_(1, если i (mod2рп) е С,
1 [0 в ост. случаях.
Последовательность X является сбалансиро-ваной согласно выше приведенным определениям. Часто классы вычетов Нк, 2Нк называют обобщенными циклотомическими классами второго порядка, а X — соответтственно обобщенной циклотомической последовательностью [2].
В этой статье исследуем линейную сложность последовательности X. Отметим, что в частном случае, когда Ц _ Ь2 _ (1,…, 1) и р=+3(шой8), линейная сложность последовательности X найдена в [5,6].
3. Вспомогательные леммы
Пусть? (х) = ^ х1 — многочлен последова-
1еС
тельности X, тогда ее линейную сложность L и минимальный многочлен т (х) можно определить по следующим формулам [2]:
L = 2pn — deg
m (x) = -
НОД^ x2 pn -1, S (x) j
, 2 pn
-1
НОД1 x2pn -1, S (x)
(3)
(4)
Обозначим через, а примитивный корень спепени рп из единицы в расширении поля GF (2). Так как в поле характеристики два справедливо
, 2 рп _Г хр
разложение х2р -1 _1хр -II, то согласно ?(ау) = 1 + ЪRk, 0(аv)+Rk, 1(av), т. е.
5(а) = 1 + Ъ (аv) + Ъ Rkjt (аv).
к0 к0
Следовательно, в силу выбора I, получаем, что
= 1 + у R
формулам (3) и (4) вычисление линейной сложности и минимального многочлена последовательности X сводится к нахождению корней многочлена? (х) в
множестве {а1,I = 0,1,…, рп -1} и определению их кратности.
Введем вспомогательные многочлены
?к,/(х)= Е х1, тк,/(х)= Е ^ Як,/(х)= Е ^
1е р Н / 1е2 р Н / 1ер G/
здесь к = 0,1,…, п -1- / _ 0,1. Индексы Н/ и G/ всегда будут рассматриваться по модулю два.
Лемма 1. Для любых значений к = 0,1,…, п -1-
/ _ 0,1 и V = 0,1,…, рп-1 справедливы соотношения:
1) ?к, у (аУ) = Як,/ (аУ) —
|як/ (аУ), если р = +1(mod8), [Як,/+1(аУ), если р = +3(mod8). Доказательство. Согласно (1) имеем pkG/ ={a (mod рп)| а еркН/}, а так как ар _ 1 и? к, / (аУ)= Е аУ1, то из последней формулы и сле-
1е ркН /
дует первое утверждение.
Далее, если р = ±1(mod8), то 2 е Н и 2G/ _ ^ [4]. Как и ранее, получаем, что в этом
случае Тк,/ (аУ) = Як / (аУ). Если же р = +3(mod8), то
2 г Н0 и 2G/ _ G/+1, тогда
Тк,/ (аУ)=? а» _ Е а" _ Як,/+: (аУ).
1е2 ркН/ 1е ркН/+1
Что и требовалось показать.
Пусть
1к, если р = +1(той8),
2) Тк, г (а') _¦
]к _•
1 — 1к, если р = +3(mod 8)
и I = {крк Ф ], к _ 0,1,…, п -1}.
Лемма 2. 5(а') = 0 для V = 0,1,…, рп-1 тогда
и только тогда, когда V є
и рп
'-г
к+1
кєі
Доказательство. Прежде всего заметим, что ?(1) Ф 0 по определению последовательности. Согласно (2) имеем
? (аУ) = 1 +? ?кА (аУ) +? Т^ (аУ),
к _0
к _0
или по лемме 1
кєі
уЯр
(5)
кєі Иєг
по определению вспомогательного многочлена.
Согласно лемме 3 из [3] для любого I = 1,…, п
сумма
ъ
Иєг *
і І1, если t _ I -1,
І0, если і ФI -1.
Из последнего соотношения по формуле (5) получаем, что если V є р г п- /, то
11, если к + / Ф п -1,
10, если к + / _ п -1.
Таким образом, 5 (а') = 0 для V = 0,1,…, рп-1
ип1_к ^ *
р г к+1, что и
кєі
доказывает лемму 2.
Для того, чтобы определить, какие из чисел, а ' являются кратными корнями многочлена 5(х), воспользуемся результатами из [3]. Определим вспомогательную последовательность Y, положив
У _¦
11, если i (modрп) є Gi и… и Gi
10 в ост. случаях.
Пусть 5 Г (х) — многочлен последовательности Y. В [3] показано, что если V є р^/, I _ 0,1,…, п -1, то
5Y (а") = Rn-1,in_l_l (р ^+/ | +1(р -1)/2, (6)
рп-1
где в _ ар. При этом, не нарушая общности, можно считать, что Rn-1,0(P) Ф 0 [7,8].
Лемма 3. Если 5(а?) = 0 для V є рп-1-кг* к+1 ,
к = 0,1,…, п -1, то av — кратный корень многочлена 5(х) тогда и только тогда, когда V є рп-к_1Git+1 при р = 1(тоё8) или V є рп-к -1 Gi+1 для нечетного п — к и V є рп-к -^ для четного п — к при р = -1(mod8).
Доказательство. Для выделения кратных корней многочлена 5 (х) исследуем его производную. По определению многочлена последовательности X
п-1
имеем
5 (х) = х 1Ъ 5и ^ (х). Тогда по лемме 1
I _0
п-1
получаем, что 5 ^) = а^ Ъ Rl ц ^)
или
I _0
п-к
? (аУ) = а У? т (аУ). Воспользовавшись формулой (6), получем, что если у е рп-к-1/, то
?'- (аУ) = а-УЯп-!, 1к (вgik+У) + (п — к -1)(р -1)/2. (7)
Если р = +3(тоё8), то Яп-1,-- (ва) г {0,1}, у _ 0,1 для любого а: а Ф 0(тоё р) [7,8].
Следовательно, в этом варианте по (7)? (аУ) Ф 0 и аУ — простой корень многочлена ?(х).
Если же р ф +1(mod8), то [7,8]
[1, если a (mod р) е G0,
Я-1. аСРа) Ч0 (/'-- ° (8)
[0, если a (mod р) е 11.
Пусть р ф 1(mod 8), тогда (р -1)/ 2 ф 0(mod8)
и согласно формулам (7,8)? (аУ) _ 0 для
у е рп-к-11/ тогда и только тогда, когда
/: g1k +у (modр) е, т. е. / ф 1к + 1(mod2).
Пусть р ф -1(mod8), тогда, как и в
предыдущем случае, получаем, что? (аУ) _ 0 для у е рп-к-11/ тогда и только тогда, когда
[/ ф 1к + 1(mod2), если (п — к) нечетно,
[/ ф 1к (mod2), если (п — к) четно.
Последнее утверждение и завершает доказательство леммы 3.
4. Метод вычисления линейной сложности последовательности
Сформулируем теперь основной результат ста-
тьи.
Теорема 1. Пусть последовательность X определена формулой (2), тогда:
, х2рп -1
1) L _ 2рп -^ р (р -1) и т (х) = -
где
G (x) = П
kєI
xp -1
G (x)
если p Ф+3(mod8) —
kєI
2)
L _ 2p& quot- -1,5^ pk (p -1)
kєI
m (x) =
x2 P& quot- -1
G (^П П (x — av)
если p ф +1(mod8).
Здесь
/k _
ik, если (n — k) четно и p ф-1(mod8), 1 — ik в ост. случаях.
Доказательство. По лемме 2? (аУ) = 0 для у = 0,1,…, рп-1 тогда и только тогда, когда у е ирп-1-к1 *к+1. Если р ф+3(mod8), то в силу
kєI
стые. Далее, когда v є p& quot- 1 kZ* k+1, то av является
корнем многочлена xp -1, но не является корнем
многочлена
xp -1. В этом случае
тео-
НОД (х2 р -1,5(х)) = ^ хР к -1, и утверждение
кєі Х" -1
ремы 1 при р Ф+3(тоё8) следует из формул (3) и (4).
Пусть р ф +1(mod8). В этом случае по лемме 3 число аv является кратным корнем многочлена 5 (х), если V є рп-к-1G/i. Следовательно, как и выше,
НОД (х2р -1,5(х)) = G (x)^ ^ (х — av). И снова
применение формул (3) и (4) завершает доказательство теоремы.
В заключение заметим, что если
п-1
р ф +3(mod 8), то по теореме 1 L & gt- 2рп — 2 рк (р -1)
к _0
или L & gt- рп +1. Таким образом, если р Ф+3(mod8), то любая последовательность, сформированная по правилу (2), заведомо обладает высокой линейной сложностью. Если же р ф +1(mod8), то этот же результат достигается при п -1 г I.
5. Заключение
В статье предложен метод расчета линейной сложности и минимального многочлена обобщенных циклотомических последовательностей, сформированных на основе классов квадратичных вычетов. Определены условия, при выполнении которых эти последовательности заведомо обладают высокой линейной сложностью и могут быть использованы для криптографических приложений.
леммы 3 все корни многочлена S (x) вида av про-
1. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988. 820 с.
2. Cusick T.W., Ding C., Renvall A. Stream Ciphers and Number Theory. Amsterdam: Elsevier, 1998. 474 р.
3. Edemskiy V. About computation of the linear complexity of
generalized cyclotomic sequences with period pn+1 // Designs, Codes and Cryptography. 2011. V. 61. Issue 3. Р. 251−260.
4. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987. 416 с.
5. Zhang J., Zhao C. -A., Ma X. On the Linear Complexity of Generalized Cyclotomic Binary Sequences with Length 2 p2 // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2010. E93. A1. Р. 302−308.
6. Zhang J., Zhao C. -A., Ma X. Linear complexity of generalized cyclotomic binary sequences of length 2pm // Appl. Algebra Eng. Commun. Comput. 2010. V. 21(2). Р. 93−108.
7. Ding C., Helleseth T., Shan W. On the Linear Complexity of Legendre Sequences // IEEE Trans. Info Theory. 1998. V. IT-44. Р. 1276−1278.
8. Едемский В. А. Гантмахер В.Е. Синтез двоичных и троичных последовательностей с заданными ограничениями на их характеристики. В. Новгород.: НовГУ, 2009. 189 с.
?єІ vє p& quot--k-G
k
xp -1
и
kєI vєp& quot--k-1G
Bibliography (Transliterated)
1. Lidl R., Niderrajjter G. Konechnye polja. M.: Mir, 1988. 820 s.
2. Cusick T.W., Ding C., Renvall A. Stream Ciphers and Number Theory. Amsterdam: Elsevier, 1998. 474 p.
3. Edemskiy V. About computation of the linear complexity of
generalized cyclotomic sequences with period pn+1 // Designs, Codes and Cryptography. 2011. V. 61. Issue 3. R. 251−260.
4. Ajjerlehnd K., Rouzen M. Klassicheskoe vvedenie v sovre-mennuju teoriju chisel. M.: Mir, 1987. 416 s.
5. Zhang J., Zhao C. -A., Ma X. On the Linear Complexity of
Generalized Cyclotomic Binary Sequences with Length 2p2
// IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2010. E93. A1. R. 302−308.
6. Zhang J., Zhao C. -A., Ma X. Linear complexity of generalized cyclotomic binary sequences of length 2pm // Appl. Algebra Eng. Commun. Comput. 2010. V. 21(2). R. 93−108.
7. Ding C., Helleseth T., Shan W. On the Linear Complexity of Legendre Sequences // IEEE Trans. Info Theory. 1998. V. IT-44. R. 1276−1278.
8. Edemskijj V.A. Gantmakher V.E. Sintez dvoichnykh i tro-ichnykh posledovatel'-nostejj s zadannymi ogranichenijami na ikh kharakteristiki. V. Novgorod.: NovGU, 2009. 189 s.

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