Линейная сложность циклотомических последовательностей
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 |