Введение Элементарная теория чисел, в частности циклотомия, применяется в теории кодирования и криптографии, при построении разностных множеств и формировании последовательностей. Циклотомические классы определяются как классы смежности подгруппы мультипликативной группы обратимых элементов кольца классов вычетов по модулю . Для составного они называются обобщенными циклотомическими классами. Циклотомические и обобщенные циклотомические классы применяются при определении последовательностей. С криптографической точки зрения циклотомические и обобщенные циклотомические последовательности изучались в [1–3]. Свойства обобщенных циклотомических последовательностей длины исследовались в [4–9]. Новый подход к определению обобщенных циклотомических классов предложен в [10], а в [11] на основе новой циклотомии из [10] сформированы бинарные последовательности с периодом . Свойства этих последовательностей, в частности линейная сложность, изучены в [3, 11, 12]. Для криптографических применений последовательность должна иметь высокую линейную сложность, но это только необходимое условие. Важно, как она меняется при изменении нескольких членов последовательности. Наименьшая линейная сложность, которую можно получить, изменяя на периоде не более чем k членов исходной последовательности, называется k-ошибкой линейной сложности последовательности [13]. В [14] изучена k-ошибка линейной сложности отдельных новых обобщенных циклотомических бинарных последовательностей. Определение бинарных последовательностей из [11] было расширено в [15], где предложено правило построения q-ичных последовательностей периода на основе новой циклотомии. Рассмотренные в [15] последовательности имеют высокую линейную сложность над конечным полем порядка . Данная статья посвящена изучению k-ошибки линейной сложности последовательностей с периодом из [15] и обобщению результатов из [14]. С этой целью для k-ошибки линейной сложности будет получена рекуррентная формула и ее оценка для ряда значений . Основные определения В этом разделе напомним определение -ичных последовательностей из [15]. Пусть – простое число, отличное от двух, , где – целые положительные числа, и – примитивный корень по модулю [16]. Согласно [10], обобщенные циклотомические классы порядка по модулю определяются следующим образом: (1) Здесь и . Множества , являются классами смежности и образуют разбиение для каждого целого . На основе этих классов в [11] сформировано новое семейство почти сбаланисированных бинарных последовательностей, их линейная сложность изучена в [3, 11, 12], когда – четное. В [15] предложено обобщение этой конструкции и рассмотрены новые -ичные последовательности. Пусть , , а также где , : и . Согласно определению имеем, что и . В [15] рассмотрено семейство -ичных последовательностей периода , определенное по следующей формуле: (2) Линейная сложность последовательности над конечным полем определяется как наименьшее натуральное число , для которого существуют константы из такие, что выполняется рекуррентное соотношение для всех . В [15] показано, что новое семейство последовательностей обладет высокой линейной сложностью над конечным полем порядка , , где – простое число. В этой статье рассмотрим, как она меняется при изменении последовательности. К-ошибка линейной сложности последовательности периода определеляется как , где минимум берется по всем N-периодическим последовательностям над , для которых расстояние Хэмминга между векторами и не превышает . Анализ -ошибки линейной сложности последовательности Основные результаты исследования представлены в следующей теореме. Теорема. Пусть – примитивный корень по модулю и – последовательность периода , определенная по (2). Тогда справедливы следующие утверждения для -ошибки линейной сложности последовательности : 1) , если ; 2) , если ; 3) при ; 4) для . Таким образом, эти рассматриваемые последовательности имеют высокую линейную сложность, и она существенно не уменьшается при изменении членов последовательности для . Следовательно, они стабильны. Прежде чем доказать основную теорему, получим несколько вспомогательных утверждений. Порождающий многочлен последовательности обозначим через . Хорошо известно, что -ошибку линейной сложности над можно найти, применяя следующее соотношение: где – многочлен последовательности, корректирующей (т. е. если меняется, то , иначе ). Здесь вес многочлена, т. е. число его ненулевых коэффициентов, обозначается через . В разделе «Анализ -ошибки линейной сложности последовательности» сначала получим рекуррентную формулу для порождающих многочленов рассматриваемых последовательностей и докажем некоторые вспомогательные утверждения о многочлене корректирующей последовательности. 1. Рекуррентная формула. Обозначим и . Заметим, что индексы в всегда вычисляются по модулю . В оставшейся части статьи значения индексов по модулю будут опускаться, если это не вызовет затруднений. Из формул (1), (2) получаем, что (3) Предварительно докажем две леммы, необходимые для получения рекуррентной формулы. Свойства изучены в [11, 12]. Согласно [12] имеем следующее утверждение. Лемма 1. Пусть определены по формуле (1), и . Тогда 1) ; 2) . Лемма 2. Пусть и , тогда 1) ; 2) ; 3) ; 4) . Доказательство: 1) очевидно, т. к. ; 2) по определению . Так как, по лемме 1, , то 3) воспользовавшись формулой , получаем, что ; 4) по 1) и формуле для видим, что Здесь и , значит . В итоге или Доказательство леммы 2 завершено. Утверждение 1. Пусть – последовательность, определенная по формуле (2). В этом случае для выполняется рекуррентное соотношение Доказательство. Согласно (3) имеем, что В силу леммы 2 получаем, что Из равенства в , опять по лемме 2, видим, что что и требовалось доказать. Заметим, что при это утверждение истинно только для [14]. 2. Оценка -ошибки линейной сложности последовательности. Пусть . В этом подразделе изучим, когда делится на . Предварительно обсудим некоторые леммы. Лемма 3. Пусть для и . Тогда Доказательство. По условию , т. е. для целого Предположим, что для . В этом случае для целого . Тогда и . Так как и , то . Таким образом, для . Далее, пусть и , где , , тогда и для . Следовательно, и делится на . Последнее утверждение невозможно для . Таким образом, для . Так как и , то для . Следствие. Если , то Лемма 4. Если , то Доказательство. Очевидно, что где , как и ранее. Пусть , тогда, по следствию, , и для имеем, что Суммируя, получаем утверждение леммы для . Предположим, что Тогда, опять по следствию 1 видим, что Снова суммируя, получаем утверждение этой леммы для . Лемма 5. Пусть – многочлен, такой что делится на для . Тогда Доказательство. По условию где и , Не нарушая общности, можем предположить, что . Тогда Пусть . Согласно лемме 4 получаем, что и Так как , то Теперь покажем, что существует многочлен , удовлетворяющий условиям леммы, вес которого равен полученной выше оценке. Возьмем Тогда, по лемме 4, Очевидно, что Лемма 5 доказана. Замечание. Для это утверждение доказано в [14] другим способом. Утверждение 2. Пусть . Тогда наименьший возможный вес многочлена равен Доказательство. Из (3) получаем, что (4) Будем доказывать это утверждение методом математической индукции. 1. Пусть . В этом случае Ясно, что тогда . 2. Предположим, что утверждение истинно для , т. е. существует многочлен с весом такой, что делится на . Тогда делится на и . Далее, предположим, что делится на . Тогда существует многочлен такой, что и . Пусть и . Определим множества , , и . Введем вспомогательные полиномы и . Тогда, согласно (4), Следовательно, и Таким образом, по лемме 5 и индукционному предположению, и . Окончательно, Существование с таким весом ясно из леммы 5. Утвеждение 2 доказано. Доказательство основной теоремы По определению справедливо следующее разложение где . Многочлены неприводимы над , когда – первообразный корень по модулю [17]. 1) Рассмотрим случай, когда . По утверждению 2 здесь для любого с весом . Таким образом, в силу утверждения 1, исследование сводится к изучению . Если делится на , тогда, по утверждению 1, видим, что делит , и наоборот. Отсюда получаем, что для . 2) Если , тогда и . 3) Пусть . Тогда, по утверждению 2, имеем многочлен с весом такой, что делится на . Утверждение 4) очевидно. Заключение Исследована k-ошибка линейной сложности q-ичных последовательностей, полученных из новых обобщенных циклотомических классов по модулю, равному степени нечетного простого числа, когда q – примитивный корень по этому модулю. Получены рекуррентное соотношение и оценка для k-ошибки линейной сложности последовательностей. Результаты показывают, что k-ошибка линейной сложности рассматриваемых последовательностей существенно не уменьшается при . Исследование обобщает результаты для бинарного случая, полученные ранее.