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