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

/

СОДЕРЖАНИЕ

• СОДЕРЖАНИЕ
• перечень сокращений, символов и специальных терминов
• ВВЕДЕНИЕ
• 1 ОБОБЩЕНЫЕ ЦИКЛОТОМИЧЕСКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ
• 1.1 ОСНОВНЫЕ ОПРЕделения
• 1.2 ЦИКЛОТОМИЧЕСКИЕ ЧИСЛА И ИХ СВОЙСТВА
• 1.3 ОБОБЩЕННЫЕ ЦИКЛОТОМИЧЕСКИЕ КЛАССЫ ПО МОДУЛЮ
• 1.4 ЦИКЛОТОМИЧЕСКИЕ ЧИСЛА И ЛИНЕЙНАЯ СЛОЖНОСТЬ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, СФОРМИРОВАННЫХ НА ОСНОВЕ КЛАССОВ СТЕПЕННЫХ ВЫЧЕТОВ
• 1.5 метод расчета линейной сложности обобщенных циклотомических последовательностей
• 1.6 О ЛИНЕЙНОЙ СЛОЖНОСТИ ДВОЙНЫХ И ТРОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ПОСТОЯННЫХ НА ВТОРЫХ-ВОСЬМЫХ ПОРЯДКОВ ЦИКЛОТОМИЧЕСКИХ ЧИСЕЛ
• 1.7 ПРИМЕРЫ ВЫЧИСЛЕНИЯ ЛИНЕЙНОЙ СЛОЖНОСТИ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ПЕРИОДАМИ
• 2. ВЫЧИСЛЕНИЕ ЛИНЕЙНОЙ СЛОЖНОСТИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧЕТВЕРТОГО ПОРЯДКА
• ЗАКЛЮЧЕНИЕ
• Список использованной литературы
• перечень сокращений, символов и специальных терминов

Термин	Расшифровка
1	2
Криптография	наука о математических методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации.
Последовательность	последовательность чисел порядка d, сформированная на основе определенного арифметического правила.
Псевдослучайная последовательность	последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.
Линейная сложность последовательности	длина наименьшего регистра сдвига с обратными связями, который позволяет воссоздать последовательность.
Правило кодирования	правило построение последовательности, то есть её определение.
Класс чисел по модулю	числа, имеющие одинаковый остаток при делении на , то есть числа, сравнимые по модулю (всем числам класса отвечает один и тот же остаток ).
Вычет по модулю , наименьший неотрицательный вычет	Любое число класса называется вычетом по модулю по отношению ко всем числам того же класса. Вычет, равный самому остатку , называется наименьшим неотрицательным вычетом.

• Условные обозначения
• -натуральные числа
• -кольцо классов вычетов по модулю
• - характеристические последовательности
• -линейная сложность
• - минимальный многочлен последовательности
• - поле Галуа
• - примитивный корень
• - простые числа
• - многочлен последовательности
• - вспомогательные многочлены
• - индекс целого числа по простому модулюс основанием , т. е.
• - циклотомические классы
• - обобщенные циклотомические классы
• - правило кодирования
• - первообразные корни
• - матрицы
• Сокращения:
• ДП - двоичная последовательность
• ДКП - дискретно-кодированная последовательность

ВВЕДЕНИЕ

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

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

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

Целью данной работы является вычисление линейной сложности последовательностей четвертого порядка с периодом pq, где p и q - простые нечетные числа.

1. ОБОБЩЕНЫЕ ЦИКЛОТОМИЧЕСКИЕ ОСЛЕДОВАТЕЛЬНОСТИ

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

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

1.2 ЦИКЛОТОМИЧЕСКИЕ ЧИСЛА И ИХ СВОЙСТВА

В этом подразделе кратко изложим основные свойства циклотомических чисел, необходимые для дальнейших исследований.

Пусть - конечное поле порядка q и d - делитель , , положим . Обозначим через образующую мультипликативной группы конечного поля.

Пусть - целые числа.

Определение 1.2.1. Циклотомическим числом порядка d называется число решений уравнения

, ( 1.2.1)

где , в поле .

Другими словами, это порядок множества пар целых чисел u и v таких, что и , так как .

Ясно, что если и , то согласно определению 1.2.1, то есть при исследовании циклотомических чисел порядка d достаточно изучить их свойства для . Далее, когда речь идет о циклотомических числах порядка индекс будем опускать, за исключением тех случаев, когда необходимо подчеркнуть о каком именно порядке чисел идет речь.

Если А подмножество , то под будем понимать множество

.

Пусть , - разбиение элементов мультипликативной группы конечного поля.

По определению 1.2.1 для циклотомических чисел имеет место равенство:

. (1.2.2)

Формула (1.2.2) определяет достаточно простой способ вычисления циклотомических чисел, при котором не требуется решать уравнение (1.2.1).

Пример 1.

1). Пусть и . В качестве возьмем 2, первообразный корень по модулю 13 . Тогда ; .

(В первом варианте элементы упорядочены по степеням g)

Вычислим циклотомические числа третьего порядка для по формуле (1.2.2).

Найдем , тогда

,

,

.

Подобным же образом легко убедиться в том, что и так далее.

2). Пусть и . Здесь ; . Тогда , следовательно:

, ,

, .

Пример 2.

Пусть и конечное поле из 9 элементов характеристики 3 определяется многочленом . В качестве образующего элемента мультипликативной группы поля возьмем . Если , то и . Тогда и , следовательно,

и ;

и .

Исследуем свойства циклотомических чисел, вытекающие из определения 1.2.1. Как показано в подразделе , поэтому уравнение равносильно следующему: или

. (1.2.3)

По условию, , следовательно, если - четное число, то , а если же - нечетное число, то .

Таким образом, из (1.2.3) получаем, что:

(1.2.4)

Продолжим изучение свойств циклотомических чисел, по формуле (1.2.2) . Порядок , при этом возможны два варианта: и . Так как, , то в первом случае порядок пересечения будет на единицу меньше. Уточним, когда .

Пусть - четное, тогда и для всех , следовательно, , таким образом, для четного значения получаем, что

(1.2.5)

Аналогично, если - нечетное, то и для всех , то есть , поэтому для нечетного значения имеем, что

(1.2.6)

Выведем ещё одно свойство циклотомических чисел. Умножив уравнение слева и справа на , получим равносильное ему соотношение: , которое имеет столько же пар решений u,v, что и исходное. Таким образом, получаем следующее очень важное свойство циклотомических чисел:

.

1.3 ОБОБЩЕННЫЕ ЦИКЛОТОМИЧЕСКИЕ КЛАССЫ ПО МОДУЛЮ

Пусть - простое число, где - натуральные числа. Обозначим через - класс вычетов степени по модулю , то есть , здесь - первообразный корень по модулю [1], . Положим , где (все действия выполняются по модулю ), тогда и порядок.

Согласно [2], - являются циклотомическими классами и

. (1.3.1)

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

. (1.3.2)

Обозначим через - наименьший неотрицательный вычет целого числа по модулю .

Рассмотрим классы вычетов по модулю N, построенные следующим образом:

, .

Следовательно, каждый класс содержит чисел и, если , то пересечение с пусто [1]. Из определения следует, что является подгруппой мультипликативной группы .

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

. (1.3.3)

Добавим еще три вида классов вычетов:

,

,

тогда порядок прии при . Соответственно, при и , при и . Из формул (1.3.1,1.2.,1.3.3) имеем

. (1.3.4)

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

Рассмотрим примеры разбиения на классы вычетов для различных значений .

Пример 1.

Пусть , , , , , , .

, , , .

, , , .

,,,.

,,,.

,,,.

,,,.

,,,.

,,,.

.

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

Лемма 1.1. Если и , то справедливо равенство:

, . (1.3.5)

Пример 4.

Пусть, как и в примере 3, , , , тогда

, . После вычислений, получаем:

,

,

,

.

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

1.4 ЦИКЛОТОМИЧЕСКИЕ ЧИСЛА И ЛИНЕЙНАЯ СЛОЖНОСТЬ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, СФОРМИРОВАННЫХ НА ОСНОВЕ КЛАССОВ СТЕПЕННЫХ ВЫЧЕТОВ

Определение. Последовательность удовлетворяющая соотношению

(1.4.1)

для всех , из называется линейной рекуррентной последовательностью.

Наименьшее значение , для которого выполняется соотношение (1.4.1) называется линейной сложностью (эквивалентной линейной сложностью, рангом) последовательности над полем .

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

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

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

Как и ранее, пусть ДП X с периодом сформирована по обобщенному ПК:

(1.4.2)

Согласно

, (1.4.3)

где , более того:

. (1.4.4)

циклотомический последовательность линейный двоичный

Если рассмотреть разложение многочлена на неприводимые множители над , то всегда можно построить конечное поле, которое содержит все его корни. Такое поле называется полем разложения многочлена .

Пример 1. Пусть , тогда, несложно убедиться, что и многочлены , - неприводимы над . В этом случае, элементы мультипликативной группы конечного поля , построенного по многочлену или будут корнями 7 степени из единицы.

Пусть - примитивный корень степени из единицы в поле разложения многочлена над . Тогда, согласно формуле (1.4.4), для ДП (БП):

. (1.4.5)

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

Введем дополнительный многочлен .

Следующая лемма описывает свойства многочлена , она доказана в [20].

Лемма 1.2. Если , то в поле справедливы следующие соотношения:

1) для .

2) для любого целого числа .

3) Если , то .

Пример 1. Пусть , , , тогда , . По определению , далее , следовательно, .

Отметим ещё одно свойство многочлена . Из равенства следует, что в поле сумма , т. е. и, по лемме 1.4.1 имеем

. (1.4.6)

Например, если , то или . Тогда , и .

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

По определению последовательности получаем, что , тогда или, по лемме 1.2 , , если . Таким образом, для нахождения корней многочлена достаточно определить значения , . Более того, значения , если и из (4.6.4) получаем, что линейная сложность ДП равна

. (1.4.7)

Теорема 1.1. Если , то

где

Теорема 1.1. определяет систему уравнений для неизвестных с использованием таблицы циклотомических чисел порядка . Её решение позволяет определить значения Последнее, согласно соотношению (1.4.7), делает возможным расчет линейной сложности рассматриваемых ДП.

1.5 МЕТОД ВЫЧИСЛЕНИЯ ЛИНЕЙНОЙ СЛОЖНОСТИ ЦИКЛОТОМИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

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

for all [1].

Полином-многочлен называется минимальным из последовательности в котором следует [1]

(1.5.1)

где является полином-многочленом последовательности. Тогда по (1) мы имеем

(1.5.2)

Пусть простое, единственный корень в области полином-многочлена в областий и. Из (1.5.2) из этого следует

(1.5.3)

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

(1.5.4)

В этом разделе мы исследуем метод вычисления для циклотомических последовательностей периодом.

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

Давайте рассматривать последовательность с периодом , построенный следующим способом:

(1.5.5)

где - предопределенные числа в области . Давайте предполагать значения , если переменная не предусмотрена.

Тогда, мы вводим вспомогательный полином-многочлен .

Следующая лемма - простое обобщение утверждений, доказанных в [3,4] для и.

Лемма 1.3. Если , тогда ;

если f , тогда .

От леммы 1.3 мы периходим

(1.5.6)

Таким образом, чтобы вычислить значения достаточно найти .Что позволит нам ввести примечание . Метод вычисления составляет основное содержание раздела.

Сначала, мы отмечаем , поэтому по лемме 1.3, мы имеем

(1.5.7)

В частности одна из лемм вспомогательного полином-многочлена всегда отличается от ноля. Не нарушая заурядность мы можем предположить, что .

Мы напоминаем что циклотомическое число порядка является множеством решений соответствия [10]. Следующая лемма вытекает из определения циклотомических чисел.

Лемма 1.4. Если тогда число решений соответствия когда равняется .

Тогда докажемм основную теорему раздела.

Теорема 1.2. Для мы имеем

где

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

где является множеством решений: . По этому , тогда как в теореме, которая была доказана.

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

1.6 О ЛИНЕЙНОЙ СЛОЖНОСТИ ДВОЙНЫХ И ТРОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ПОСТОЯННЫХ НА ВТОРЫХ-ВОСЬМЫХ ПОРЯДКОВ ЦИКЛОТОМИЧЕСКИХ ЧИСЕЛ

В этом разделе мы иллюстрируем изложенные выше методы с примерами вычисления линейной сложности двойных и троичных последовательностей по областям где.

Пусть и . Используем теоремму 1 когда , тогда

(1.6.1)

где, если является нечетным и нулевым. По формуле (7) мы имеем

(1.6.2)

Циклотомические числа второго порядка зависящие от , если четно, тогда, и если является нечетным, тогда . Поэтому, по (1.6.1) и (1.6.2) формуле мы получаем, чтоСледовательно, и являются корнями полином-многочлена . Принятие во внимание предположения , мы получаем тогда и только тогла в области .

если , тогда для или , поэтому:

1). , если или ;

2). , где является корнем уравнения , если или .

В случае, если , тогда для или , так:

1). , если или ;

2). , где - корень уравнения , если или .

Пусть , и . Циклотомические числа третьего порядка сформированы разложением , где являются целыми числами [10]. В частности мы имеем

Если и четно, тогда модуль остатков два из перечисленных циклотомических чисел равняется нолю, исключая . По теореме 1.3 и формуле (1.5.7), мы получаем следующий набор уравнения для неизвестного , и:

(1.6.3)

По формуле (1.6.3) , мы получаем , если.

В случае, если , тогда

для.

Тогда , где - корень уравнения .

Полученные значения позволяют вычислять линейную сложность последовательностей, например если , то есть, (1.5.6), является характерной последовательностью , где для и когда .

В случае, если , и is even, тогда и . В таких остатках выбора циклотомических чисел третьего порядка, вычислены формулами:

Тогда, для теореме 1.2 и формуле (1.5.7) мы получаем следующую систему уравнений:

(1.6.4)

Исследование (1.6.4), и также подобронного к нему значения , зависящие от остатков , и значений мы получаем следующие решения:

1). (до перестановки), если , или , ;

2). , , если , или , ;

3). , если , или , ;

4). , где являются корнями уравнения:

, если , или , ;

, если , или , ;

, если , или , .

Циклотомические изменения значений не влияют на вычисление линейной сложности. Кроме того, , если [10], тогда . По этому, , по (7) - корни полином-многочлена , который разложен на множители в области следующим образом . Это точно соответствует результатам последнего, четвертого случая.

Пусть , для . В этом подразделе и в следующих мы ограничимся с исследованием значений полином-многочлена двоичной последовательности, потому что линейная сложность троичных последовательностей когда в области был изучен в [11]. Циклотомические числа четвертого порядка сформированы разложением: [10], где - целые числа, и зависят от , совпадает с .

Если даже является следствиями подраздела 1.6.1, . По определению вспомогательного полином-многочлена, , где

(1.6.5)

Для циклотомические числа четвертого порядка, сформированны

После вычисления их модуля два остатка , где являются целыми числами, по теореме 1.2 и формуле (1.6.5), мы имеем

(1.6.6)

После изучения (1.6.5) и (1.6.6), в зависимости от модуля остатков мы получаем:

1). , если , ;

2). , если , ;

3). , если , , где является корнем уравнения: ;

4). , если , .

Если - нечетный, тогда как и показанно в разделе 1.6.1, . В этом случае, то же самое что касается значения .

5). , если , где является корнем уравнения: or , где является корнем уравнения . Если , где является корнем первого порядка, иначе второго. Полученные формулы для позволят вычислять линейную сложность и минимальный полином-многочлен любой двоичной последовательности простого периода , построенный в циклотомических классах четвертого порядка, включая изученные в [5]. Особенно, если является характерной последовательностью биквадратного класса остатка, тогда , если или .

Пусть, для . Циклотомические числа 6 порядка сформированы разложением: [12], где являются целыми числами, в зависимости от .

По определению вспомогательного полином-многочлена мы имеем . Которые показывают в подразделе 1.6.2 значения завищащие от , где определена от разложения . От отношений между и [10] мы получаем это, тогда и только тогда, когда. Следовательно, если , когда и

(1.6.7)

Если является нечетным, тогда и циклотомические числа шестого порядка определены [12]:

После вычисления их по модулю два по теореме 1.1, мы добираемся

(1.6.8)

Решение (1.6.7) и (1.6.8) приводит к следующему:

1). , если , , где i корень уравнения: ;

2). , если , ;

3). , если , ;

4). , если , .

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

1.6.5. Пусть , для . Циклотомические числа восьмого порядка определены разложением [10, 13] , где являются целыми числами, и зависят от остатка по модулю четыре. В этом подразделе мы ограничимся исследованием значений только для двоичных последовательностей с нечетными значениями и .

Как для результатов подраздела 1.6.3 мы имеем

(1.6.9)

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

По теореме 1.1 и формуле (1.6.9) мы добираемся

(1.6.10)

Так, по (1.6.9) и (1.6.10) следуя за этим, числа принадлежат множеству , где корень полином-многочлена , и зависят от остатков по модулю два. Чтобы упорядочить их, мы используем заключение теоремы 1.1. В данном случае Наконец мы получаем:

1). , или , ;

2). , или , ;

3). , или , ;

4). , или , ;

5). , или , ;

6). , или , ;

7). , или , ;

8). , или , .

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

Док. Класс остатков в различных положониях, если [10]. Поэтому, , тогда среди значений есть пять нолей. По лемме 1.5, и формуле (1.5.3) следует доказательство первого утверждения леммы 1.4. Второе мы доказываем почти таким же способом. Минимальный полином-многочлен последовательности может быть вычислен в случае (1.5.4).

1.7 ПРИМЕРЫ ВЫЧИСЛЕНИЯ ЛИНЕЙНОЙ СЛОЖНОСТИ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ПЕРИОДАМИ И

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

Согласно китайской Теореме Остатка, кольца остатков является изоморфным к прямому продукту [9]. Пусть , где , как прежде, циклотомические классы порядка , является подмножеством индексов .

Исследуем двоичную последовательность , определенную как

(1.6.11)

Для последовательности формула (1.5.2) будет похожа

(1.6.12)

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

Лемма 1.6. .

Докозательство. Для , когда . Когда принимает значения от , тогда остаток

принимает значения от , которые должны были быть доказан в лемме.

Следующая лемма следует из лемм 1.5 и 1.6.

Лемма 1.7. Если полином-многочлен последовательности , т

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

Лемма 1.8. Если двоичная последовательность определенна в (1.6.11) для подмножества равная, где -циклотомические классы четвертого порядка, - различных индексов от ноля до трех, тогда его линейная сложность , if или и , если или.

Докозательство. По лемме 1.4, . Извлекая пользу из значений найденные в подразделе 1.6.4, после подведения итогов мы получаем равные нолю, если или и равняется .

Просто удостовериться этому, когда значения и единственность - кореня со степенью два. По этому и формуле (1.6.12) мы получаем утверждение леммы 1.8.

Лемма 1.9. Если двоичная последовательность определена циклотомическими классами четвертого порядка и формулой (1.6.11) когда or и , , , , тогда его линейная сложность .

То же самое, доказывая лемму 1.9 мы удостоверяемся, что если утверждение леммы 1.6 верно, то где , и и единственность- кореня со степенью четыре.

2. ВЫЧИСЛЕНИЕ ЛИНЕЙНОЙ СЛОЖНОСТИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧЕТВЕРТОГО ПОРЯДКА

Пусть последовательность четвертого порядка, то есть , тогда, согласно лемме 1.1, она формируется по правилу:

(2.1)

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

. (2.2)

Как и в [7] из формулы (2.2) получаем следующее утверждение.

Лемма 2.1. Если последовательность определена по правилу (2.1), тогда для имеем

Следствие 2.1. Значение многочлена последовательности постоянно, когда принадлежит обобщенным циклотомическим классам , множествам .Пусть , когда .

Воспользовавшись формулой (1.7) из леммы 2.1 получаем, что

,(2.3)

где и

Прежде чем приступить к вычислению, введем несколько обозначений. Пусть, далее, и . Определим матрицу четвертого порядка следующим образом: (*- транспонирование матрицы).

Лемма 2.2.Если , то или

(2.4)

Данная формула следует непосредственно из леммы 2.1.

Таким образом, фактически, для расчета линейной сложности циклотомических последовательностей достаточно рассчитать матрицу для этого случая. В [9] были найдены значения для и частично для. В частности, если , то всегда справедливо разложение , - целые числа и , посредством которого и находятся значения . Согласно [9] имеют место следующие соотношение:

1. или, если , то есть и , где - дискретный логарифм 2 по основанию по модулю ;

2. , где - корень уравнения , если , то есть и ;

3. или , если , то есть и ;

4., если , то есть и ;

5. или, если , где - корень пятнадцатой степени из единицы в расширении поля , при этом он удовлетворяют уравнению . В первом варианте , а во втором . Отметим, что будет корнем 3 из единицы, поэтому можно считать без нарушения общности, что.

Далее, так как справедливо разложение , то длявозможны два варианта:

1. - корень первого множителя, тогда является корнем пятой степени из единицы;

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

Для удобства вычислений обозначим через именно корень пятнадцатой степени из единицы и, в первом случае заменим т на. Таким образом, мы имеем 4 варианта:

5a., здесь ;

5b., здесь ;

5c., здесь ;

5d., здесь .

При этом выполняются соотношения:

, ,

и так далее.

Формулы для аналогичны.

Сразу же заметим, что в первых четырех вариантах, то есть , а в пятом , тогда . Аналогично, если для q имеет место один из первых четырех вариантов, то , а в пятом - .

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

1) 13, 353,593;

2) 17, 929;

3) 73, 89, 233;

4) 41, 313, 761;

5) 5,13, 61;

5a) 13, 29,61;

5b) 397,1069;

5c)5, 37, 53;

5d) 277, 1093.

Введем дополнительно следующие обозначения. Пусть

, и .

Для получения быстрых и точных расчетов простых чисел была использована следующая программа:

Рисунок 1.Пример расчета простых чисел для.

Рисунок 2. Пример расчета простых чисел для.

Для получения значений была использована программа Mathcad. С помощью неё были рассчитаны матрицы H:

Рисунок 3. Пример расчета матрицы Н в программе Mathcad.

Лемма 2.3. Если последовательность X задана правилом (2.1) и ,,то и .

Доказательство. Согласно приложению, а по условию леммы и, тогда согласно формуле (2.3) , а по формуле .

Таблица 1 -- Численные примеры для леммы 2.3.

p	Q	N	L	p	Q	N	L
17	13	221	220	17	29	493	492
41	13	533	532	41	29	1189	1188
73	61	4453	4452	73	13	949	948
89	61	5429	5428	89	29	2581	2580

Лемма 2.4. Если последовательность X задана правилом (2.1) и тои

.

Доказательство. Согласно приложению , а по условию леммы и , тогда согласно формуле (2.3)и.

Таблица 2 -- Численные примеры для леммы 2.4.

p	Q	N	L	p	q	N	L
5	17	85	64	5	41	205	160
13	17	221	192	13	73	949	864
29	73	2117	2016	29	17	493	448
61	41	2501	2400	61	17	1037	960

Аналогично предыдущим леммам получаются следующие утверждения:

Лемма 2.5. Если последовательность X задана правилом (2.1), то:

1) для и ;

2)для и ;

3) для и ;

4) для и ;

Таблица 3 -- Численные примеры для леммы 2.5.

Вариант	p	q	N	L
1	17	73	1241	1224
	113	41	2993	1512
2	113	353	39889	29920
	17	929	12064	15793
	73	89	4840	6497
	41	313	12833	9672
3	17	113	1921	1008
	41	73	2993	1512
	41	89	3649	1848
	17	353	6001	3168
4	73	113	8249	2128
	17	41	697	200
	313	17	5321	1264
	89	113	10057	2576

Лемма 2.6. Если последовательность X задана правилом (2.1), то:

1). Если , то , если (A) и (B), если ;

2). Если , то (C), если и (D), если .

Таблица 3 -- Численные примеры для леммы 2.6.

Вариант	p	q	N	L
A	13	5	65	48
	397	277	109969	82368
B	13	29	377	96
	397	1069	424393	106128
	5	37	185	40
	277	1093	302761	75624
C	13	277	3601	1668
	397	5	1985	1188
D	13	397	5161	4764
	5	277	1385	1108

ЗАКЛЮЧЕНИЕ

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

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

Список использованной литературы

1. Айерлэнд, К. Классическое введение в современную теорию чисел / К. Айерлэнд, М. Роузен.- М.: Мир, 1987.- 416 с.

2. Cusick T W, Ding C, Renvall A. Stream Ciphers and Number Theory. Amsterdam: Elsevier, 1998.

3. Whiteman A L. A family of difference sets. Illinois J. Math., 1962, 6: 107-121.

4. Свердлик, М.Б Оптимальные дискретные сигналы / М.Б. Свердлик. - М.: Сов.радио, 1975. - 200 с.

5. D.H. Green and P.R. Green. Modified Jocobi sequences. IEE Proc. Comput. Digit. Tech.,147(4), 2000.

6. Лидл, Р. Конечные поля / Р. Лидл, Нидеррайтер Г. - М.: Мир, 1988.- 820 с.

7. Edemskiy, O. Antonova .About Computation of the Linear Complexity of GeneralizedCyclotomic Sequences with Period pq. Proceedings of 2011 International Workshop on Signal Design and Its Applications in Communications (IWSDA'011). China. 2011, pp. 9-12.

8. Едемский В. А. О линейной сложности двоичных последовательностей на основе классов биквадратичных и шестеричных вычетов. Дискретная математика. 2010 г. Т. 22, вып. 1 . С. 74-82.

9. Едемский, В.А. Синтез двоичных и троичных последовательностей с заданными ограничениями на их характеристики / В.А. Едемский, В. Е. Гантмахер.- Великий Новгород.: НовГУ, 2009.- 189 с.