Russian Federation
The article presents the analysis of the linear complexity of periodic q-ary sequences when changing k of their terms per period. Sequences are formed on the basis of new generalized cyclotomy modulo equal to the degree of an odd prime. There has been obtained a recurrence relation and an estimate of the change in the linear complexity of these sequences, where q is a primitive root modulo equal to the period of the sequence. It can be inferred from the results that the linear complexity of these sequences does not sign ificantly decrease when k is less than half the period. The study summarizes the results for the binary case obtained earlier.
k-error of linear complexity, cyclotomy, q-ary sequences
Введение Элементарная теория чисел, в частности циклотомия, применяется в теории кодирования и криптографии, при построении разностных множеств и формировании последовательностей. Циклотомические классы определяются как классы смежности подгруппы мультипликативной группы обратимых элементов кольца классов вычетов по модулю . Для составного они называются обобщенными циклотомическими классами. Циклотомические и обобщенные циклотомические классы применяются при определении последовательностей. С криптографической точки зрения циклотомические и обобщенные циклотомические последовательности изучались в [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-ошибка линейной сложности рассматриваемых последовательностей существенно не уменьшается при . Исследование обобщает результаты для бинарного случая, полученные ранее.
1. Cusick T., Ding C., Renvall A. Stream Ciphers and Number Theory. Elsevier Science, 2004. 446 p.
2. Ding C., Helleseth T. New generalized cyclotomy and its applications. Finite Fields and Their Applications, 1998, vol. 4 (2), pp. 140-166.
3. Ye Z., Ke P., Wu C. A further study of the linear complexity of new binary cyclotomic sequence of length pn. AAECC, 2019, vol. 30, no. 3, pp. 217-223.
4. Gantmakher V. E., Bystrov N. E., Chebotarev D. V. Shumopodobnye signaly. Analiz, sintez, obrabotka [Pseudonoise signals. Analysis, synthesis, processing]. Saint-Petersburg, Nauka i tekhnika Publ., 2005. 400 p.
5. Du X., Chen Z. A generalization of the Hall’s sextic residue sequences. Information Sciences, 2013, vol. 222, pp. 784-794.
6. Edemskiy V. About computation of the linear complexity of generalized cyclotomic sequences with period pn+1. Designs, Codes and Cryptography, 2011, vol. 61, no. 3, pp. 251-260.
7. Kim Y. J., Song H. Y. Linear complexity of prime n-square sequences. 2008 IEEE International Symposium on Information Theory (Toronto, Ontario, Canada, July 6-11, 2008). Google Scholar, 2008. Pp. 2405-2408.
8. Wu C., Chen Z., Du X. The linear complexity of q-ary generalized cyclotomic sequences of period pm. Journal of Wuhan University, 2013, vol. 59, no. 2, pp. 129-136.
9. Yan T., Li S., Xiao G. On the linear complexity of generalized cyclotomic sequences with the period pm. Applied Mathematics Letters, 2008, vol. 21, no. 2, pp. 187-193.
10. Zeng X., Cai H., Tang X., Yang Y. Optimal frequency hopping sequences of odd length. IEEE Transactions on Information Theory, 2013, vol. 59, no. 5, pp. 3237-3248.
11. Xiao Z., Zeng X., Li C., Helleseth T. New generalized cyclotomic binary sequences of period p2. Designs, Codes and Cryptography, 2018, vol. 86, no. 7, pp. 1483-1497.
12. Edemskiy V., Li C., Zeng X., Helleseth T. The linear complexity of generalized cyclotomic binary sequences of period pn. Designs, Codes and Cryptography, 2019, vol. 87, no. 5, pp. 1183-1197.
13. Stamp M., Martin C. An algorithm for the k-error linear complexity of binary sequences with period 2n. IEEE Transactions on Information Theory, 1993, vol. 39, no. 4, pp. 1398-1401.
14. Chen Z., Edemskiy V., Ke P., Wu C. On k-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, vol. 12, no. 4, pp. 805-816.
15. Edemskiy V., Sokolovskiy N. The linear complexity of new q-ary generalized cyclotomic sequences of period pn. MATEC Web of Conferences, 2019, vol. 292, 02001.
16. Aierlend K., Rouzen M. Klassicheskoe vvedenie v sovremennuiu teoriiu chisel [Classical principles of modern theory of numbers]. Moscow, Mir Publ., 1987. 416 p.
17. Lidl R., Niderraiter G. Konechnye polia [Finite fields]. Moscow, Mir Publ., 1988. 820 p.
