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

Том 56

2020

Вып. 1

УДК 621.391.1 : 519.7

А.Р. Васин

КУСОЧНО-ПОЛИНОМИАЛЬНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

НАД КОЛЬЦОМ ГАЛУА

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

Галуа, доказывается критерий его полноцикловости. Приводится оценка откло-

нения выходных последовательностей рассматриваемого генератора. Показы-

вается, что полученная оценка асимптотически эквивалентна известным оцен-

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

случаях является асимптотически более точной.

Ключевые слова: кусочно-полиномиальные последовательности, кольцо Галуа,

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

ские суммы.

DOI: 10.31857/S0555292320010088

§ 1. Введение

В настоящее время актуальной математической задачей является задача постро-

ения псевдослучайных последовательностей (ПСП), удовлетворяющих некоторым

заданным свойствам. Одним из важных свойств ПСП с практической точки зре-

ния является “хорошее” распределение ее элементов. Для решения некоторых за-

дач, возникающих, например, в методе Монте-Карло, имитационном моделировании

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

равномерному.

Широкое распространение получили различные ПСП над кольцами Галуа, та-

кие как, например, линейные рекуррентные последовательности (ЛРП) и последо-

вательности, вырабатываемые полиномиальными генераторами, поскольку, во-пер-

вых, они строятся с помощью стандартных кольцевых операций и, во-вторых, явля-

ются достаточно легко реализуемыми. Существенным недостатком ЛРП является

небольшая глубина линейной зависимости элементов последовательности от преды-

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

ложениях. Последовательности, вырабатываемые полиномиальными генераторами,

с другой стороны, как правило, лишены этой проблемы, поэтому представляют ин-

тересную альтернативу ЛРП.

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

ров над кольцами Галуа. В частности, было показано, что транзитивных полиномов

(задающих полноцикловые подстановки) над кольцами Галуа R, отличными от ко-

нечных полей GF (q) из q элементов и примарных колец вычетов Z_pn по модулю pⁿ,

не существует.

В работе [2] был предложен способ построения генератора над кольцами Галуа

максимального периода |R|, названного инверсным, который представляет собой по-

переменное действие инверсной функции и некоторой подстановки на множестве

делителей нуля кольца R. Также в [2,3] исследовалась величина, называемая откло-

нением. В нестрогом смысле, который далее будет формализован, эта величина дает

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

тельности от равномерного распределения. В этих работах были получены оценки

отклонения D^∗ℓ отрезка длины ℓ его выходных последовательностей и отклонение

последовательности пар элементов на всем периоде.

В настоящей статье предлагается способ построения генератора максимального

периода над произвольным кольцом Галуа R, который обобщает инверсный гене-

ратор. Этот генератор назван кусочно-полиномиальным. Как и в случае полино-

миального, кусочно-полиномиальный генератор реализуется с помощью стандарт-

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

длина периода, которая равна |R|, тогда как для полиномиальных генераторов над

кольцами Галуа, отличными от конечных полей и примарных колец вычетов, такая

величина длины периода не достижима.

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

бой попеременное действие полинома и некоторой подстановки на множестве дели-

телей нуля кольца R. Исследуются длина периода и статистические свойства рас-

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

оценка отклонения D^∗ℓ отрезка длины ℓ его выходных последовательностей. Полу-

ченные новые результаты сравниваются с известными оценками отклонения для

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

скими структурами. В частности, если длина отрезка последовательности ℓ = O(T ),

степень многочлена d = O(T ) при мощности кольца T → ∞, то отклонение отрезка

кусочно-полиномиальной последовательности

(

)

D^∗ℓ = O

d² ℓ-2 T² log T

а при достаточно больших ℓ справедлива асимптотически более точная оценка

(

)

D^∗ℓ = O

d⁴ ℓ-4 T⁴ log T

Полученная асимптотика при определенных значениях соответствует аналогичной

асимптотике для последовательностей, вырабатываемых полиномиальными генера-

торами над кольцами вычетов Z_M и простыми полями GF(p). Также при определен-

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

полученная в данной статье, является асимптотически более точной, чем оценка

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

§ 2. Основные определения и обозначения

Рассмотрим кольцо Галуа R = GR(p^tn, pⁿ) характеристики pⁿ с p^tn = qⁿ элемен-

тами (см. [4, 5]). Пусть R^∗ - множество обратимых элементов кольца R. Обозначим

через ξ элемент кольца R, порождающий множество Тейхмюллера

Γ(R) = {0, e, ξ, ξ², . . . , ξpt-²} = {x ∈ R | x^q = x}.

Пусть

Γ(R)^∗ = Γ(R) \ {0}.

Произвольный элемент x кольца R можно однозначно представить в виде

x = x₀ + px₁ + ... + pn-1xn-1,

(1)

где x₀, x₁, . . . , xn-1 ∈ Γ(R). С другой стороны, рассматривая R как модуль над коль-

цом Z_pn вычетов по модулю pⁿ, произвольный элемент y кольца R можно предста-

100

вить в виде

y=a₀ +a₁ξ+...+at-1ξpt-¹,

(2)

где a₀, . . . , at-1 ∈ Zpn. Рассмотрим автоморфизм Фробениуса σ, действующий на

каждый элемент x, определенный равенством (1), по правилу

σ(x) = xp0 + pxp1 + . . . + pn-1xpn-1,

а на многочлен f(s) = f₀ + f₁s + . . . + f_ds^d ∈ R[s] - по правилу

σ(f(s)) = σ(f₀) + σ(f₁)s^p + . . . + σ(f_d)s^dp,

и функцию следа Tr:

∑

Tr(x) =

σ^j(x).

j=0

Здесь e - единица кольца R, а R₀ = {0, e, . . ., (pⁿ - 1)e} - подкольцо кольца R,

изоморфное Z_pn .

Будем говорить, что элемент x ∈ R сравним с элементом y ∈ R по модулю идеа-

ла pⁱR, 0 ≤ i ≤ n, и обозначать x ≡ y (pⁱR), если x - y ∈ pⁱR.

Рассмотрим произвольный многочлен f(s) ∈ R[s]. Назовем многочлен f(s) невы-

рожденным, если f(s) = σ(g(s)) - g(s) + θ для произвольных g(s) ∈ R[s], θ ∈ R

(см. [6]). Используя представление (1) элементов кольца, представим f(s) в следу-

ющем виде:

f (s) = f₀(s) + pf₁(s) + . . . + pn-1fn-1(s),

где f_i(s) - многочлен с коэффициентами из Γ(R) для всех 0 ≤ i ≤ n - 1. Пусть

степень каждого f_i(s) равна d_i. Назовем число

D_f = max{d₀pn-1, . . . , dn-2p, dn-1}

взвешенной степенью многочлена f(s).

Пусть χ_e - канонический аддитивный характер кольца R:

χ_e(x) = e2πiTpnx) .

Произвольный аддитивный характер χ кольца R можно представить в виде χ(x) =

= χ_e(αx) для некоторого элемента α из R. Если α = 0, то характер χ называется

нетривиальным.

§ 3. Построение кусочно-полиномиальной функции над кольцом Галуа

Представим произвольный элемент x кольца R в виде x = p^ℓx, где x ∈ R^∗,

0 ≤ ℓ ≤ n. Элемент кольца может быть записан в таком виде многими способами,

однако в двух таких представлениях x = p^ℓ x = p^ℓ x элементы x и x сравнимы по

модулю p^n-ℓR. Для некоторого числа d ≥ 1 и многочлена F (s) = f₀ + f₁s + . . . + f_ds^d

из R[s], где f₀, . . . , fd-1 ∈ R, f_d ∈ R\{0}, определим функцию ϕ_F : R → R по правилу

ϕ_F (x) = ϕ_F (p^ℓx) = f₀ + p^ℓ(f₁x + . . . + f_dx^d).

Такое задание корректно, поскольку если x = p^ℓ x = p^ℓ x, то x ≡ x (p^n-ℓR), поэтому

f₁x + . . . + f_dx^d ≡ f₁x + . . . + f_dx^d (p^n-ℓR), следовательно, p^ℓ(f₁x + . . . + f_dx^d) =

= p^ℓ(f₁x + . . . + f_dx^d), откуда ϕ_F(p^ℓx) = ϕ_F(p^ℓx).

101

k+1

Введем следующие обозначения: ϕ¹

=ϕ_F, ϕ

= ϕ^kF ◦ ϕ_F, k ≥ 1.

По функции ϕ_F определим функцию ϕ₀ : GF(p^t) → GF(p^t) следующим образом.

Пусть

f₀, . . . ,fd - образы элементов f0, . . . , fd при действии естественного эпимор-

физма из R на R/pR = GF (p^t). Тогда

ϕ₀(z) =

f₀ +

f₁z + . . . +

f_dz^d,

где сложение выполняется в GF (p^t).

Пусть ϕ′0(z) =

f₁ +

f₂z + . . . +

f_dzd-1 - производная многочлена ϕ₀ (см. [7]).

Предложение 1. Отображение ϕ_F является подстановкой на R тогда и

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

^{ϕ₀ - подстановка на GF(p^t),

(3)

ϕ′0 не имеет ненулевых корней в GF(p^t).

Доказательство. Необходимость. Поскольку ϕ_F инъективно, то для любых

различных элементов x, y из кольца R справедливо неравенство ϕ_F (x) = ϕ_F (y). Рас-

смотрим такие x, y, что x = pn-1x₀, y = pn-1y₀, где x₀, y₀ - произвольные элементы

из Γ(R), x₀ = y₀. Получаем, что поскольку ϕ_F (x) = ϕ_F (y), то pn-1(f₁x₀ + . . . +

+f_dxd0) = pn-1(f₁y₀ + . . . + f_dyd0), откуда f₁x₀ + . . . + f_dxd0 = f₁y₀ + . . . + f_dyd0. От-

сюда ϕ₀(x₀) = ϕ₀(y₀) для любых x₀, y₀ ∈ Γ(R). В силу произвольности выбора эле-

ментов x₀, y₀ получаем, что ϕ₀(z₁) = ϕ₀(z₂) для любых различных z₁, z₂ ∈ GF (p^t),

следовательно, ϕ₀ инъективно, поэтому является подстановкой на GF (p^t).

Рассмотрим элементы x, y вида x = pn-2(z + px₁), y = pn-2(z + py₁), где x₁, y₁ ∈

∈ Γ(R), x₁ = y₁, z ∈ Γ(R) \ {0}. Из условия ϕ_F (x) = ϕ_F (y) получаем, что

(

)

(

)

pn-2

f₁(z + px₁) + . . . + f_d(z + px₁)^d

=pn-2

f₁(z + py₁) + . . . + f_d(z + py₁)^d

поэтому

(

)

pn-2

f₁(z + px₁) + f₂(z² + 2pzx₁ + p²x²¹) + . . . + f_d(z^d + dpzd-1x₁ + p²r₁)

= pn-2(f₁(z + py₁) + f₂(z² + 2pzy₁ + p²y²¹) + . . . + f_d(z^d + dpzd-1y₁ + p²r₂))

для некоторых r₁, r₂ ∈ R. Отсюда следует, что

f₁(z + px₁) + f₂(z² + 2pzx₁) + . . . + f_d(z^d + dpzd-1x₁) ≡

≡ f₁(z + py₁) + f₂(z² + 2pzy₁) + . . . + f_d(z^d + dpzd-1y₁) (p²R),

откуда

(x₁ - y₁)p(f₁ + 2f₂z + . . . + df_dzd-1) ≡ 0 (p²R),

следовательно, f₁ + 2f₂z + . . . + df_dzd-1 ≡ 0 (pR), поэтому

f₁ + 2f₂z + . . . + df_dzd-1 = 0,

откуда ϕ′0(z) = 0 для любого z ∈ Γ(R) \ {0}. В силу произвольности выбора элемен-

та z получаем, что для любого элемента z^′ ∈ GF (p^t) \ {0} справедливо неравенство

ϕ′0(z^′) = 0.

Достаточность. Покажем, что при выполнении условия (3) отображение ϕ_F явля-

ется подстановкой на R. Для этого достаточно доказать, что для любых элементов

y₁ = y₂ из R справедливо неравенство ϕ_F (y₁) = ϕ_F (y₂). Пусть y₁ = pℓ1x₁, y₂ = pℓ2 x₂,

x_i ∈ R^∗, i = 1, 2.

Рассмотрим случай, когда ℓ₁ = ℓ₂. Пусть, не ограничивая общности, ℓ₁ < ℓ₂.

Заметим, что если f₁x₁ + . . . + f_dxd1 =

0, то ϕ₀(x₁) =

f₀ = ϕ₀(0), откуда x₁ = 0

102

в силу инъективности подстановки ϕ₀, поэтому x₁ ∈ R^∗ - противоречие. Поэтому

f₁x₁ + . . . + f_dxd1 = 0. Тогда в p-адическом разложении ϕ_F (y₂) = f₀ + pℓ2 (f₁x₂ +

+ ... + f_dxd2) слагаемое при pℓ1 равно pℓ1-му разряду элемента f₀, а в p-адическом

разложении ϕ_F (y₁) = f₀ + pℓ1(f₁x₁ + . . . + f_dxd1) слагаемое при pℓ1 не равно pℓ1 -му

разряду элемента f₀, поэтому ϕ_F (y₁) = ϕ_F (y₂).

Рассмотрим случай, когда ℓ₁ = ℓ₂ = ℓ. Предположим, что ϕ_F (y₁) = ϕ_F (y₂). Тогда

(

)

ϕ_F (y₁) - ϕ_F (y₂) = p^ℓ

f₁(x₁ - x₂) + . . . + f_d(xd1 - xd2)

= 0.

Поскольку x₁ = x₂ + pⁱc, c =

0, 0 ≤ i ≤ n - ℓ - 1, получаем

(

)

p^ℓ

f₁(x₂ - x₂ + pⁱc) + f₂((x₂ + pⁱc)² - x²²) + . . . + f_d((x₂ + pⁱc)^d - xd2)

= 0,

откуда

(

)

p^ℓ

f₁pⁱc + 2f₂x₂pⁱc + (pⁱc)² + . . . + df_dxd-12pⁱc + . . .

= 0,

поэтому

(

)

p^ℓ

pⁱ(f₁c + 2f₂x₂c + . . . + df_dxd-12c) + pi+1r

= 0,

где r ∈ R. Получаем, что коэффициент при pℓ+i равен

c(f₁ + 2f₂x₂ + . . . + df_dxd-12) = c

f₁ +

f₂x₂ + . . . +

f_dxd-12) = cϕ′0(x₂).

Поскольку c =

0, ϕ′0(x₂) = 0, то c

f₁ +

f₂x₂ + . . . +

f_dxd-12) = 0 - противоречие.

Таким образом, ϕ_F инъективно, и следовательно, является подстановкой на R.

▴

Всюду далее будем предполагать, что отображение ϕ_F является подстановкой

на R. Рассмотрим последовательность (z_i)∞i=0, где z_i = ϕi0(z₀), i ∈ N, z₀ ∈ GF (p^t). За-

метим, что если ϕ₀ - полноцикловая подстановка на GF (p^t), то последовательность

x₀ = 0, x₁ = ϕ_F (x₀), . . . , xm+1 = ϕ_F (x_m), . . . пробегает элементы R, p-адическое

разложение которых имеет вид

x_m = x(m)0 + px(m)1 + . . . + pn-1x(m)n-1,

где x_m = x(m)0 = z_m. Поэтому x(m)0 пробегает Γ(R), когда m = 0, 1, . . . , p^t - 1.

Пусть всюду далее ϕ₀ - полноцикловая подстановка на GF (p^t). Пусть B(ϕ_F ) =

= x(pt-¹⁾⁰ + pR. Для любого элемента x^′ ∈ pR определим множество

{

}

Orb(x^′) =

x^′, ϕ_F (x^′), . . . , ϕpt-1F(x^′)

Заметим, что когда i пробегает значения от 0 до p^t -1, младшие разряды элементов

ϕ^iF (x^′) пробегают множество Γ(R). Таким образом, для любого элемента x ∈ R

существует единственный элемент x^′ ∈ pR, такой что x ∈ Orb(x^′).

Определение. Пусть ϕ_F - подстановка на R, соответствующая ей функция ϕ₀

- полноцикловая подстановка на GF (p^t), x - произвольный элемент из R, и пусть

x ∈ Orb(x^′) для некоторого x^′ ∈ pR. Пусть π - некоторая полноцикловая подстанов-

ка на множестве pR. Определим функцию Φ_F,π : GR(p^tn, pⁿ) → GR(p^tn, pⁿ) следую-

щим образом:

^{ϕ_F (x), если x ∈ B(ϕ_F ),

Φ(x) = Φ_F,π(x) =

π(x^′),

если x ∈ B(ϕ_F ).

Функции Φ_F,π такого вида будем называть кусочно-полиномиальными.

Предложение 2. Функция Φ_F,π - полноцикловая подстановка на R.

103

Доказательство. Покажем, что для любых y₁ = y₂ из кольца R выполняет-

ся неравенство Φ(y₁) = Φ(y₂). Пусть y₁ ∈ Orb(y′1), y₂ ∈ Orb(y′2), y′1, y′2 ∈ pR. Если

y₁, y₂ ∈ B(ϕ_F ), то y′1 = y′2, поэтому Φ(y₁) = π(y′1) = π(y′2) = Φ(y₂). Если y₁ ∈ B(ϕ_F ),

y2 ∈ B(ϕF), то Φ(y2) = ϕF(y2) ∈ pR, поэтому Φ(y1) = Φ(y2), поскольку Φ(y1) =

= π(y′1) ∈ pR. Если y₁, y₂ ∈ B(ϕ_F ), то Φ(y₁) = ϕ_F (y₁) = ϕ_F (y₂) = Φ(y₂), поскольку

ϕ_F - подстановка. Таким образом, Φ инъективно, и следовательно, является подста-

новкой на R.

Полноцикловость подстановки Φ следует из того, что для каждого элемента

x^′ ∈ pR элементы множества Orb(x^′) лежат на одном цикле подстановки ϕ_F , а под-

становка π является полноцикловой на множестве делителей нуля pR. ▴

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

ально обобщает класс кусочно-инверсных функций из работы [2]. В качестве при-

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

пенных функций, задаваемых отображением ϕ_F (p^ℓx) = ap^lx^d + b, где a ∈ R \ {0},

b ∈ R, d ∈ N. Пусть ϕ₀(s) = as^d +^b - полноцикловый (транзитивный) многочлен

над полем GF (p^t). Тогда, поскольку производная ϕ′0(s) = dasd-1 может быть равна

нулю только в точке s = 0, по предложению 1 функция ϕ_F является подстановкой

над R, поэтому корректно задана кусочно-полиномиальная функция Φ_F,π с произ-

вольной полноцикловой на множестве pR подстановкой π. Приведем пример таких

функций.

Пример 1. Рассмотрим кольцо

R = GR(3⁴,3²) = {Aα + B : A,B ∈ Z₉} = Z₉[α]/D,

GF (3²) = {0, 1, β, β², β³, 2, β⁵, β⁶, β⁷},

где D ∈ Z₉[α] - некоторый многочлен Галуа степени 2, т.е. неприводимый по моду-

лю 3 многочлен степени 2 из Z₉. Положим a = 2α + r₀, r₀ ∈ pR, b = r₁ + r₂, где

r₁ ∈ {1, 2α+1, 8, α+2}, r₂ ∈ pR. Пусть F(s) = as⁷ +b. Тогда

F (s) = ϕ₀(s) = β⁵s⁷ +b^′,

где b^′ ∈ {1, β³, 2, β⁷}, и преобразование ϕ₀ является полноцикловой подстановкой над

полем GF (3²).

Поскольку по предложению 1 преобразование ϕ_F является подстановкой, то кор-

ректно задана кусочно-степенная функция Φ_F,π для некоторой подстановки π, пол-

ноцикловой на множестве pR.

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

функцией ϕ_F (p^ℓx) = ap^ℓx²³ + b.

Кусочно-полиномиальные функции не ограничиваются кусочно-степенными, как

показывают следующие примеры.

Пример 2. В обозначениях примера 1 рассмотрим многочлен

F (s) = s⁵ + (8α + 8)s + α.

Тогда

F (s) = ϕ₀(s) = s⁵ + β⁶s + β является транзитивным многочленом над GR(3²),

а производная ϕ′0(s) = 2s⁴ + β⁶ не имеет корней. Поэтому по предложению 1 преоб-

разование

ϕ_F (p^ℓx) = p^ℓx⁵ + (8α + 8)p^ℓx + α

является подстановкой, и корректно задана кусочно-полиномиальная функция Φ_F,π

для некоторой подстановки π, полноцикловой на множестве pR.

Пример 3. Рассмотрим кольцо

R = GR(2⁶,2²) = {Aα² + Bα + C : A,B,C ∈ Z₄} = Z₄[α]/D,

GF (2³) = {0, 1, β, β², β³, β⁴, β⁵, β⁶},

104

где D ∈ Z₄[α] - некоторый многочлен Галуа степени 3. Рассмотрим многочлен

F (s) = (3α² + 2α + 2)s⁷ + s⁶ + (α + 1)s⁴ + s³ + αs² + s + 1.

Тогда

F (s) = ϕ₀(s) = β²s⁷ + s⁶ + β³s⁴ + s³ + βs² + s + 1 является транзитивным

многочленом над GR(2³), а производная ϕ′0(s) = β²s⁶ + s² + 1 не имеет корней.

Поэтому по предложению 1 преобразование

(

)

ϕ_F (p^ℓx) = p^ℓ

(3α² + 2α + 2)x⁷ + x⁶ + (α + 1)x⁴ + x³ + αx² + x

является подстановкой, и корректно задана кусочно-полиномиальная функция Φ_F,π

для некоторой подстановки π, полноцикловой на множестве pR.

§ 4. Оценка тригонометрической суммы

Пусть Φ = Φ_F,π - произвольная кусочно-полиномиальная функция над кольцом

Галуа GR(p^tn, pⁿ), T = p^tn, 1 ≤ ℓ ≤ T . Пусть задана последовательность

x₀, x₁ = Φ(x₀), . . . , xℓ-1 = Φℓ-1(x₀).

В данном параграфе приводится оценка тригонометрической суммы



∑



|S_ℓ(Φ)| =



χ(x_m)



m=0

методом, предложенным в работе [8] для оценки отклонения выходных последо-

вательностей полиномиальных генераторов над конечными простыми полями. Над

кольцами Галуа он был впервые применен в работах [2, 3] для получения оценок

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

Галуа, а в работе [9] - для получения оценок отклонения линейных рекуррентных

последовательностей над кольцами Галуа.

Нам понадобится следующая

Лемма 1 [6, теорема 2]. Пусть f(s) ∈ R[s] - невырожденный многочлен со

взвешенной степенью D_f . Тогда для нетривиального аддитивного характера χ

справедливо неравенство



∑



√



χ(f(x))

≤ (D_f - 1)

p^t.



x∈Γ(R)

Лемма 2. Пусть Φ = Φ_F,π - произвольная кусочно-полиномиальная функция

над кольцом Галуа GR(p^tn, pⁿ), d = deg F (s), T = p^tn. Пусть задана последователь-

ность x₀, x₁ = Φ(x₀), . . . , xℓ-1 = Φ(xℓ-2), 1 ≤ ℓ ≤ T . Тогда если F (s) = s + a, a ∈ R,

d ≥ 3p²-n-1, (d,p) = 1, то



∑



|S_ℓ(Φ)| =



χ(x_m)



m=0

(√

√

(

))1/2

3ℓ

<ℓ1/2

ℓpt(n-1)K + pt(n-1)

-pt/2 +2

4pt(n-1)K

где K = dpn+2 -¹ + 2.

105

Доказательство. Для любого целого k справедливо



∑



Sℓ(Φ) -

χ(xm+k)

≤ 2|k|.

(4)



m=0

{

}



Для натурального числа Q определим множество C(Q) = k ∈ Z

-Q

<k≤

Тогда

∑

Q²

|k| ≤

k∈C(Q)

Суммируя неравенство (4) по всем k ∈ C(Q), получаем

Q|S_ℓ(Φ)| ≤ V +

(5)

где



∑

∑



∑



∑



V =



χ(xm+k)

≤



χ(Φ^k(x_m))



m=0 k∈C(Q)

m=0

k∈C(Q)

Из неравенства Коши- Буняковского - Шварца следует, что



∑

∑



∑

∑



V² ≤ ℓ



χ(Φ^k(x_m))

≤ℓ



χ(Φ^k(x_m))



m=0

k∈C(Q)

m=0

k∈C(Q)

∑

(

)

∑

(

)

=ℓ

Φk1 (x_m) - Φk2(x_m)

=ℓ

Φk1 (x_m) - Φk2(x_m)

m=0 k1,k2∈C(Q)

k1,k2 m=0

∑

(

)

∑

(

)

=ℓ

Φk1 (x) - Φk2(x)

= Qℓ² + ℓ

Φk1 (x) - Φk2(x)

≤

k1,k2 x∈R

k1=k2 x∈R



∑



∑



≤ Qℓ² + 2ℓ



χ(Φk1-k2 (x) - x)



k2<k1

x∈R

Получаем



∑



∑



V² ≤ Qℓ² + 2ℓ

(Q - k)

χ(Φ^k(x) - x)

(6)



k=1

x∈R

[√

]

3ℓ

Положим Q =

+ 1. Такое Q удовлетворяет условиям 1 ≤ Q ≤ T при

pt(n-1)K

1 ≤ ℓ ≤ T. Из условия d ≥ 3p²-n-1 следует, что K > 3pt-2, поэтому

pt(n-1)+2K > p^tn.

Поскольку ℓ ≤ p^tn, получаем

ℓ<

pt(n-1)+2K,

106

откуда

3ℓ

<p²,

pt(n-1)K

поэтому Q - 1 < p. Заметим, что



∑



∑



χ(Φ^k(x) - x) -

χ(ϕ^kF (x) - x)

≤ 2pt(n-1)k,



x∈R

поэтому



∑



∑



χ(Φ^k(x) - x)

≤



χ(ϕ^kF (x) - x)

+ 2pt(n-1)k.



x∈R



∑



Оценим величину

χ(ϕ^kF (x) - x)

Пусть F₁(s) = F (s), F_k(s) = F (Fk-1(s)), k ≥ 2.



^.

x∈R

Представив произвольный элемент x как x₀ + c, где x₀ ∈ Γ(R), c ∈ pR, получаем



∑



∑



∑

(

)



χ(ϕ^kF (x) - x)



ϕ^kF (x₀ + c) - (x₀ + c)



x∈R

c∈pR x0∈Γ(R)



[

]



(

)

∑

(

)

∑



ϕ^kF (c) - c

F_k(x₀ + c) - (x₀ + c)



c∈pR

x0∈Γ(R)^∗



[

]



(

)

∑

(

)

∑



ϕ^kF (c) - c

- χ(F_k(c) - c) +

F_k(x₀ + c) - (x₀ + c)



≤



c∈pR

x0∈Γ(R)

[



]

∑



∑

(

)



≤



F_k(x₀ + c) - (x₀ + c)



+2 .



c∈pR

x0∈Γ(R)

Для элемента c из pR определим многочлен G_k,c(s) = F_k(s + c) - (s + c). Если d =

= k = 1, то поскольку F(s) = s + a, a ∈ R, степень многочлена G_k,c равна 1,

поэтому многочлен G_k,c невырожден. Если d и k одновременно не равны 1, то степень

многочлена G_k,c равна dk. Поскольку (d, p) = 1, k ≤ Q - 1 < p, получаем, что

(deg G_k,c, p) = 1. Заметим, что если многочлен g(s) вырожденный, то g(s) = σ(h(s))-

- h(s) + θ для некоторых h(s) ∈ R[s], θ ∈ R. Пусть h(s) = h₀ + h₁s + . . . + h_us^u.

Тогда σ(h(s)) = σ(h₀) + σ(h₁)s^p + . . . + σ(h_u)s^pu, поэтому либо g(s) - константа,

либо deg g(s) = pu, откуда (deg g, p) = p. Так как (deg G_k,c, p) = 1, получаем, что

многочлен G_k,c невырожден. Применяя лемму 1 и учитывая, что взвешенная степень

DGk,c ≤ pn-1dk, получаем



∑

[

]

∑



χ(ϕ^kF (x) - x)

≤

(pn-1kd - 1)pt/2 + 2

= pt(n-1)((pn-1kd - 1)pt/2 + 2),



x∈R

c∈pR

поэтому



∑



χ(Φ^k(x) - x)

≤ pt(n-1)((pn-1kd - 1)pt/2 + 2) + 2pt(n-1)k =



x∈R

= pt(n-1)((pn-1kd - 1)pt/2 + 2k + 2).

107

Из (6) получаем

∑

V² ≤ Qℓ² + 2ℓ (Q - k)pt(n-1)(kK - pt/2 + 2) =

k=1 (

)

∑

= Qℓ² + 2ℓpt(n-1) Q (kK - (pt/2 - 2)) - (k²K - k(pt/2 - 2))

k=1

(

= Qℓ² + 2ℓpt(n-1) Q²(Q - 1)

- Q(Q - 1)(pt/2 - 2) -

)

(Q - 1)Q(2Q - 1)

Q(Q - 1)

-K

(pt/2 - 2)

(

)

Q+1

pt/2 - 2

= Qℓ² + 2ℓpt(n-1)Q(Q - 1) K

(

)

Q+1

pt/2 - 2

< Qℓ² + 2ℓpt(n-1)Q² K

(

))

Q+1

= Q²ℓ ℓQ-1 + pt(n-1) K

-pt/2 +2

[√

]

3ℓ

Подставляя Q =

+ 1 в неравенство (5), получаем

pt(n-1)K

(

([√

]

)

ℓ

3ℓ

pt(n-1)K

|S_ℓ(Φ)| < ℓ1/2

[√

]

3ℓ

pt(n-1)K

[√

]

)1/2

3ℓ

(

)

pt(n-1)K

+pt(n-1)

-pt/2 +2

(

√

pt(n-1)K

3ℓ

pt(n-1)K

<ℓ1/2

ℓ

3ℓ

pt(n-1)K

√

)1/2

3ℓ

(

)

pt(n-1)K

+pt(n-1)

-pt/2 +2

(√

(

))1/2

√

3ℓ

=ℓ1/2

ℓpt(n-1)K + pt(n-1)

-pt/2 +2

▴

4pt(n-1)K

Замечание 1. Условия F(s) = s + a, a ∈ R, deg F(s) ≥ 3p²-n-1, (deg F(s), p) = 1

на многочлен F (x) в кусочно-полиномиальной функции Φ_F,π из леммы 2 не являют-

ся вырожденными. Они выполняются, например, для многочленов из примеров 1-3.

§5. Оценка отклонения

Для определения того, насколько распределение последовательности близко к

равномерному, вычисляется величина, которая называется отклонением (статисти-

кой Колмогорова).

108

Введем обозначение I = [0, 1) и зафиксируем некоторое натуральное число ℓ.

Отклонением D^∗ℓ (см. [10, определение 1.2]) последовательности x₀, . . ., xℓ-1 чисел

из I называется величина



A([0, α), ℓ)



D^∗ℓ = D^∗ℓ(x₀, . . . , xℓ-1) = sup



-α



,

0<α≤1

ℓ

где A([0, α), ℓ) - число элементов последовательности x₀, . . . , xℓ-1, попадающих в по-

луинтервал [0, α).

Заметим, что величина D^∗ℓ определяет отклонение реального распределения эле-

ментов последовательности от “идеального” равномерного распределения.

Для произвольного элемента x кольца R вида (2) определим нормализующее

отображение η: R → [0, 1) следующим образом:

(a₀ + a₁pⁿ + . . . + at-1pn(t-1))

η(x) =

p^tn

где a_i ∈ Z_pn .

Нам понадобится следующая

Лемма 3 [9, утверждение 1]. Пусть P

- множество, состоящее из чисел

y₀, . . . , yℓ-1, y_i = η(x_i), 0 ≤ i ≤ ℓ-1, а x₀, . . ., xℓ-1 - последовательность элементов

кольца R = GR(p^tn, pⁿ). Тогда, если



∑



χ(x_i)

≤ B,



i=0

где χ - произвольный нетривиальный аддитивный характер кольца R, а B - неко-

торое действительное число, не зависящее от характера χ, то

(

)

1-pⁿ

D^∗ℓ(P) <

n ln p +

p^tn

ℓ

π²

pⁿ

Пусть задана произвольная кусочно-полиномиальная функция Φ_F,π над коль-

цом Галуа R = GR(p^tn, pⁿ). Последовательность (x_i)∞i=0 будем называть кусочно-

полиномиальной последовательностью с порождающей функцией Φ_F,π, если x_i =

= Φ_F,π(xi-1), i ≥ 1. Пусть y_i = η(x_i), i ∈ N₀. Последовательность (y_i)∞i=0 будем

называть последовательностью чисел в полуинтервале [0, 1), порожденной кусочно-

полиномиальной последовательностью над кольцом Галуа.

Теорема. Пусть Φ = Φ_F,π - произвольная кусочно-полиномиальная функция

над кольцом Галуа R, T = p^tn. Пусть также имеется многочлен F (s) = s + a,

a ∈ R, d = degF(s) ≥ 3p²-n-1, (d,p) = 1. Пусть P - последовательность чисел

y_i,

0 ≤ i ≤ ℓ - 1,

в полуинтервале [0, 1), порожденная кусочно-полиномиальной последовательно-

стью над кольцом Галуа с порождающей функцией Φ. Тогда для чисел ℓ, удовле-

творяющих неравенству 1 ≤ ℓ ≤ T, справедлива оценка

(((

)1/2

)

)1/2

(

)1/2

4C₁

2C₁

pt(n-1)(pt/2 - 2)

D^∗ℓ(P) <

+C₂

p^tn

3ℓ

ℓ

4ℓC₁

2ℓ

(

)

(

)

pⁿ - 1

где C₁ = pt(n-1)

dpn+2 -¹ + 2

, C₂ =t

n ln p +

π²

pⁿ

109

Доказательство. Теорема непосредственно следует из лемм 2 и 3. ▴

Замечание 2. Условия F(s) = s + a, a ∈ R, deg F(s) ≥ 3p²-n-1, (deg F(s), p) = 1

на многочлен F (x) в кусочно-полиномиальной функции Φ_F,π из теоремы не являют-

ся вырожденными. Они выполняются, например, для многочленов из примеров 1-3.

Из теоремы следует, что если ℓ = O(T), d = O(T) при T → ∞, то

(

)

D^∗ℓ = O

d² ℓ-2 T² log T

а при достаточно больших ℓ, т.е. когда ℓ ≥

C₁, справедлива асимптотически более

точная оценка

(

)

D^∗ℓ = O

d⁴ ℓ-4 T⁴ log T

Отметим, что подобная асимптотика корректна, поскольку существует беско-

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

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

ны, задающие кусочно-инверсные функции, т.е. многочлены F (s) = asexpR-1 + b,

a ∈ R \ {0}, b ∈ R, expR - экспонента кольца R, для которых

F (s) является пол-

ноцикловым над полем (условие на производную при этом также выполняется).

Согласно [11] такие многочлены существуют.

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

когда ϕ_F (p^ℓx) = ap^ℓx-1 + b, a, b ∈ Γ(R), была получена оценка отклонения D^∗ℓ =

= O(ℓ-1/2T1/2 log T). Пусть d = o(1) при T → ∞. Тогда оценки являются асимпто-

тически эквивалентными, а при

C₁ ≤ ℓ < T оценка из теоремы является асимп-

тотически более точной. Для колец вычетов Z_M с уточнением для простых полей

GF (p) известна следующая оценка отклонения выходных последовательностей по-

линомиальных генераторов (см. [12, теорема 11; 13, теорема 4.1; 14, теорема 2]):

пусть ℓ = O(M), M → ∞, тогда для любого натурального числа r

(

)

D^∗ℓ = O

ℓ

2r (log M)-2 log log M

где константа зависит лишь от степени многочлена и числа r. Эта оценка является

асимптотически более точной, чем оценка из теоремы, если r ≥ 2.

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

1. Ермилов Д.М., Козлитин О.А. Цикловая структура полиномиального генератора над

кольцом Галуа // Матем. вопр. криптогр. 2013. Т. 4. № 1. С. 27-57.

2. Solé P., Zinoviev D. Inversive Pseudorandom Numbers over Galois Rings // European J.

Combin. 2009. V. 30. № 2. P. 458-467.

3. Вернигора Е.В. Инверсный конгруентный генератор над кольцом Галуа характеристи-

ки p^l // Укр. матем. вiсник. 2011. Т. 8. № 4. С. 607-618.

4. Нечаев А.А. Код Кердока в циклической форме // Дискрет. матем. 1989. Т. 1. № 4.

С. 123-139.

5. McDonald B.R. Finite Rings with Identity. New York: M. Dekker, 1974.

6. Helleseth T., Kumar P.V., Shanbhag A.G. Exponential Sums over Galois Rings and Their

Applications // Finite Fields and Applications (Proc. 3rd Int. Conf. Glasgow, Scotland.

July 11-14, 1995). Lond. Math. Soc. Lecture Notes Ser. V. 233. Cambridge: Cambridge

Univ. Press, 1996. P. 109-128.

7. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра. Т. 1. М.: Гелиос АРВ, 2003.

8. Niederreiter H., Shparlinski I.E. On the Distribution and Lattice Structure of Nonlinear

Congruential Pseudorandom Numbers // Finite Fields Appl. 1999. V. 5. № 3. P. 246-253.

110

9. Васин А.Р. Оценки отклонения линейных рекуррентных последовательностей над

кольцами Галуа // Дискрет. матем. 2019. Т. 31. № 3. С. 17-25.

10. Кейперс Л., Нидеррейтер Г. Равномерное распределение последовательностей. М.: На-

ука, 1985.

11. Chou W.-S. The Period Lengths of Inversive Pseudorandom Vector Generations // Finite

Fields Appl. 1995. V. 1. № 1. P. 126-132.

12. El-Mahassni E. Exponential Sums for Nonlinear Recurring Sequences in Residue Rings //

Albanian J. Math. 2010. V. 4. № 1. P. 3-13.

13. Topuzoğlu A., Winterhof A. Pseudorandom Sequences // Topics in Geometry, Coding The-

ory and Cryptography. Dordrecht: Springer, 2007. P. 135-166.

14. Niederreiter H., Winterhof A. Exponential Sums for Nonlinear Recurring Sequences //

Finite Fields Appl. 2008. V. 14. № 1. P. 59-64.

Васин Антон Романович

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

ООО “Центр сертификационных исследований”, Москва

21.07.2019

vasinantr@yandex.ru

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

05.02.2020

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

07.02.2020

111