ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 56

2020

Вып. 4

УДК 621.391 : 519.714.5

И.В. Чередник

ОСОБЕННОСТИ p-ЛИНЕЙНОГО РАЗЛОЖЕНИЯ p-ЛИНЕЙНЫХ ФУНКЦИЙ

В ТЕРМИНАХ ОПЕРАЦИИ СДВИГ-КОМПОЗИЦИИ

Исследуется операция сдвиг-композиции дискретных функций, которая воз-

никает при гомоморфизмах конечных регистров сдвига. Доказано, что при про-

стом p в классе всех функций, линейных по крайним переменным, для p-линей-

ных функций совпадают понятия приводимости и p-линейной приводимости.

Кроме того, показано, что линейная функция, неприводимая в классе всех ли-

нейных функций, не имеет p-линейных делителей, биективных по крайней пра-

вой переменной, а в некоторых случаях и вовсе не имеет p-линейных делителей.

Ключевые слова: регистр сдвига, гомоморфизмы регистров сдвига, сдвиг-ком-

позиция, конечные поля, p-линейные функции, разложение матричных много-

членов, скрученные многочлены, скрученные линейные рекуррентные последо-

вательности.

DOI: 10.31857/S0555292320040063

§ 1. Введение

Пусть F_q - конечное поле из q = p^t элементов, F_q(n) = {f | f : F^nq → F_q} -⋃

множество всех F_q-значных функций от n переменных, F_q =

F_q(n).

n≥0

В работах отечественных криптографов К.Г. Таболова, А.Я. Прососова, В.А. Ба-

шева, В.И. Солодовникова и др. была введена и исследована (преимущественно

в терминах гомоморфизмов регистров сдвига) операция сдвиг-композиции (⊳-умно-

жения) на множестве всех функций F_q:

∀f ∈ F_q(n + 1) ∀g ∈ F_q(m + 1)

(

)

(f ⊳ g)(x₀, . . . , xn+m) = f

g(x₀, . . . , x_m), . . . , g(x_n, . . . , xn+m)

В работах перечисленных выше авторов в разной степени общности и направлен-

ности достаточно подробно исследована связь между представлением функции h

в виде h = f ⊳ g и существованием гомоморфизма регистра сдвига, внутреннее

функционирование которого определяется функцией h, на регистр сдвига, внутрен-

нее функционирование которого определяется функцией f (функция g из разложе-

ния h = f ⊳ g определяет характер гомоморфизма регистров сдвига). Все основные

достижения в данной области единым образом изложены в монографии [1], мы лишь

кратко перечислим результаты, полученные в направлении декомпозиции функций

относительно операции ⊳-умножения.

В работе [2] описаны все возможные представления произвольной функции h ∈ F_q

в виде h = l ⊳ g, где l - линейная над F_q функция. Это достижение позволяет

указать все возможные гомоморфизмы произвольного регистра сдвига на регистры

сдвига с линейной обратной связью.

В работе [3] описаны все возможные представления произвольной функции h ∈ F_q

в виде h = f ⊳ l, где l - линейная над F_q функция. Кроме того, изучена возмож-

ность представления произвольной функции h ∈ F_q в виде f = l₁ ⊳ g ⊳ l₂, где l₁, l₂ -

линейные над F_q функции.

В работе [4] в терминах операции сдвиг-композиции исследуется возможность ле-

вого линейного разложения системы функций. Как оказалось, подобные разложения

кроме стандартных приложений, связанных с гомоморфизмами регистров сдвига

(см. [1]), обнаруживают очень интересное применение в вычислении представления

произвольной функции h ∈ F_q в виде h = f ⊳ g, где f - p-линейная функция (линей-

ная над F_p). Здесь стоит отметить, что предложенный в работе [4] метод позволяет

эффективно выделять максимальный левый p-линейный ⊳-делитель у произвольной

p-нелинейной функции, но не пригоден для построения нетривиального p-линейного

⊳-разложения p-линейной функции. Последняя задача по существу является пере-

формулировкой классической проблемы факторизации многочленов над кольцом

матриц и, очевидно, крайне сложна.

В данной статье мы представляем два нетривиальных результата о p-линейных

разложениях p-линейных функций, которые кроме теоретической ценности описа-

ния возможных гомоморфизмов регистров сдвига также имеют большое значение

при исследовании факторизации многочленов над кольцом матриц и, соответствен-

но, при построении практически значимых классов скрученных линейных рекур-

рентных последовательностей (см. [5]).

§ 2. Постановка задачи

1. Следуя терминологии работ [1,2,6,7], регистром сдвига длины n над полем F_q

с функцией обратной связи ϕ ∈ F_q(n + 1) и выходной функцией ψ ∈ F_q(n + 1) будем

называть автомат

R(ϕ, ψ) = (F_q, F^nq, F_q, h, f),

у которого функции переходов и выходов определяются равенствами

h((x₁, . . . , x_n), x) = (x₂, . . . , x_n, ϕ(x₁, . . . , x_n, x)),

f ((x₁, . . . , x_n), x) = ψ(x₁, x₂, . . . , x_n, ϕ(x₁, . . . , x_n, x)).

Нетрудно видеть, что биективность функции обратной связи ϕ по первой пе-

ременной равносильна регулярности регистра сдвига R(ϕ, ψ) - при любом входном

символе частичная функция переходов h_x автомата R(ϕ, ψ) является биекцией. Кро-

ме того, биективность каждой из функций ϕ и ψ по последней переменной является

необходимым и достаточным условием для обратимости автомата R(ϕ, ψ). В связи с

отмеченными особенностями при реализации регистров сдвига на практике преиму-

щественно используются функции обратной связи, биективные по первой и (или)

последней переменным, и выходные функции, биективные по последней переменной

(см. [1, 2, 7]). Здесь стоит отметить, что наиболее простыми в реализации и, соот-

ветственно, наиболее распространенными на практике функциями, биективными по

какой-либо переменной, являются функции, линейные по указанной переменной.

Множество всех F_q-значных функций, биективных по первой (последней) пере-

менной, будем обозначать через^∗F_q (F^∗q), а множество всех F_q-значных функций,

линейных по первой (последней) переменной, - через⁺F_q (F+q). При этом естествен-

ными будут производные обозначения

^∗F^∗q =^∗F_q ∩ F^∗q,

^∗F+q =^∗F_q ∩ F+q,

⁺F^∗q =⁺F_q ∩ F^∗q,

⁺F+q =⁺F_q ∩ F+q.

2. Как известно (см. [8]), каждая функция f(x₀, . . ., x_n) ∈ F_q единственным об-

разом представляется приведенным многочленом из F_q[x₀, x₁, . . .]:

∑

f (x₀, . . . , x_n) =

ci0...in x00 . . . xnn .

i0,...,in∈0,q-1

При проведении некоторых исследований относительно функций из F_q часто быва-

ет удобным вести изложение на языке соответствующих приведенных многочленов

из F_q[x₀, x₁, . . .], которые в отличие от функций определяются от общего набора

переменных x₀, x₁, . . .

Множество всех приведенных многочленов из F_q[x₀, x₁, . . .] относительно опе-

раций сложения и умножения с последующим приведением результата по модулю

идеала (x^qi - x_i | i ∈ N₀) образует коммутативное кольцо с единицей. Кроме того,

на множестве всех приведенных многочленов из F_q[x₀, x₁, . . .] корректно определить

операцию сдвиг-композиции (⊳-умножения):

(

)

^def= f

g(x₀, . . . , x_m), . . . , g(x_n, . . . , xn+m)

mod (x^qi - x_i | i ∈ N₀).

Нетрудно видеть, что множество всех приведенных многочленов из F_q[x₀, x₁, . . .]

относительно операции ⊳-умножения образует полугруппу с нейтральным элемен-

том x₀.

3. Как известно, существует несколько подходов к определению степени нелиней-

ности отображения над конечным полем F_q (см. [9, 10]). Наиболее простой состоит

в том, что под степенью нелинейности функции f ∈ F_q понимается степень соответ-

ствующего приведенного многочлена из F_q[x₀, x₁, . . .]. При таком подходе линейны-

ми называют функции, приведенные многочлены которых имеют вид

β₀x₀ + . . . + β_nx_n ∈ F_q[x₀, x₁, . . .].

Однако в случае q = p^t на практике зачастую гораздо более плодотворным оказыва-

ется другой подход к определению степени нелинейности, который учитывает более

общую линейность отображения f ∈ F_q над подполем F_p.

Если функция f(x₀, . . . , x_n) ∈ F_q задана приведенным многочленом

∑

f (x₀, . . . , x_n) =

ci0...in x00 . . . xnn ,

i0,...,in∈0,q-1

то индексом p-нелинейности функции f называют величину

{

}

ind_p f = max

∥i₀∥_p + . . . + ∥i_n∥_p : i₀, . . ., i_n = 0, q - 1, ci0...in = 0

(1)

где ∥j∥_p = j₀ +j₁ +. . .+jt-1 - p-ичный вес числа j = j₀ +pj₁ +. . .+pt-1jt-1 ∈ 0, q - 1.

С другой стороны, если зафиксировать некоторый базис α₁, . . . , α_t простран-

ства F_q над F_p, то каждый аргумент x_i функции f(x₀, . . . , x_n) можно представить

в виде

x_i = α₁xi1 + . . . + α_tx_it, x_ij ∈ F_p,

а саму функцию f(x₀, . . . , x_n) отождествить с набором p-значных координатных

функций

f₁(x₀₁, . . . , x0t, . . . , xn1, . . ., x_n,t),

f_t(x₀₁, . . . , x0t, . . . , xn1, . . ., x_n,t),

который удовлетворяет соотношению f = α₁f₁ + . . . + α_tf_t. В таком случае индекс

p-нелинейности функции f согласно [9] можно вычислить по формуле

ind_p f = max{deg f₁, . . . , deg f_t}.

(2)

Здесь стоит отметить, что в случае простого p индекс p-нелинейности функции

f ∈ F_q совпадает с ее аддитивным показателем нелинейности dlf. Изящное акси-

оматическое изложение аддитивного подхода к измерению степени нелинейности,

а также сравнение данного подхода с классическим, можно найти в работах [10,11].

Так, в работе [10] доказано, что при простом p аддитивный показатель dl f степени

нелинейности функции f ∈ F_p совпадает с классическим показателем deg f, а для

произвольной функции f ∈ F_q ее аддитивный показатель нелинейности можно вы-

числять различными способами в зависимости от представления функции f:

dl f = max{dl f₁, . . . , dl f_t} = max{deg f₁, . . . , deg f_t} = ind_p f.

Функцию f ∈ F_q будем называть p-линейной, если ind_p f = 1 и f(0, . . . , 0) = 0.

Согласно (1) функция f(x₀, . . . , x_n) ∈ F_q является p-линейной в том и только том

случае, когда она представляется приведенным многочленом вида

(

)

(

)

+...+

∈ F_q[x₀,x₁,...],

β₀₁x₀ + . . . + β0txpt-10

βn1x_n + . . . + β_ntxpt-1n

при этом ее координатные функции f₁, . . . , f_t ввиду (2) представляются многочле-

нами вида

a⁽¹⁾⁰¹x₀₁ + . . . + a(1)0tx0t + . . . + a(1)n1xn1 + . . . + a(1)n,tx_n,t ∈ F_p[x₀₁, . . ., x0t, x₁₁, . . .],

a(t)01x₀₁ + . . . + a(t)0tx0t + . . . + a(t)n1xn1 + . . . + a(t)n,tx_n,t ∈ F_p[x₀₁, . . ., x0t, x₁₁, . . .].

Множество всех p-линейных функций из F_q будем обозначать через L^pq. Заметим, что

в данной терминологии классические линейные функции из F_q являются q-линей-

ными, т.е. L_q = L^qq. Напомним, что многочлены вида β₁x + . . . + β_txpt-1 ∈ F_q[x] опи-

сывают все линейные преобразования пространства F_q над полем F_p и называются

p-линеаризованными многочленами (см. [8]). Соответственно, все p-линеаризован-

ные многочлены вида

(

)

(

)

β₀₁x₀ + . . . + β0txpt-10

+...+

βn1x_n + . . . + β_n,txpt-1n

∈ F_q[x₀,x₁,...,x_n]

описывают все отображения пространства Fn+1q в F_q, линейные над F_p.

4. Множество L_q[x₀, x₁, . . .] всех линейных, но не аффинных многочленов над F_q

β₀x₀ + . . . + β_nx_n ∈ F_q[x₀, x₁, . . .]

относительно операций сложения и ⊳-умножения образует коммутативное кольцо,

а отображение

β₀x₀ + . . . + β_nx_n → β₀x⁰ + . . . + β_nxⁿ

является изоморфизмом колец (L_q[x₀, x₁, . . .], +, ⊳)= (F_q[x], +, · ) (см. [1, 2, 7]).

Рассмотрим теперь множество L^pq[x₀, x₁, . . .] всех p-линеаризованных многочле-

нов из F_q[x₀, x₁, . . .]. Множество всех p-линеаризованных многочленов из F_q[x] от-

носительно операций сложения и композиции образует кольцо, изоморфное кольцу

EndFp F_q всех линейных преобразований пространства F_q над F_p. Указанный изо-

морфизм

β₁x + . . . + β_txpt-1 → B

естественным образом индуцирует отображение

(

)

(

)

+...+

→B₀ +...+B_nXⁿ,

β₀₁x₀ + . . . + β0txpt-10

βn1x_n + . . . + β_n,txpt-1n

являющееся изоморфизмом колец (L^pq[x₀, x₁, . . .], +, ⊳)= ((EndFp F_q)[X], +, · ). Отме-

тим, что кольцо ((EndFp F_q)[X], +, · ) известно как кольцо скрученных многочленов

и является базовым объектом исследований в теории скрученных линейных рекур-

рентных последовательностей (см. [5, 12]).

Элементы кольца EndFp F_q наиболее естественно представлять матрицами разме-

ра t×t над полем F_p. Поэтому всюду далее в данной статье мы будем рассматривать

кольцо скрученных многочленов ((EndFp F_q)[X], +, · ) в матричном представлении

((F_p)_t×t[X], +, · ), подразумевая при этом известный изоморфизм

((F_p)_t×t[X], +, · )= ((F_p[x])_t×t, +, · ).

5. Будем говорить, что функция g делит справа функцию h, если существует

функция f, для которой выполняется равенство h = f ⊳g; при этом будем говорить,

что функция f делит функцию h слева. Произвольная h ∈ F_q делится слева и справа

на обратимые элементы моноида (F_q, ⊳):

h = g ⊳ (g-1 ⊳ h), h = (h ⊳ g-1) ⊳ g,

подобные разложения будем называть несобственными. Если функция h допускает

собственное разложение h = f ⊳ g, то будем говорить, что h приводима, а функции

f и g будем называть собственными левым и правым делителями функции h.

Следуя [3], определим один параметр, который естественным образом характе-

ризует размер функции. Если функция f(x₀, . . . , x_n) зависит существенным образом

только от переменных xi0, . . ., x_i

, 0 ≤ i0 < ... < ik ≤ n, то величину lenf = ik - i0

будем называть длиной функции f. Длины постоянных функций по определению

полагаем равными -∞. Введенный параметр удачно согласуется с операцией сдвиг-

композиции:

len(f ⊳ g) ≤ len f + len g;

более того, при естественных с практической точки зрения ограничениях f ∈^∗F^∗q

или g ∈^∗F^∗q указанное неравенство обращается в равенство (см. [3, утверждение 3]).

Разложение h = f ⊳ g, в котором len f < len h и len g < len h, будем называть

существенным, при этом функции f и g будем называть существенными левым и

правым делителями функции h.

С практической точки зрения исследования гомоморфизмов регистров сдвига су-

щественность соответствующих разложений (см. [2, теорема 1]) означает, что гомо-

морфный образ регистра сдвига является регистром сдвига меньшей длины. Здесь

стоит отметить также, что наличие собственных разложений еще не гарантирует

возможность их применения при решении практической задачи построения гомо-

морфизма регистра сдвига на регистр сдвига меньшей длины. Так, например, над

полем F₄ = {0, 1, α, α + 1} линейная функция x₀ + x₁ допускает собственное разло-

жение

(

)

(

)

x₀ + x₁ =

x₀ + (α + 1)x₁ + αx²¹

⊳

x₀ + αx₁ + αx²¹

в котором длины компонент разложения совпадают с длиной исходной функции.

Замечание 1. Вообще говоря, существенное разложение необязательно является

собственным и, наоборот, собственное разложение не всегда существенно. Однако

при рассмотрении класса^∗F^∗q, который относительно операции сдвиг-композиции

образует полугруппу, понятия собственного и существенного разложений совпада-

ют, поскольку множество всех обратимых элементов моноида (^∗F^∗q, ⊳) совпадает

с множеством всех его элементов длины 0.

Замечание 2. Нетрудно видеть, что множество

F_q всех функций из F_q, сохраня-

ющих константу 0, замкнуто относительно операции сдвиг-композиции и образует

полугруппу. Для произвольной функции f ∈ F_q, f(0, . . . , 0) = c_f существует тесная

связь между приводимостью f в F_q и приводимостью

f =f-c_f в

F_q:

f = g ⊳ h ⇐⇒

f =(x₀ -c_f)⊳g⊳(x₀ +c_h)⊳^h=g₁ ⊳h, g₁,h∈

F_q.

Таким образом, исследование приводимости в моноиде (F_q, ⊳) сводится к иссле-

дованию приводимости в подмоноиде

F_q, ⊳). В дальнейшем в данной статье без

ограничения общности рассматривается приводимость в рамках

F_q, даже если это

не оговаривается явным образом.

6. В работе [4] предложен эффективный алгоритм выделения максимального ле-

вого существенного p-линейного делителя у произвольной p-нелинейной функции h:

h = f ⊳ g, f ∈ L^pq, leng минимально возможная.

К сожалению, указанный алгоритм не пригоден даже для вычисления собственного

разложения p-линейной функции - результатом применения данного метода к p-ли-

нейной функции h будет тривиальное разложение h = h ⊳ x₀. Задача нахождения

p-линейных разложений p-линейных функций по существу эквивалентна построе-

нию ⊳-разложений p-линеаризованных многочленов в кольце (L^pq[x₀, x₁, . . .], +, ⊳)

и фактически является переформулировкой классической проблемы о факториза-

ции многочленов над кольцом матриц - по-видимому, на текущий момент данная

проблема не имеет простого алгебраического решения.

В данной статье представлены два нетривиальных результата о p-линейных раз-

ложениях p-линейных функций, которые кроме теоретической ценности также име-

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

сов скрученных линейных рекуррентных последовательностей (см. [5]). Исследова-

ние приводимости проводится в естественных практических рамках поиска суще-

ственных разложений, в которых обе компоненты линейны (биективны) по крайней

правой переменной.

Операция сдвиг-композиции обладает определенной симметричностью, а потому

для краткости формулирования результатов и удобства проведения соответствую-

щих доказательств мы будем рассматривать множества^∗F_q и⁺F_q, хотя естественно,

что все утверждения остаются верными и для множеств F^∗q и F+q.

§3. p-линейная приводимость линейных функций

Как было отмечено выше, множество всех линейных многочленов L_q[x₀, x₁, . . .]

относительно операций сложения и сдвиг-композиции образует кольцо, изоморфное

кольцу многочленов F_q[x]. Таким образом, исследование приводимости классиче-

ской линейной функции в классе L_q эквивалентно известной проблеме факториза-

ции многочленов над конечным полем F_q (см., например, [8]).

Поскольку L_q ⊊ L^pq, то очевидно, что для классической линейной функции по-

нятие p-линейной приводимости в классе L^pq является более широким по сравнению

с линейной приводимостью в классе L_q. Для удобства и наглядности исследование

p-линейной приводимости классических линейных функций будем проводить в мат-

ричном представлении, подразумевая ранее отмеченные изоморфизмы

(L^pq[x₀, x₁, . . .], ⊳, +)= ((EndFp F_q)[X], +, · )= ((F_p)_t×t[X], +, · )= ((F_p[x])_t×t, +, · ).

В матричной терминологии исследование p-линейной приводимости классической

линейной функции h ∈ L_q фактически означает исследование приводимости соот-

ветствующего многочлена h(x) ∈ F_q[x] в кольце многочленов (F_p)_t×t[X].

Напомним, как устроено естественное вложение F_q[x] → (F_p)_t×t[X]. Выберем про-

извольный неприводимый над F_p многочлен χ(x) ∈ F_p[x] степени t. Как известно,

многочлен χ(x) имеет в поле F_q корень α и F_q = F_p(α). При выборе произвольной

матрицы S ∈ (F_p)_t×t с характеристическим многочленом χ(x) корректно определить

отображение

r₀ + r₁α + . . . + rt-1αt-1 → r₀E + r₁S + . . . + rt-1St-1,

(3)

являющееся изоморфизмом полей

F_q = F_p(α)= F_p(S) = {r₀E + r₁S + . . . + rt-1St-1 : r₀, r₁, . . ., rt-1 ∈ F_p}.

Данный изоморфизм полей естественным образом продолжается до изоморфизма

колец многочленов F_p(α)[x]= F_p(S)[X], при котором многочлену

∑

h(x) = h₀ + . . . + hn-1xn-1 + h_nxⁿ ∈ F_p(α)[x], h_i =

rij α^j ,

0 ≤ i ≤ n,

j=0

ставится в соответствие многочлен

∑

H (X) = H₀ + . . . + Hn-1Xn-1 + H_nXⁿ ∈ F_p(S)[X], H_i = r_ij S^j,

0 ≤ i ≤ n.

j=0

Таким образом, установлено вложение F_q[x] → (F_p)_t×t[X] (здесь стоит отметить, что

данное вложение не является единственным, но все подобные вложения сопряжены).

Теперь можно сформулировать и доказать центральный результат данного па-

раграфа.

Теорема 1. Пусть многочлен h(x) ∈ F_q[x] неприводим над F_q. Тогда H(X) не

имеет собственных унитарных делителей в кольце (F_p)_t×t[X]. Если к тому же

h(x) ∈ F_pl [x] при всех l < t, то H(X) вообще не имеет собственных делителей

в (F_p)_t×t[X].

Доказательство. Для удобства будем полагать, что h(x) ∈ F_q[x] - унитарный

многочлен степени n. При проведении доказательства будем использовать вложение

F_q[x] → (F_p)_t×t[X], которое определялось ранее с помощью отображения (3).

Неприводимый многочлен χ(x) ∈ F_p[x] в расширении F_q = F_p(α) имеет t раз-

личных корней α, . . . , αpt-1 , и как известно из курса линейной алгебры, существует

обратимая матрица C ∈ (F_q)_t×t, такая что C-1SC = diag(α, . . . , αpt-1 ). На самом де-

ле сопряжение указанной матрицей C приводит к диагональному виду все матрицы

из F_p(S):

C-1(r₀E + r₁S + . . . + rt-1St-1)C = . . . =

(

)

= diag

r₀ + r₁α + . . . + rt-1αt-1, . . ., r₀ + r₁αpt-1 + . . . + rt-1(αpt-1 )t-1

(

)

= diag

β, . . . , βpt-1

∈ (F_q)_t×t.

Предположим, что многочлен H(X) допускает в кольце (F_p)_t×t[X] собственное

разложение:

H (X) = F (X) · G(X), det F (x) = 1, det G(x) = 1.

Тогда при сопряжении обеих частей данного равенства матрицей C получим соот-

ношение

F₁(X) · G₁(X) = (C-1F(X)C) · (C-1G(X)C) = C-1h(X)C =

((

)

(

)

∑

=C-1

r0jSj

+...+

rn-1j

S^j Xn-1 + Xⁿ C =

j=0

(

)

∑

(

)

pt-1j

r0j, diag

α^j, . . ., α

+...+

j=0

(

)

∑

(

)

pt-1j

rn-1j diag

α^j, . . . , α

Xn-1 + Xⁿ =

j=0(

)

xn-1 + xⁿ

−1

(

)

= diag h(x), . . . , h(pt-1)(x)

Если l ∈ N - наименьшее со свойством h(x) ∈ F_pl[x], то t = lm и (m, n) = 1.

Кроме того, h(pl+s) = h(ps), s ∈ N₀, и следовательно,

(

)

(

)

diag h(x), . . . , h(pt-1)(x)

= diag h(x), . . . , h(pl-1)(x), . . . , h(x), . . . , h(pl-1)(x)

Теперь в равенстве

(

)

F₁(x) · G₁(x) = diag h(x), . . . , h(pl-1)(x), . . . , h(x), . . . , h(pl-1)(x)

вычислим определители обеих частей:

det F₁(x) · det G₁(x) = h(x)^m · . . . · h(pl-1)(x)^m.

Из единственности канонического разложения следует, что

det G₁(x) = h(x)m0 · . . . · h(pl-1)(x)ml-1 .

Поскольку detG₁(x) = detG(x) ∈ F_p[x], а h(x), . . . , h(pl-1)(x) ∈ F_pl [x] - все много-

члены, сопряженные с h(x) над F_p, то на самом деле m₀ = . . . = ml-1:

(

)m0

(

)

det G₁(x) = h(x) · . . . · h(pl-1)(x)

deg

det G₁(x)

= nlm₀.

Если G(X) - унитарный многочлен степени k, то G₁(X) = C-1G(X)C - унитар-

ный многочлен той же степени k, и следовательно, det G₁(x) - унитарный многочлен

степени kt. В таком случае справедливы равенства

(

)

deg

det G₁(x)

= kt = klm = nlm₀,

из которых ввиду взаимной простоты (m, n) = 1 следует, что n | k. Таким образом,

deg G(X) = k = n = deg H(X), и соответственно, G(X) = H(X).

Если h(x) ∈ F_pl[x] при всех l < t, то многочлен h(x) · . . . · h(pt-1)(x) является

неприводимым над F_p многочленом (степени nt), что противоречит системе условий

det F₁(x) · det G₁(x) = h(x) · . . . · h(pt-1)(x), det F₁(x) = 1, det G₁(x) = 1.

▴

Напомним, что произвольная p-линейная функция f(x₀, . . . , x_n) ∈ L^pq задается

соответствующим p-линеаризованным многочленом

(

)

(

)

β₀₁x₀ + . . . + β0txpt-1

+...+ βn1x_n +...+β_n,txpt-1

которому при изоморфизме (L^pq[x₀, x₁, . . .], ⊳, +)

= ((F_p)_t×t[X], +, · ) сопоставляет-

ся многочлен B₀ + . . . + B_nXⁿ. При этом, очевидно, линейным по крайней правой

переменной функциям из L^pq соответствуют унитарные многочлены из (F_p)_t×t[X].

Следствие 1. Пусть h ∈ L_q - функция, неприводимая в классе L_q. Тогда h

не допускает собственного (и следовательно, существенного) разложения в сдвиг-

композицию p-линейных функций, одна из которых линейна по крайней правой пе-

ременной.

Если к тому же h ∈ L_pl при всех l < t, то h(x) вообще не допускает собствен-

ного разложения в сдвиг-композицию p-линейных функций.

В заключение параграфа приведем несколько примеров, наглядно демонстриру-

ющих качественное расширение понятия p-линейной приводимости по сравнению с

классической линейной приводимостью. Для простоты изложения в примерах пред-

варительно будет рассмотрено матричное представление.

Пример 1. Рассмотрим неприводимый над полем F₄ = {0,1,α,α+1} многочлен

h(x) = 1 + x + x³. Согласно доказанной теореме 1 многочлен H(X) = E + X + X³ не

имеет унитарных делителей в кольце (F₂)2×2[X]. Однако H(X) допускает собствен-

ное разложение в кольце (F₂)2×2[X]:

(

)

(

)

(

)

H (X) = E + X + X³ =

X+

X³ =

(

)

1+x+x³

⁽1

⁽1 + x x⁾

1+x+x³

x²

1+x

x²

(₍

)

(

)

(

)

(₍

)

(

)

(

)

X+

X²

X+

X²

Таким образом, линейная функция x₀ + x₁ + x₃, неприводимая в классе L₄, до-

пускает над F₄ существенное и собственное 2-линейное разложение

(

)

x₀ + x₁ + x₃ =

x₀ + (α + 1)x₁ + (α + 1)x²¹ + x₂ + (α + 1)x²²

⊳

(

)

⊳

x₀ + αx₁ + (α + 1)x²¹ + x₂ + (α + 1)x²²

Пример 2. Многочлен h(x) = 1+x²+x⁴ над полем F₄ = {0,1,α,α+1} раскла-

дывается на линейные множители:

h(x) = (α + x)² · ((α + 1) + x)².

При этом для многочлена H(X) = E + X² + X⁴ в кольце (F₂)2×2[X] можно указать

разложение

(

)

) (

(

)

H (X) = E +

X+X²

· E+

X+X²

в котором каждый сомножитель не имеет корней в (F₂)2×2, и следовательно, не

имеет унитарных делителей в (F₂)2×2[X].

Таким образом, для линейной функции x₀ + x₂ + x₄ над полем F₄ в дополнение

к каноническому линейному разложению

(

)

(

)

x₀ + x₂ + x₄ = (αx₀ + x₁) ⊳ (αx₀ + x₁) ⊳

(α + 1)x₀ + x₁

⊳

(α + 1)x₀ + x₁

можно указать нетривиальное 2-линейное разложение

x₀ + x₂ + x₄ = (x₀ + x²¹ + x₂) ⊳ (x₀ + x²¹ + x₂),

в котором каждая из компонент не имеет 2-линейных делителей, линейных по край-

ней правой переменной.

Пример 3. Многочлен h(x) = 1 + x + x³ + x⁴ над полем F₄ = {0,1,α,α + 1}

раскладывается на линейные множители:

h(x) = (1 + x)² · (α + x) · ((α + 1) + x).

При этом для многочлена H(X) = E + X + X³ + X⁴ в кольце (F₂)2×2[X] можно

указать дополнительные разложения:

(

)

) (

(

)

H (X) = E +

X+X²

· E+

X+X²

(

)

(

)

1+x+x²

1+x²

1+x+x²

(

)

) (

(

)

H (X) = E +

X+X²

· E+

X+X²

(

)

(

)

1+x+x²

1+x²

1+x+x²

в которых каждый из сомножителей не имеет корней в (F₂)2×2, и следовательно, не

имеет унитарных делителей в (F₂)2×2[X].

Таким образом, над полем F₄ линейная функция x₀ + x₁ + x₃ + x₄ в дополнение

к каноническому линейному разложению

(

)

x₀ + x₁ + x₃ + x₄ = (x₀ + x₁) ⊳ (x₀ + x₁) ⊳ (αx₀ + x₁) ⊳

(α + 1)x₀ + x₁

обладает нетривиальными 2-линейными разложениями

(

)

(

)

x₀ + x₁ + x₃ + x₄ =

x₀ + (α + 1)x₁ + αx²¹ + x₂

⊳

x₀ + αx₁ + αx²¹ + x₂

(

)

(

)

x₀ + x₁ + x₃ + x₄ =

x₀ + αx₁ + x²¹ + x₂

⊳

x₀ + (α + 1)x₁ + x²¹ + x₂

в которых каждая из компонент не имеет 2-линейных делителей, линейных по край-

ней правой переменной.

§ 4. Приводимость p-линейных функций

В работе [3] доказывается несколько практически значимых результатов о степе-

ни нелинейности сдвиг-композиции функций. Наиболее интересными, на наш взгляд,

являются следующие утверждения.

Теорема 2 [3, теорема 10]. Если p - простое число, то для композиции f ⊳ g

произвольных функций f ∈ F_p и g ∈⁺F_p справедливы следующие утверждения:

1. deg(f ⊳ g) = 1 тогда и только тогда, когда deg f = deg g = 1;

2. deg(f ⊳ g) = 2 тогда и только тогда, когда либо deg f = 1 и deg g = 2, либо

deg f = 2 и deg g = 1.

Здесь стоит отметить, что ядром доказательства теоремы 2 является следующая

лемма, которая и сама по себе представляет интерес.

Лемма 1 [3, лемма 12]. При простом p для любого f ∈ F_p, degf ≥ 2, и любого

g ∈ ⁺F_p выполняется неравенство

deg(f ⊳ g) ≥ deg g + 1.

В работе [3] приведены примеры, показывающие невозможность продолжения

результатов теоремы 2 и леммы 1 на случай непростого поля F_q при использовании

классического подхода к определению степени нелинейности. В данном параграфе

исследуется возможность распространения результатов теоремы 2 и леммы 1 на слу-

чай непростого поля F_q при использовании индекса p-нелинейности, определенного

выше (см. (1) и (2)).

Как показывает следующий пример, результат леммы 1 не допускает обобщения

на случай непростого поля F_q даже при использовании параметра ind_p вместо deg.

Пример 4. Пусть q = p³. Зафиксируем произвольный базис α₁,α₂,α₃ поля F_q

над F_p. Рассмотрим функцию f ∈⁺F+q, определяемую в базисе α₁, α₂, α₃ набором

координатных функций

f₁ = x₀₁ + x₁₂xk+1,2 + x₁₃xk+1,3 + xk+2,1,

f₂ = x₀₂ + xk+1,2,

f₃ = x₀₃ + xk+1,3,

и функцию g ∈⁺F+q, которая в том же базисе α₁, α₂, α₃ определяется набором

координатных функций

g₁ = x₀₁ + x₂₁ · . . . · x2k+1,1 + x2k+3,1,

g₂ = x₀₂ + x₁₁ · . . . · xk1 + x2k+3,2,

g₃ = x₀₂ + xk+3,1 · . . . · x2k+2,1 + x2k+3,3.

Согласно формулам (2) справедливы равенства

ind_p f = max{deg f₁, deg f₂, deg f₃} = 2,

ind_p g = max{deg g₁, deg g₂, deg g₃} = 2k.

При этом нетрудно проверить, что степени координатных функций сдвиг-компози-

ции f ⊳ g удовлетворяют соотношениям

deg(f ⊳ g)₁ = k + 1, deg(f ⊳ g)₂ = k, deg(f ⊳ g)₃ = k,

и следовательно, ind_p(f ⊳ g) = k + 1.

Рассмотренный пример наглядно демонстрирует, что величины

ind_p f = max{deg f₁, . . . , deg f_t}, ind_p g = max{deg g₁, . . . , deg g_t}

невозможно использовать для точной оценки параметра ind_p(f ⊳ g), поскольку зна-

чение ind_p(f ⊳ g) зависит не от максимума степеней координатных функций f и g,

а от сочетаний мономов этих координатных функций.

Кроме того, нетрудно видеть, что пример 4 опровергает возможность непосред-

ственного продолжения результатов леммы 1 и утверждения 2 теоремы 2 (при k = 1)

на случай непростого поля F_q при использовании параметра ind_p. С учетом отмечен-

ного еще более неожиданным представляется тот факт, что утверждение 1 теоремы 2

допускает независимое обобщение на случай непростого поля F_q.

Теорема 3. Пусть q = p^t, где p - простое. Тогда для сдвиг-композиции f ⊳ g

функций f ∈^∗F_q и g ∈⁺F^∗q равенство ind_p(f ⊳ g) = 1 выполняется в том и только

том случае, когда ind_p f = ind_p g = 1.

Доказательство. Содержательную часть доказательства утверждения пред-

ставим в виде двух отдельных результатов, которые сами по себе представляют

практический интерес.

Для удобства будем считать, что функции f(x₀, . . . , x_n) и g(x₀, . . . , x_m) имеют

длины n и m соответственно.

Лемма 2. Пусть q = p^t. Для произвольных f ∈ L^pq и g ∈ F_q справедливы сле-

дующие утверждения:

1. ind_p(f ⊳ g) ≤ ind_p g;

2. ind_p(g ⊳ f) ≤ ind_p g;

3. Если к тому же f ∈^∗L^pq, то ind_p(g ⊳ f) = ind_p g = ind_p(f ⊳ g).

Доказательство. Доказательство утверждений 1 и 2 представляется очевид-

ным при использовании представления функций f, g наборами координатных функ-

ций.

Докажем утверждение 3. Пусть

f (x₀, . . . , x_n) = f₀₀x₀ + . . . + f0,t-1xpt-10 + . . . + fn0xn + . . . + fn,t-1xnt-1 ,

∑

g(x₀, . . . , x_m) =

ci0...im x00 . . . xmm .

i0,...,im∈0,q-1

Условие f ∈^∗L^pq означает, что π(x₀) = f₀₀x₀ + . . . + f0,t-1xpt-10 - перестановочный

p-линеаризованный многочлен. При этом очевидны разложения

f =f^′ ⊳π, f =π⊳f^′′, f^′,f^′′ ∈⁺L^pq.

Пусть xj00 . . . xmm - наименьший относительно стандартного лексикографического по-

рядка моном функции g со свойством

ind_p g = ind_p xj00 . . . xmm = ∥j0∥p + . . . + ∥jm∥p, cj0...jm = 0.

Нетрудно понять, что приведенные многочлены функций g⊳f^′ и f^′′ ⊳g также содер-

жат одночлен cj0...jm x00 . . . xmm . Тогда с учетом утверждений 1 и 2 можно выписать

следующие цепочки неравенств:

ind_p g ≤ ind_p(g ⊳ f^′) = ind_p(g ⊳ f ⊳ π-1) ≤ ind_p(g ⊳ f) ≤ ind_p g,

ind_p g ≤ ind_p(f^′′ ⊳ g) = ind_p(π-1 ⊳ f ⊳ g) ≤ ind_p(f ⊳ g) ≤ ind_p g.

▴

Легко видеть, что достаточность условия, сформулированного в теореме 3, сле-

дует из утверждения 3 доказанной леммы 2.

Для доказательства необходимости нам потребуется еще один вспомогательный

результат.

Лемма 3. Пусть q = p^t, где p - простое, а сдвиг-композиция функций f ∈ F_q

и g ∈ ⁺F^∗q удовлетворяет условию ind_p(f ⊳ g) = 1. Тогда indp f = 1.

Доказательство. Если indp g = 1, то по лемме 2 имеем ind_pf = ind_p(f⊳g) = 1

- все доказано. Поэтому далее будем полагать, что ind_p g > 1 и справедливо пред-

ставление

g = x₀ + l_g(x₁,...,xs-1) + ϕ(x_s,...,x_m),

в котором ind_p l_g = 1, а функция ϕ существенным и p-нелинейным образом зависит

от переменной x_s, s ≤ m.

Доказательство проведем методом от противного. Предположим, что ind_p f > 1.

Представим функцию f в виде

f = l_f(x₀,...,xr-1) + ψ(x_r,...,x_n),

где ind_p l_f = 1, а функция

∑

ψ(x_r , . . . , x_n) =

x^irψ_i(xr+1, . . . , x_n)

i=0

существенным и p-нелинейным образом зависит от переменной x_r, r ≤ n.

Во введенных обозначениях рассмотрим соотношение f ⊳ g подробнее:

f ⊳ g = (l_f ⊳ g)(x₀,...,xr+m-1) +

∑(

)_i

x_r + τ(xr+1, . . ., xr+m)

(ψ_i ⊳ g)(xr+1, . . . , xn+m),

i=0

где

τ (xr+1, . . . , xr+m) = l_g(xr+1, . . . , xr+s-1) + ϕ(xr+s, . . . , xr+m).

Теперь заметим, что равенство ind_p(f ⊳ g) = 1 возможно только лишь в случае,

когда функция l_f ⊳ g зависит p-линейным образом от переменных x₀, . . . , xr-1:

(l_f ⊳ g) (x₀, . . . , xr+m-1) =

∑

= l(x₀, . . . , xr-1) +

x^irϕ_i(xr+1, . . . , xr+m-1), ind_p l = 1.

i=0

Если r = n, то очевидно, что ψ_i ∈ F_q при всех i ∈ {0, . . . , q - 1}. Рассмотрим

случай, когда r < n, и предположим, что существует такой i ∈ {1, . . . , q - 1}, для

которого ψ_i ∈ F_q. Тогда выберем наибольшее k со свойством ψ_k ∈ F_q и продолжим

расписывать соотношение f ⊳ g подробнее:

∑

f ⊳ g = l(x₀,...,xr-1) +

x^irϕ_i(xr+1, . . . , xr+m-1) +

i=0

∑(

)_i

x_r + τ(xr+1, . . . , xr+m)

(ψ_i ⊳ g)(xr+1, . . . , xn+m) +

i=0

(

)_k

x_r + τ(xr+1, . . ., xr+m)

(ψ_k ⊳ g)(xr+1, . . . , xn+m) +

∑

(

)_i

x_r + τ(xr+1, . . . , xr+m)

ψ_i =

i=k+1

∑

= l(x₀, . . . , xr-1) +

x^irϕ_i(xr+1, . . . , xr+m-1) +

i=0

∑(

)_i

x_r + τ(xr+1, . . . , xr+m)

(ψ_i ⊳ g)(xr+1, . . . , xn+m) +

i=0

∑

⁽k⁾

xⁱ

τ (xr+1, . . . , xr+m)^k-i(ψ_k ⊳ g)(xr+1, . . . , xn+m) +

^r i

i=0

∑

+ x^kr(ψ_k ⊳ g)(xr+1,...,xn+m) +

x^irv_i(xr+1, . . . , xr+m).

i=0

Из полученного представления f ⊳ g легко видеть, что равенство ind_p(f ⊳ g) = 1

с необходимостью влечет за собой включение

ϕ_k(xr+1, . . . , xr+m-1) + (ψ_k ⊳ g)(xr+1, . . . , xn+m) + v_k(xr+1, . . ., xr+m) ∈ F_q,

которое невозможно ввиду того, что

(

)

len

ϕ_k(xr+1, . . . , xr+m-1) + v_k(xr+1, . . . , xr+m)

≤m-1<

< m = leng ≤ lenψ_k + leng = len(ψ_k ⊳ g)(xr+1,...,xn+m).

Таким образом, показали, что независимо от r ≤ n для всех i ∈ {1, . . . , q - 1} вы-

полняется включение ψ_i ∈ F_q, а сдвиг-композиция f ⊳ g на самом деле имеет вид

∑

f ⊳ g = l(x₀,...,xr-1) +

x^irϕ_i(xr+1, . . . , xr+m-1) +

i=0

∑

(

)_i

+ (ψ₀ ⊳ g)(xr+1, . . . , xn+m) +

ψ_i ·

x_r + τ(xr+1, . . . , xr+m)

(4)

i=1

Поскольку функция f существенным и p-нелинейным образом зависит от пере-

менной x_r, то существует такое i ∈ {1, . . . , q - 1}, что ψ_i = 0 и ∥i∥_p = 1. Выбе-

рем наибольшее k, у которого ψ_k = 0 и ∥k∥_p - максимально возможный. Пусть

k = k_lp^l + ... + kt-1pt-1, k_l ≥ 1. Обозначим

k(l) = 0 + . . . + 0 + k_lp^l + . . . + kt-1pt-1 = k,

k(l-1) = 0 + . . . + pl-1 + (k_l - 1)p^l + . . . + kt-1pt-1,

k⁽⁰⁾ = p⁰ + . . . + 0 + (k_l - 1)p^l + . . . + kt-1pt-1,

k^∗ = 0 + . . . + 0 + (k_l - 1)p^l + . . . + kt-1pt-1 = 0

∑

(

)_i

и выделим в сумме ψ_i ·

x_r + τ(xr+1, . . ., xr+m)

коэффициент при xk∗r :

i=1

∑

(

)

∑

ψ_i ·

x_r + τ(xr+1, . . ., xr+m)

ⁱ =

ψ_i · (x_r + τ)i0+pi1+...+pt-1it-1 =

i=1

∑

(

)it-1

= ψ_i · (x_r + τ)i0 · (x^pr + τ^p)i1 · ... · xpt-1r + τpt-1

i=1

(

)_k

(

)kt-1

= ψ_k(l) · xplr + τpl

· ... · xpt-1r + τpt-1

(

) (

(

)kl-1

)kt-1

+τpl-1

+ ψ_k(l-1) · xpl-1r

· xplr + τpl

· ... · xpt-1r + τpt-1

(

)kl-1

)kt-1

+ ... + ψ_k(0) · (x_r + τ) · xplr + τpl

· ... · xpt-1r + τpt-1

(

)_k

(

l-1

)kt-1

+ ψ_k∗ ·

+ t(x_r , . . . , xr+m) =

xplr + τpl

· ... · xpt-1r + τpt-1

(

)

(

)

= ψ_k(l) · xk(l)r + klxr∗ τpl + . . .

+ ψ_k(l-1) · xk(l-1)r + xr∗ τpl-1 + . . .

(

)

(

)

+ ψ_k∗ ·

+ t(x_r , . . . , xr+m) =

+ . . . + ψ_k(0) · xk(0)r + xr∗τp0 + . . .

xk∗r + . . .

= ψ_k(l) xk(l)r + ψk(l-1) xr(l-1) + . . . + ψk(0) xr(0) +

(

)

+ k_lψ_k(l) · τpl + ψ_k(l-1) · τpl-1 + . . . + ψ_k(0) · τp0

+ ψ_k∗ xk∗r + v(xr, . . ., xr+m) =

(

)

= k_lψ_k(l) · τpl + ψ_k(l-1) · τpl-1 + . . . + ψ_k(0) · τp0

+ ψ_k∗ xk∗r + w(xr, . . . , xr+m)

(здесь многочлены t(x_r , . . . , xr+m), v(x_r, . . . , xr+m) и w(x_r , . . . , xr+m) не содержат

мономов с переменной x_r в степени k^∗).

Теперь легко видеть, что условие ind_p(f ⊳ g) = 1 накладывает на компоненты

представления (4) следующее ограничение:

(

)

+ ψ_k∗

⊳ τ(xr+1,...,xr+m) ∈ F_q.

ϕ_k∗ (xr+1, . . ., x_m) + k_lψ_k(l) xpl0 + . . . + ψk(0) x00

Однако данное включение невозможно ввиду того, что k_lψ_k(l) = 0 и τ ∈ F^∗q, а сле-

довательно, композиция

(

)

k_lψ_k(l) xpl0 + . . . + ψk(0) x00

+ ψ_k∗

⊳ τ(xr+1,...,xr+m)

существенным образом зависит от xr+m.

Таким образом, ψ_i ∈ F_q для всех i ∈ {1, . . . , q - 1} и неравенство ψ_i = 0 возможно

только при ∥i∥_p = 1 - пришли к противоречию с тем, что функция ψ существенным

и p-нелинейным образом зависит от переменной x_r. ▴

Теперь можно доказать необходимость условия, сформулированного в теореме 3.

Так как p - простое, то согласно доказанной лемме 3 из условия ind_p(f ⊳ g) = 1

следует, что ind_p f = 1. А поскольку f ∈^∗F_q, то согласно утверждению 3 леммы 2

имеем равенство ind_p g = ind_p(f ⊳ g) = 1. ▴

Следствие 2. При простом p регистр сдвига R(ϕ,ψ) с p-линейной функцией

обратной связи ϕ ∈^∗(L^pq)⁺ может допускать гомоморфизм на регистр сдвига

R(ϕ^′, ψ^′), ϕ^′ ∈^∗F+q, только если ϕ^′ - p-линейная; при этом данный гомоморфизм

с необходимостью является p-линейным отображением.

Доказательство очевидным образом следует из [2, теорема 1] и теоремы 3. ▴

Следствие 3. Неавтономный линейный регистр сдвига с неприводимым ха-

рактеристическим многочленом не допускает собственных гомоморфизмов на ре-

гулярные регистры сдвига, функции обратной связи которых линейны по входной

переменной.

Доказательство очевидным образом следует из [2, теорема 1], доказанной

теоремы 3 и следствия 1. ▴

Замечание 3. Ранее отмечалось, что при простом p для произвольной функции

f ∈ F_q ее индекс p-нелинейности indp f совпадает с аддитивным показателем нели-

нейности dl f. Следовательно, теорема 3 - центральный результат данного парагра-

фа - допускает формулировку в терминах показателя dl, не зависящего от числа p.

Таким образом, можно сделать вывод, что аддитивный показатель нелинейности при

исследовании сдвиг-композиции является более органичным продолжением класси-

ческого понятия нелинейности отображения deg на случай непростого поля F_q по

сравнению с индексом p-нелинейности.

В заключение параграфа приведем ряд примеров, которые демонстрируют су-

щественность каждого из условий теоремы 3 и леммы 3.

Пример 5. Пусть q = p² и F_q = F_p(α). Рассмотрим проекцию π: F_q → F_p,

определенную в базисе e, α по правилу

π(x₁ + x₂α) = x₂.

Выберем произвольный нелинейный многочлен σ ∈ F_p[x₁, . . . , x_n]. Нетрудно понять,

что функция ϕ = σ ⊳ π ∈ F_q в базисе e, α имеет координатные функции

ϕ₁(x₁₁, x₁₂, . . ., xn1, xn2) = σ(x₁₂, . . . , xn2), ϕ₂(x₁₁, x₁₂, . . ., xn1, xn2) = 0,

и следовательно, выполняется равенство ind_p ϕ = deg σ > 1.

Сдвиг-композиция

(

)

π⊳

x₀ + ϕ(x₁, . . ., x_n) + xn+1

= π(x₀) + π(xn+1)

доказывает существенность условия f ∈^∗F_q в теореме 3.

Пример 6. В обозначениях примера 5 сдвиг-композиция

(

)

(

)

x₀ + ϕ(x₁, . . ., x_n)

⊳

x₀ - ϕ(x₁, . . . , x_n)

(

)

= x₀ - σ(x₁₂,...,xn2) + σ ⊳ π

x₁ - ϕ(x₂, . . . , xn+1)

= x₀ - σ(x₁₂,...,xn2) + σ(x₁₂,...,xn2) = x₀

подтверждает существенность условия g ∈ F^∗q в лемме 3 и теореме 3.

Кроме того, данный пример показывает, что при составном q обратимые элемен-

ты множества⁺F_q могут иметь произвольные длину и степень нелинейности (см.

следствие 2 в работе [3]).

Пример 7. Условие g ∈⁺F_q в лемме 3 и теореме 3 нельзя заменить даже на

близкое g ∈^∗F_q. Для любого q > 2 существует перестановочный полином f(x₀) ∈ F_q,

ind_p f > 1. Нетрудно понять, что обратный перестановочный полином g(x₀) также

удовлетворяет условию ind_p g > 1. При этом справедливо равенство f ⊳ g = x₀.

СПИСОК ЛИТЕРАТУРЫ

1. Солодовников В.И. Регистры сдвига и криптоалгоритмы на их основе: теоретико-авто-

матные свойства и их приложения. Saarbrücken: Lambert Acad. Publ., 2017.

2. Солодовников В.И. Гомоморфизмы регистров сдвига в линейные автоматы // Дискрет.

матем. 2008. Т. 20. № 4. С. 89-101.

3. Чередник И.В. Линейное разложение дискретных функций в терминах операции сдвиг-

композиции // Матем. вопр. криптогр. 2020. Т. 11. № 1. С. 115-143.

4. Чередник И.В. Линейное разложение системы дискретных функций в терминах опера-

ции сдвиг-композиции // Матем. вопр. криптогр. (в печати).

5. Гольтваница М.А. Методы построения скрученных линейных рекуррентных последо-

вательностей максимального периода, базирующиеся на факторизации многочленов

Галуа в кольце матричных многочленов // Матем. вопр. криптогр. 2019. Т. 10. № 4.

С. 25-51.

6. Башев В.А. Теоретико-групповая характеризация неавтономных линейных регистров

сдвига // Тр. по дискр. матем. Т. 8. М.: Физматлит, 2004. С. 52-68.

7. Солодовников В.И. Гомоморфизмы двоичных регистров сдвига // Дискрет. матем. 2005.

Т. 17. № 1. С. 73-88.

8. Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1, 2. М.: Мир, 1988.

9. Кузьмин А.С., Нечаев А.А., Шишкин В.А. Бент- и гипербент-функции над конечным

полем // Тр. по дискр. матем. Т. 10. М.: Физматлит, 2007. С. 97-122.

10. Черемушкин А.В. Аддитивный подход к определению степени нелинейности дискрет-

ной функции // Прикл. дискр. матем. 2010. № 2 (8). С. 22-33.

11. Черемушкин А.В. Аддитивный подход к определению степени нелинейности дискрет-

ной функции на циклической группе примарного порядка // Прикл. дискр. матем.

2013. № 2 (20). С. 26-38.

12. Гольтваница М.А., Зайцев С.Н., Нечаев А.А. Скрученные линейные рекурренты мак-

симального периода над кольцами Галуа // Фундамент. и прикл. матем. 2012. Т. 17.

№ 3. С. 5-23.

Чередник Игорь Владимирович

Поступила в редакцию

МИРЭА - Российский технологический университет

04.06.2020

(РТУ МИРЭА), Москва

После доработки

p.n.v.k.s@mail.ru

07.11.2020

Принята к публикации

08.11.2020