Регистрация / Вход
Прислать материал

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

Сведения об участнике
ФИО
Цурина Александра Сергеевна
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Новгородский государственный университет имени Ярослава Мудрого"
Тезисы (информация о проекте)
Область наук
Математика. Механика
Раздел области наук
Математика
Тема
Линейная сложность восьмеричных сбалансированных бинарных последовательностей
Резюме
В данной статье представлены результаты исследования линейной сложности восьмеричных сбалансированных бинарных последовательностей, сформированных на основе четырех циклотомических классов.
Ключевые слова
Линейная сложность, восьмеричные последовательности, циклотомические классы
Цели и задачи
Цель настоящей работы заключается в исследовании линейной сложности восьмеричных сбалансированных бинарных периодических последовательностей, т. е. получение теоретических результатов о линейной сложности последовательностей над полем второго порядка. Линейная сложность последовательности будет определена посредством разложение периода последовательности на сумму квадратов целых чисел.
Введение

Проблема защиты информации волновала человеческий ум с давних времен. Традиционным обеспечением конфиденциальности, целостности и аутентификации данных является шифрование. По правилу Керкхоффа стойкость алгоритма шифрования должна определяться стойкостью ключа, то есть длинной используемого ключа.

Линейная сложность  последовательности определяется как длина наименьшего  регистра сдвига с обратной связью, который позволяет воссоздать эту последовательность и является её важным показателем . Чем выше линейная сложность псевдослучайной последовательности, тем выше стойкость этой последовательности к взлому. Поэтому последовательности, обладающие высокой линейной сложностью, важны для криптографических приложений.

 

 

Методы и материалы

Циклотомические классы (классы степенных вычетов и их классы смежности) достаточно часто используются для синтеза последовательностей, в том числе и с высокой линейной сложностью. Последовательности, в этом случае, называются циклотомическими.  Линейная сложность над конечным полем второго порядка циклотомических последовательностей, формируемых на основе квадратичных, биквадратичных и шестеричных вычетов, полностью исследована в цикле работ [1,2]. В то же время для восьмеричных бинарных последовательностей известны только отдельные результаты [1].

Метод исследования основан на вычислении дискретного преобразования Фурье последовательности и значений спектральной последовательности. Применяется специализированный метод вычисления значений многочлена, генерирующего циклотомические классы, разработанный ранее в  [1].

Описание и обсуждение результатов

Пусть \(p=1+8f\) где \(f\) – натуральное число. Обозначим через \(H_0\) – класс вычетов восьмой степени по модулю p, то есть \(H_0=\{\theta^{8t}\pmod p,t=\overline{0,f-1}\}\), здесь \( \theta\) – первообразный корень по модулю p . Положим \(H_s=\theta^sH_0\), где \( s=\overline{0,7}\) (все действия выполняются по модулю p), тогда \(H_i\cap H_j=\emptyset, i\neq j \).

Рассмотрим циклотомические последовательности, сформулированные по следующему правилу:

\(x_i= \begin{cases} 1, & \quad \text{if}\ i\pmod p \in\displaystyle\bigcup_{k\in I}H_k,\\ 0, & \quad \text{otherwise. } \\ \end{cases} \),                                                           (1)

где  \(I\) - подмножество множества индексов \(\{0,1,...,7\}.\)

Обозначим через \(\alpha\)примитивный корень степени p из единицы в поле разложения  многочлена \(t^p-1\) над  полем второго порядка. Пусть \(S_8(t)=\displaystyle\sum_{n\in H_0}t^n\). Тогда,  по (1), имеем \(S(\alpha^n)=\displaystyle\sum_{k\in I}S_8(\alpha^{\theta^k})\), где \(S(t)=x_0+x_1t+...+x_{p-1}t^{p-1}\).

Согласно [1], справедливо следующее соотношение:

\(S_8(\alpha)S_8(\alpha^{\theta^k})=\displaystyle\sum_{f=0}^{7} (k,f)S_8(\alpha^{\theta^f})+\delta \),                                    (2)

где  - \((k,f)\) циклотомические  числа восьмого порядка и \(\delta= \begin{cases} R, & \quad \text{if}\ R \equiv 0 \pmod2 \text{ and } {k=0} \text{ or } R\equiv1\pmod2 \text{ and } {k=4}, \\ 0, & \quad \text{otherwise. } \\ \end{cases} \)

Таким образом, последнее уравнение определяет систему уравнений для значений \(S_8(\alpha),S_8(\alpha^{\theta}), ...,S_8(\alpha^{\theta^7}).\) Её решение позволяет найти значение  и вычислить линейную сложность последовательности по теореме Блейхута.

Теорема. Пусть последовательность X сформирована по (1) для  \(I=\{0,1,2,3\}, p=x^2+4y^2=a^2+2b^2, x\equiv a\equiv 1\pmod4, y\equiv 0\pmod4\), и \(\frac{p-1}{8}\)- нечетное число. Тогда:

·      \(L=\frac{p-1}{2}\) , если \( y\equiv 4\pmod8\);

·       \(L={p-1}\) , если \( y\equiv 0\pmod8\).

Другие случаи рассматриваются аналогично. Достоверность вышеприведенных результатов подтверждена многочисленными расчетами линейной сложности по алгоритму Берлекэмпа-Месси.

Таким образом,  получены теоретические результаты о линейной сложности бинарных последовательностей, сформированных на циклотомических классах восьмого порядка.

Используемые источники
1. Едемский В.А., Синтез двоичных и троичных последовательностей с заданными ограничениями на их характеристики / В.А. Едемский, В. Е. Гантмахер. - Великий Новгород.: НовГУ, 2009.-189 с.2. Dai, Z., Gong, G., Song, H-Y., Ye, D.: 'Trace Representation and Linear Complexity of Binary eth Power Residue Sequences of Period p', IEEE Transactions on Information Theory, 2011, 57, (3), pp.1530-1547

Information about the project
Surname Name
Tsurina Aleksandra
Project title
Linear complexity of the octal balanced binary sequences
Summary of the project
In this article presents the results of the investigation of the linear complexity octal balanced binary sequences formed on the basis of four cyclotomic classes
Keywords
Linear complexity, octal sequence, cyclotomic classes