Линейная сложность циклотомических последовательностей

курсовая работа

1.1 ОСНОВНЫЕ ОПРЕделения

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

Пусть - натуральное число. Обозначим через кольцо классов вычетов по модулю , а через - мультипликативную группу его обратимых элементов [1]. Рассмотрим разбиение множества , то есть

, . (1.1)

Если - мультипликативная подгруппа и существуют элементы такие, что , то называются циклотомическими классами, если - простое число, и обобщенными циклотомическими классами, если - составное [2]. Последовательности, правила кодирования которых основаны на , называются, соответственно, циклотомическими или обобщенными циклотомическими последовательностями.

В настоящий момент известно несколько способов построения обобщенных циклотомических последовательностей с периодом , где - нечетные простые числа. В этой работе будут рассматриваться только обобщенные циклотомические последовательности [3].

Напомним, что обобщенные циклотомические классы порядка по модулю определяются следующим образом: , , где - общий примитивный корень по модулям и , а элемент

. (1.2)

При этом мультипликативный порядок равен наименьшему общему кратному

и , а [3].

Отметим, что вариант, когда множестваопределяются классами квадратичных вычетов (последовательности простых чисел близнецов, Якоби [4]) исследовался ещё до появления работы [3], и, в настоящий момент, он изучен достаточно подробно[5].

Положим дополнительно и , тогда, как это показано в [3], справедливо разбиение

. (1.3)

Определение. Последовательность называется последовательностью порядка d, если

(1.4)

Здесь рассмотрим только тот вариант, что был предложен в [3]. При этом отметим, что позднее термин обобщенные циклотомические последовательности применялся для любых характеристических последовательностей объединения классов .

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

Напомним, кратко основные понятия, относящиеся к этой теме.

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

Последовательности, обладающие высокой линейной сложностью важны для криптографических приложений [2].

Многочлен - называют минимальным или характеристическим многочленом последовательности [6].

Хорошо известно, смотри, например [6], что минимальный многочлен последовательности и её линейную сложность можно вычислить по следующим формулам:

, (1.5)

где - многочлен последовательности, , при этом:

. (1.6)

Далее, если черезпримитивный корень степени из единицы в поле разложения многочлена нади не делится на 2, то

. (1.7)

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

В [7] был предложен другой подход к построению обобщенных циклотомических классов и общий метод вычисления линейной сложности обобщенных циклотомических последовательностей, основанных на классах степенных вычетов. В следующих подразделах изложим его основные положения.

Делись добром ;)