Обобщенные циклотомические последовательности. Цикломатические числа и их свойства. Метод расчета линейной сложности обобщенных циклотомических последовательностей. Примеры вычисления линейной сложности двоичных последовательностей с периодами.
Краткое сожержание материала:

Размещено на

СОДЕРЖАНИЕ

• СОДЕРЖАНИЕ
• перечень сокращений, символов и специальных терминов
• ВВЕДЕНИЕ
• 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].

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