Инверсный конгруентный генератор над кольцом Галуа характеристики pl
Рассматривается конструкция инверсного конгруентного генератора над кольцом Галуа нечетной характеристики pl, которая была предложена Соле и Зиновьевым для p = 2. C помощью оценок тригонометрических сумм на последовательностях псевдослучайных чисел получена оценка дискрипантной функции, порождаемой...
Gespeichert in:
| Datum: | 2011 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2011
|
| Schriftenreihe: | Український математичний вісник |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/124438 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Инверсный конгруентный генератор над кольцом Галуа характеристики pl / Е.В. Вернигора // Український математичний вісник. — 2011. — Т. 8, № 4. — С. 607-618. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124438 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1244382017-09-27T03:03:04Z Инверсный конгруентный генератор над кольцом Галуа характеристики pl Вернигора, Е.В. Рассматривается конструкция инверсного конгруентного генератора над кольцом Галуа нечетной характеристики pl, которая была предложена Соле и Зиновьевым для p = 2. C помощью оценок тригонометрических сумм на последовательностях псевдослучайных чисел получена оценка дискрипантной функции, порождаемой последовательности псевдослучайных чисел и ассоциированной с ней последовательности двумерных “перекрывающихся” точек. 2011 Article Инверсный конгруентный генератор над кольцом Галуа характеристики pl / Е.В. Вернигора // Український математичний вісник. — 2011. — Т. 8, № 4. — С. 607-618. — Бібліогр.: 8 назв. — рос. 1810-3200 2010 MSC. 11K45. http://dspace.nbuv.gov.ua/handle/123456789/124438 ru Український математичний вісник Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассматривается конструкция инверсного конгруентного генератора над кольцом Галуа нечетной характеристики pl, которая была предложена Соле и Зиновьевым для p = 2. C помощью оценок тригонометрических сумм на последовательностях псевдослучайных чисел получена оценка дискрипантной функции, порождаемой последовательности псевдослучайных чисел и ассоциированной с ней последовательности двумерных “перекрывающихся” точек. |
| format |
Article |
| author |
Вернигора, Е.В. |
| spellingShingle |
Вернигора, Е.В. Инверсный конгруентный генератор над кольцом Галуа характеристики pl Український математичний вісник |
| author_facet |
Вернигора, Е.В. |
| author_sort |
Вернигора, Е.В. |
| title |
Инверсный конгруентный генератор над кольцом Галуа характеристики pl |
| title_short |
Инверсный конгруентный генератор над кольцом Галуа характеристики pl |
| title_full |
Инверсный конгруентный генератор над кольцом Галуа характеристики pl |
| title_fullStr |
Инверсный конгруентный генератор над кольцом Галуа характеристики pl |
| title_full_unstemmed |
Инверсный конгруентный генератор над кольцом Галуа характеристики pl |
| title_sort |
инверсный конгруентный генератор над кольцом галуа характеристики pl |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2011 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124438 |
| citation_txt |
Инверсный конгруентный генератор над кольцом Галуа характеристики pl / Е.В. Вернигора // Український математичний вісник. — 2011. — Т. 8, № 4. — С. 607-618. — Бібліогр.: 8 назв. — рос. |
| series |
Український математичний вісник |
| work_keys_str_mv |
AT vernigoraev inversnyjkongruentnyjgeneratornadkolʹcomgaluaharakteristikipl |
| first_indexed |
2025-07-09T01:26:21Z |
| last_indexed |
2025-07-09T01:26:21Z |
| _version_ |
1837130718145150976 |
| fulltext |
Український математичний вiсник
Том 8 (2011), № 4, 607 – 618
Инверсный конгруентный генератор над
кольцом Галуа характеристики p
l
Елена В. Вернигора
(Представлена И. В. Протасовым)
Аннотация. Рассматривается конструкция инверсного конгруен-
тного генератора над кольцом Галуа нечетной характеристики p
l,
которая была предложена Соле и Зиновьевым для p = 2. C помо-
щью оценок тригонометрических сумм на последовательностях псев-
дослучайных чисел получена оценка дискрипантной функции, по-
рождаемой последовательности псевдослучайных чисел и ассоции-
рованной с ней последовательности двумерных “перекрывающихся”
точек.
2010 MSC. 11K45.
Ключевые слова и фразы. Дискрипанция, псевдослучайные чи-
сла, конгруентный генератор, кольца Галуа.
Введение
Последовательности псевдослучайных чисел широко применяю-
тся в задачах имитирования случайных процессов, а также при
использовании метода Монте Карло для вычисления интегралов. В
последние годы псевдослучайные числа используются в криптогра-
фии. Среди нелинейных конгруентных генераторов, порождающих
непредсказуемые последовательности псевдослучайных чисел, наи-
более хорошо изученными являются инверсные конгруентные гене-
раторы (см. [2–4])
yn+1 = ay−1
n + b, n = 0, 1, . . . ,
где параметры a, b и инициальное значение y0 берутся из конечного
поля Fq, причем y−1
n есть обратное к yn в поле Fq, если yn 6= 0, а для
yn = 0 берем (условно) y−1
n = 0.
Статья поступила в редакцию 25.07.2011
ISSN 1810 – 3200. c© Iнститут математики НАН України
608 Инверсный конгруентный генератор...
В работе P. Sole и D. Zinoviev [8] рассматривается обобщение ин-
версного конгруентного генератора на случай кольца Галуа R(l, m)
характеристики 2l. Этими авторами предложена конструкция генера-
тора над R(l, m), порождающего последовательность псевдослучай-
ных чисел отрезка [0, 1).
В настоящей работе мы рассматриваем инверсный конгруентный
генератор над кольцом Галуа характеристики pl, где p > 2 — про-
стое число, и показываем, что соответствующая последовательность
псевдослучайных чисел проходит двумерный сериальный тест на ста-
тистическую независимость (непредсказуемость).
На протяжении всей статьи мы используем следующие обозначе-
ния:
p всегда обозначает простое число больше 2;
eq(x) := e
2πi x
q для натурального q и вещественного x;
Zq — кольцо классов вычетов по модулю q;
Fq — поле из q элементов.
1. Основные определения и
вспомогательные утверждения
Пусть g(x) — фундаментально примитивный многочлен степе-
ни m из кольца Zpl [x], то есть старший коэффициент g(x) равен 1
и многочлен g̃(x), получаемый из g(x) заменой его коэффициентов
ai ∈ Zpl вычетами по модулю р, является примитивным многочленом
степени m над полем Zp. Через R(l, m) мы обозначим фактор-кольцо
Zpl [x]/(g(x)). Ясно, что R(l, m) — это кольцо Галуа характеристики
pl. Пусть ξ — примитивный элемент в R(l, m), который порождает
тейхмюллерово множество Ξ ⊂ R(l, m), Ξ =
{
0, 1, ξ, . . . , ξpm−2
}
, так
что каждое x ∈ R(l, m) допускает р-адическое представление (разло-
жение).
x = x(0) + px(1) + p2x(2) + · · · + pl−1x(l−1),
x(i) ∈ Ξ, i = 0, . . . , l − 1.
(1.1)
Для x, представленного в форме (1.1), задаем автоморфизм Фро-
бениуса
F (x) = (x(0))p + p(x(1))p + · · · + pl−1(x(l−1))p ∈ R(l, m).
Обозначим Tr(x) =
∑m−1
j=0 F j(x), где F j(x) = F (F j−1(x)). Очевидно,
Tr(x) ∈ Zpl .
Е. В. Вернигора 609
Поскольку каждое x(i) ∈ Ξ допускает единственное представле-
ние через базис 1, ξ, ξ2, . . . , ξm−1, то из (1.1) получаем альтернативное
представление
x = a0 + a1ξ + · · · + am−1ξ
m−1, ai ∈ Zpl . (1.2)
Обозначим:
Rs(l, m) =
{
x ∈ R(l, m)| x(0), . . . , x(s−1) = 0;x(s) 6= 0
}
(1.3)
R∗(l, m) =
{
x ∈ R(l, m)| x(0) 6= 0
}
. (1.4)
Следовательно,
Rs(l, m) = psR∗(l, m).
Ясно, что
R(l, m) =
l
⋃
s=0
Rs(l, m).
Обозначим:
Bs(x) = x + Rs(l, m) = {x + y| y ∈ Rs(l, m)} ; B1(x) := B(x).
Очевидно, Bs(x + y) = Bs(x) для ∀ y ∈ Rs(l, m). Кроме того, имеем
дизъюнктивное разложение
R(l, m) =
⋃
x∈Ξ
B(x).
Для x ∈ R(l, m) обозначим x̄ ∈ Ξ такое, что x ≡ x̄(mod p), то есть
x̄ = x(0) (см. (1.1)).
Покажем, что каждое x ∈ R∗(l, m) обратимо в R(l, m). Действи-
тельно, если x = x(0) + px(1) + · · · + pl−1x(l−1), то
x−1 = y = y(0) + py(1) + · · · + pl−1y(l−1),
где
y0 =
{
1, если x(0) = 1
ξk0 , если x(0) = ξpm−1−k0 ,
y1 = −x
(1)
1 y2
0 = ξ
1
2
(pm−1)x
(1)
1 y2
0,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
yj = −y
(0)
0 (x(j)y(0) + x(j−1)y(1) + · · · + x(1)y(j−1)),
j = 1, 2, . . . , l − 1.
(1.5)
610 Инверсный конгруентный генератор...
Рассмотрим отображение R(l, m) в Fpm , которое получается из
представления (1.2) заменой коэффициентов ai их вычетами по mod
p и отождествлением ξ с примитивным элементом поля Fpm :
R(l, m) ∋ x = a0 + a1ξ + · · · + am−1ξ
m−1 ∈ Fpm ,
где ai ≡ ai(mod p), 0 ≤ ai < p.
Обобщим определение обратимости на случай x ∈ Rs(l, m). Пусть
x = psy, y ∈ R∗(l, m), тогда обобщенное обратное определяется так:
x−1
об. = psy−1, где y−1 определено выше для y ∈ R∗(l, m).
Над полем Fpm определим отображение ϕ0 : Fpm → Fpm
ϕ0(t) =
{
a0t
−1 + b0, если t 6= 0,
b0, если t = 0;
(1.6)
(здесь a0, b0 — фиксированные из Fpm). Рассмотрим рекурсию: tn+1 =
a0ϕ0(tn) + b0, n = 0, 1, . . . , (a0, b0, t0 ∈ Fpm).
Таким образом, мы имеем последовательность t0, t1, . . . . Эта
последовательность вполне определяется однозначно параметрами
a0, b0, t0 ∈ Fpm .
Известно (см., например, [1, 4, 7]), что существует непустое мно-
жество Mpm наборов (a0, b0) ∈ F 2
pm таких, что наименьший период
последовательности {tn} равен pm, т.е. элементы t0, t1, . . . пробегают
все поле Fpm , а потому t0 можно брать равным 0.
Определим функцию ϕ : R(l, m) → R(l, m). Зафиксируем a, b ∈
{
1, ξ, . . . , ξpm−2
}
= Ξ \ {0} := Ξ∗.
ϕ(x) =
{
b если x = 0,
psax−1
∗ + b, если x = psx∗, x∗ = R∗(l, m).
(1.7)
В дальнейшем мы будем считать, что для a, b ∈ Ξ∗ имеем a =
a0, b = b0, (a0, b0) ∈ Mpm . Тогда последовательность x0, x1, . . . , опре-
деляемая как x0 = 0, xn+1 = ϕ(xn), n = 0, 1, . . . , имеет -адическое
представление
xn = x(0)
n + px(1)
n + · · · + pl−1x(l−1)
n , xn = x(0)
n = tn. (1.8)
Учитывая длину периода этой последовательности τ = pm, полу-
чаем, что x
(0)
n пробегает всё Ξ = Fpm , а потому имеем
R(l, m) =
pm−1
⋃
n=0
(x(0)
n + pR(l, m)) =
pm−1
⋃
n=0
B(x(0)
n ).
Е. В. Вернигора 611
Обозначим B = B(x
(0)
pm−1). Для x ∈ R(l, m) определяем множество:
Orb(x) :=
{
x, ϕ(x), . . . , ϕpm−1(x)
}
, ϕk(x) = ϕ(ϕk−1(x)).
Мы также имеем
R(l, m) =
⋃
x∈pR(l,m)
Orb(x).
Следовательно, для каждого x ∈ R(l, m) найдётся x′ ∈ pR∗(l, m) та-
кое, что x ∈ Orb(x′).
Зафиксируем некоторую транзитивную подстановку на множе-
стве pR(l, m). Число элементов в pR(l, m) равно pm(l−1).
Определим функцию Φ : R(l, m) → R(l, m) так:
Φ(x) =
{
ϕ(x), если x /∈ B,
π(x′), если x ∈ B и x ∈ Orb(x′).
(1.9)
Это определение корректно, так как x′ ∈ pR определено однозначно
для каждого x ∈ R(l, m).
Заметим, что функция Φ определяет взаимно однозначное ото-
бражение, так как если y = Φ(x), то
x =
{
Φ−1(y) = a(y − b)−1, если y 6= b,
0 = Φ−1(b), если y = b.
(1.10)
Таким образом, Φ действует как транзитивная подстановка на
кольце R. Случай p = 2 исследован в [8], случай произвольного про-
стого рассматривается аналогично.
Пусть теперь f(x) ∈ R(l, m)[x]. Представим f(x) в виде
f(x) = F0(x) + pF1(x) + · · · + pl−1Fl−1(x), Fj(x) ∈ Ξ[x].
Пусть Df = max[d0p
l−1, . . . , dl−2p, dl−1], dj = cтепень Fj(x). Тогда
справедливы утверждения.
Лемма 1.1. Пусть f — невырожденный многочлен над R(l, m). Тог-
да для (c, p) = 1 имеем:
∣
∣
∣
∣
∑
x∈Ξ
epl(c · Tr(f(x)))
∣
∣
∣
∣
≤ (Df − 1)p
m
2 .
Доказательство см. [6, теор. 1]
Лемма 1.2. Пусть f1(x), f2(x) ∈ R(l, m)[x], причем f1, f2 одновре-
менно невырождены. Тогда для (c1, c2, p) = 1 имеем
∣
∣
∣
∣
∣
∑
x∈Ξ∗
epl(c1Tr(f1(x)) + c2Tr(f2(x
−1)))
∣
∣
∣
∣
∣
≤ (Df1 + Df2)p
m
2 .
Доказательство см. [5].
612 Инверсный конгруентный генератор...
2. Тригонометрические суммы на
последовательности псевдослучайных чисел
Рассмотрим последовательность xn элементов из R(l, m), опреде-
ленную рекурсией
xn+1 = Φ(xn) = Φn+1(x0), n = 0, 1, . . . (2.1)
Из предыдущего следует, что период этой последовательности равен
pml. Представляя xn в форме (1.2) определим нормализованное ото-
бражение R(l, m) → [0, 1) :
R ∋ y = a0 + a1ξ + · · · + am−1ξ
m−1 → η(y)
=
a0 + a1p + · · · + am−1p
m−1
pml
∈ [0, 1).
Таким образом, последовательность {xn} периода pml порожда-
ет последовательность η(xn) ∈ [0, 1), которую мы назовём инвер-
сной конгруентной последовательностью псевдослучайных чисел. Но
чтобы оправдать название псевдослучайной последовательности, мы
должны показать, что {η(xn)} равномерно распределена на [0, 1) и
непредсказуема.
Для этого нам понадобятся оценки некоторых специальных сумм.
Теорема 2.1. Пусть последовательность {xn}, порожденная рекур-
сией (1.5), имеет период τ = pml. Тогда для любого N ≤ τ и любого
ненулевого по mod p вектора h ∈ Zm, справедлива оценка:
∣
∣
∣
∣
N−1
∑
n=0
epm(h · xn)
∣
∣
∣
∣
≤ (3Nplm−m
2
+l−1)1/2,
здесь запись h · xn означает скалярное произведение векторов h =
(h0, . . . , hm−1) и xn = (x(0), x(1), . . . , x(m−1)).
Доказательство. Обозначим SN (h) =
∑N−1
n=0 eq(h · xn). Поскольку
xn = Φn(x0), n = 0, 1, . . . , то мы имеем для любого целого k
∣
∣
∣
∣
SN (h) −
N−1
∑
n=0
eq(h · xn+k)
∣
∣
∣
∣
≤ 2 |k| . (2.2)
Для целого K ≥ 1 обозначим через R(K) множество целых k ∈ Z,
для которых
−
K − 1
2
≤ k ≤
K − 1
2
,
Е. В. Вернигора 613
если K — нечетное;
−
K
2
+ 1 ≤ k ≤
K
2
,
если K — четное. Очевидно,
∑
k∈R(k) |k| ≤
1
4K2.
Применяя неравенство (2.2) для всех k ∈ R(K) и складывая эти
неравенства, получим
K |SN (h)| ≤ W +
1
2
K2, (2.3)
где
W =
∣
∣
∣
∣
N−1
∑
n=0
∑
k∈R(K)
eq(h · xn+k)
∣
∣
∣
∣
≤
N−1
∑
n=0
∣
∣
∣
∣
∑
k∈R(K)
eq(h · Φk(xn))
∣
∣
∣
∣
.
Теперь, в силу неравенства Коши–Шварца, находим
W 2 ≤ N
N−1
∑
n=0
∣
∣
∣
∣
∑
k∈R(K)
eq(h · Φk(xn))
∣
∣
∣
∣
2
≤ N
τ−1
∑
n=0
∣
∣
∣
∣
∑
k∈R(K)
eq(h · Φk(xn))
∣
∣
∣
∣
2
= N
∑
x∈R(l,m)
∣
∣
∣
∣
∑
k∈R(K)
eq(h · Φk(x))
∣
∣
∣
∣
2
≤ N
∑
k1,k2∈R(K)
∣
∣
∣
∣
∑
x∈R(l,m)
eq(h(Φk1(x) − Φk2(x)))
∣
∣
∣
∣
= KNplm + 2N
∑
k1,k2∈R(K)
k1>k2
∣
∣
∣
∣
∑
x∈R(l,m)
eq(h · (Φk1−k2(Φk2(x)) − Φk2(x))
∣
∣
∣
∣
= KNplm + 2N
∑
k1,k2∈R(K)
k1>k2
∣
∣
∣
∣
∑
x∈R(l,m)
eq(h · (Φk1−k2(x) − x))
∣
∣
∣
∣
. (2.4)
Пусть α0, α1, . . . , αm−1 — базис R(l, m) над Zpl , двойственный к
базису
{
1, ξ, ξ2, . . . , ξm−1
}
:= Ξ∗. Тогда для каждого x ∈ R(l, m), x =
x(0) + x(1)ξ + · · ·+ x(m−1)ξm−1, по определению двойственного базиса
имеем:
x(i) = Tr(αix), i = 0, 1, . . . , m − 1,
где Tr(αix) означает функцию следа из R(l, m) в Zpl .
Поэтому, в силу линейности Tr над Zpl , получаем, обозначая
Φk1−k2(x) = y, x = (x(0), . . . , x(m−1)), y = (y(0), . . . , y(m−1)) :
614 Инверсный конгруентный генератор...
∑
x∈R(l,m)
eq(h · (Φk1−k2(x) − x))
=
∑
x∈R(l,m)
eq
( m−1
∑
j=0
hj(y
(j) − x(j))
)
=
∑
x∈R(l,m)
eq
( m−1
∑
j=0
hjTr(αj(y − x))
)
=
∑
x∈R(l,m)
eq
( m−1
∑
j=0
Tr(hjαj(y − x))
)
=
∑
x∈R(l,m)
eq(Tr(βy − βx)) := S(β),
где β =
∑m−1
j=0 hjαj ∈ R(l, m).
Далее, так как y = Φk1−k2(x), то применяя индукцию по k и
используя рекурсию (1.5), мы легко получаем, что Φk(x) имеет один
из трёх следующих видов:
(i) A(k)x+B(k)
C(k)x+D(x) , A(k), B(k), C(k), D(k) ∈ Zpl ;
(A(k), B(k), p) = (C(k), D(k), p) = 1;
0 ≤ s < l − 1;
(ii) A(k)x + B(k), A(k) 6= 0;
(iii) B(k)
(2.5)
Каждый элемент из R(l, m) можно однозначно представить в виде
x + c, где x ∈ Ξ, c ∈ pR(l, m) = B(0).
Теперь учтём, что в представлении (2.5)(i) элемента x ∈ R(l, m)
знаменатель обращается в нуль (для каждого k) не более (rk−1) раз.
Поэтому имеем:
|S(β)| ≤
∑
c∈pR(l,m)
(∣
∣
∣
∣
∑
x∈Ξ∗
eq(β1x + β2x
−1)
∣
∣
∣
∣
+ 2k − 1
)
,
где β1, β2 линейно выражаются через β и одновременно не обращаю-
тся в нуль.
Сумму по x ∈ Ξ∗ можно оценить по лемме 1.1, если β2 = 0 или
по лемме 1.2, если β2 6= 0. Поэтому имеем(учитывая, что |pR(l, m)| =
pm(l−1)):
W 2 ≤ KNplm + 2N
K−1
∑
k=1
(K − k)pm(l−1)(2pl · p
m
2 + 2k − 1)
Е. В. Вернигора 615
≤ KNplm + 2Npm(l−1)
(
2pl−1 · p
m
2 ·
K(K − 1)
2
+
K(K − 1)(2K − 1)
6
)
< KNplm + (K − 1)KN(2pl+m
2
−1 +
K
3
)pm(l−1)
= K2N
(
plm(1 − 2p−
m
2
+l−1)K−1 + 2plm−m
2
+l−1 +
2
3
K
)
. (2.6)
при условии, что K ≤ τ . Положим
K =
[(3
2
)1/2
p
lm
2
−1
∣
∣1 − 2p−
m
2
+l
∣
∣
1/2
]
+ 1. (2.7)
Будем считать, что τ ≥ N > 2p
lm
2 . Тогда условие K ≤ τ удовле-
творяется. При таком выборе К имеем:
plm
∣
∣1− 2p−
m
2
+l−1
∣
∣K−1 + 2plm−m
2
+l−1 +
2
3
K ≤
((8
3
)1/2
+ 2
)
plm−m
2
+l−1.
(2.8)
Следовательно, из (2.2)–(2.8) находим:
|SN (h)| <
((8
3
)1/2
+ 2
)1/2
N1/2 · p
lm
2
−m
4
+ l
2
− 1
2 .
Отсюда уже следует утверждение теоремы 1.1.
Следствие 2.1. Пусть последовательность xn порождена рекур-
сией (1.5) и имеет максимальный период τ = pml, причем m > 2l.
Тогда для ненулевого по mod p вектора h ∈ Zm справедливо равен-
ство |Sτ (h)| = 0.
Действительно, мы имеем
Sτ (h) =
τ−1
∑
n=0
eq(h · xn) =
∑
x∈R(l,m)
eq(h · x)
=
q−1
∑
x(0),...,x(m−1)
=0
eq
( m−1
∑
j=0
hjx
(j)
)
=
m−1
∏
j=0
q−1
∑
x(j)=0
e
2πi
hjx(j)
q = 0, (2.9)
так как хотя бы одно hj 6≡ 0 (mod p).
Пусть последовательность {xn}, порожденная рекурсией (1.5),
имеет период τ . Положим
Sτ (h1, h2) :=
τ−1
∑
n=0
eq(h1xn + h2xn+r), (2.10)
где r — натуральное, r < τ , h1, h2 ∈ Zm
q .
616 Инверсный конгруентный генератор...
Теорема 2.2. Пусть {xn} — последовательность максимального
периода, то есть τ = pml, и пусть h1, h2 — ненулевые по mod p
векторы. Тогда
|Sτ (h1, h2)| ≤ 3pml−m
2
+l−1.
Доказательство. Поскольку функция Φ есть подстановка на R(l, m),
то Φ(xn+r) = Φr(xn), а потому
Sτ (h1, h2) =
τ
∑
n=0
eq(h1 · xn + h2 · xn+r) =
∑
x∈R(l,m)
eq(h1 · x + h2 · Φ
r(x)).
Теперь, как и при доказательстве теоремы 2.1, мы получаем:
∣
∣
∣
∣
∑
x∈R(l,m)
eq(h1 · x + h2 · Φ
r(x))
∣
∣
∣
∣
=
∣
∣
∣
∣
∑
x∈R(l,m)
eq(Tr(β1x + β2x
−1))
∣
∣
∣
∣
≤
∑
c∈pR(l,m)
(
2m +
∣
∣
∣
∣
∑
x∈Ξ∗
eq(Tr(β1x + β2x
−1))
∣
∣
∣
∣
)
, (2.11)
где β1, β2 ∈ R(l, m), β1, β2 одновременно не равны нулю. А потому
|Sτ (h1, h2)| ≤ pm(l−1)(2m + 2pl−1p
m
2 ) ≤ 3pml−m
2
+l−1.
Теорема доказана.
Замечание 2.1. Полученные оценки сумм SN (h) и Sτ (h1, h2) равно-
мерны по векторам h1, h2 6≡ 0 (mod pl). Эти оценки мы будем исполь-
зовать для анализа на равнораспределенность и непредсказуемость
последовательности {η(xn)}, описанной в начале этого пункта.
3. Дискрипанция
Пусть {Xn} — последовательность k-мерных точек из гиперку-
ба [0, 1)k. Дискрипанция этой последовательности {xn} определяется
величиной
D
(k)
N (X0, X1, . . . , XN−1) = sup
∆⊂[0,1)k
∣
∣
∣
∣
AN (∆)
N
− |∆|
∣
∣
∣
∣
,
где супремум берется по всем параллелепипедам ∆ из гиперкуба
[0, 1)k со сторонами, параллельными координатным осям, |∆| — объём
параллелепипеда ∆, AN (∆) — количество точек xj , j = 0, 1, . . . , N−1,
попавших в ∆. Ясно, что 0 ≤ ∆ ≤ 1.
Е. В. Вернигора 617
Если D
(k)
N → 0 при N → ∞, то распределение точек xn в [0, 1)k
“практически” равномерное. Для периодических последовательно-
стей DN не может стремиться к нулю. Но считается, что чем меньше
D
(k)
N при больших N , тем “лучше” равнораспределены точки в [0, 1)k.
Из одномерной последовательности точек {Un} можно строить ра-
зличные последовательности k-мерных точек. Для изучения непред-
сказуемости одномерной последовательности обычно рассматривают
следующую последовательность k-мерных точек:
X(k)
n = (xn, xn+1, . . . , xn+k−1). (3.1)
Сериальный тест на непредсказуемость одномерной последова-
тельности {xn} утверждает, что если k-мерные точки типа (20)
равномерно распределены, k = 1, 2, 3, 4, 5, то последовательность
{Un} “практически” непредсказуема. В нашем случае, применение
лемм 3.12 и 3.13 из работы Х. Нидеррайтера [7], а также равномер-
ность по векторам h, h1, h2 ∈ Zm
q оценок тригонометрических сумм
SN (h), Sτ (h1, h2), приводят к следующим неравенствам:
D
(1)
N ≤
1
pml
+
(
2
π
log pml +
7
5
m −
m − 1
pl
)
(
3N−1plm−m
2
+l−1
)1/2
(3.2)
D(2)
τ ≤ 1−
(
1 −
1
pml
)2
+3
(
2
π
log pml +
7
5
m −
m − 1
pl
)2
p−
m
2
+l−1. (3.3)
Таким образом, при m > 2(l − 1) и N > plm(1+ǫ)−m
2
+l−1, ǫ > 0 —
произвольно малая постоянная, последовательность {η(xn)} прохо-
дит двумерный сериальный тест на псевдослучайность.
В заключение заметим, что результат теоремы 2.2 в случае p = 2
был получен в работе [8].
Литература
[1] W.-S. Chou, The Period Lengths of Inversive Pseudorandom Vector Generati-
ons // Finite Fields and Their Applications, 1 (1995), 126–132.
[2] J. Eichenauer-Herrmann, H. Grothe, A new inversive congruential pseudorandom
numbers generator with power of two modulus // ACM Trans. Modeling and
Comp. Simulation, 2(1) (1992), 1–11.
[3] J. Eichenauer, J. Lehn, A non-linear congruential pseudorandom numbers
generator // Statist. Heftc, 27 (1986), 315–326.
[4] M. Flahive, H. Niederreiter, On inversive congruential generators for
pseudorandom numbers in: Finite Fields, Coding Theory, and Advances in
Communications and Computing, G. L. Mullen and P. J.-S. Shines (eds.), Marsel
Dekker, N-Y, 1992, 75-80.
618 Инверсный конгруентный генератор...
[5] T. Helleseth, P. V. Kumar, A. G. Shanbhag, Exponential sums over Galois ri-
ngs and their applications, Finite Fields and Applications // Lond. Math. Soc.,
Lecture Notes Ser., 233 (1996), 109–128.
[6] P. V. Kumar, T. Helleseth, A. R. Calderbank, An upper bound for Weil exponential
sums over Galois rings and applications // IEEE Trans. Inform. Theory, IT-41
(1995), 456–468.
[7] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods,
SIAM, Philadelphia, 1992.
[8] P. Sole, D. Zinoviev, Inversive Congruential Pseudorandom Numbers over Galois
Rings, IITP RAS, Moscow, Russia, CNRS-13S, Sophia Antipolis, FRANCE.
Сведения об авторах
Елена Викторовна
Вернигора
Институт математики, экономики
и механики
Одесский национальный университет
им. И. И. Мечникова
ул. Дворянская, 2,
Одеса, 65082
Украина
E-Mail: verlin@ukr.net
|