Варбанець Сергій Павлович Метод тригонометричних сум в теорії конгруентних генераторів псевдовипадкових чисел та асимптотичних задачах теорії чисел

Короткий опис

Варбанець Сергій Павлович, доцент кафедри комп’ютерної алгебри та дискретної математики, Одеський національний університету імені І. І. Мечникова. Назва дисертації: «Метод тригонометричних сум в теорії конгруентних генераторів псевдовипадкових чисел та асимптотичних задачах теорії чисел». Шифр та назва спеціальності 01.01.08 математична логіка, дискретна математика і теорія алгоритмів. Спецрада Д 26.001.18 Київського національного університету імені Тараса Шевченка

Мiнiстерство освiти i науки Укрiїни
Київський нацiональний унiверситет iменi Тараса Шевченка
Квалiфiкацiйна наукова праця
на правах рукопису
Варбанець Сергiй Павлович
УДК 511.33, 519.2
ДИСЕРТАЦIЯ
Метод тригонометричних сум в теорiї
конгруентних генераторiв
псевдовипадкових чисел та асимптотичних
задачах теорiї чисел
01.01.08 - математична логiка, теорiя алгоритмiв i дискретна математика
Подається на здобуття наукового ступеня
доктора фiзико-математичних наук
Дисертацiя мiстить результати власних дослiджень. Використання iдей,
результатiв i текстiв iнших авторiв мають посилання на вiдповiдне джерело
С.П. Варбанець
Науковий консультант
Кореновський Анатолiй Олександрович
доктор фiзико-математичних наук, професор
Київ - 2021

ЗМIСТ
Вступ 16
Роздiл 1. Тригонометричнi суми над кiльцем цiлих чисел уявного
квадратичного поля 28
1.1. Повнi тригонометричнi суми над G . . . . . . . . . . . . . . . . . . 33
1.1.1. Чиста сума . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.1.2. Твiстовi суми Клостермана на G . . . . . . . . . . . . . . . . 42
1.2. Тригонометричнi суми спецiального виду . . . . . . . . . . . . . . . 46
1.2.1. Узагальненi суми Клостермана над кiльцем цiлих елементiв
уявного квадратичного розширення поля Q(
√
−d) . . . . . . 46
1.2.2. Багатовимiрнi (кратнi) суми Клостермана над Z[θ] . . . . . . 74
1.2.3. Багатовимiрнi норменi суми Клостермана над Z[θ] . . . . . . 81
1.3. Твiстовi тригонометричнi суми Клостерманiвського типу . . . . . . 91
Висновки до роздiлу 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Роздiл 2. Генерування послiдовностей псевдовипадкових чисел 101
2.1. Iнверснi конгруентнi генератори зi змiнним зсувом . . . . . . . . . . 107
2.1.1. Зображення елементiв послiдовностi {yn} у виглядi многочленiв вiд номера елемента i iнiцiального значення y0. . . . . 107
2.1.2. Тригонометричнi суми на псевдовипадкових числах, породжених iнверсними генераторами. . . . . . . . . . . . . . . . 123
2.1.3. Рiвнорозподiленiсть i непередбачуванiсть послiдовностей ПВЧ,
породжених iнверсними конгруентними генераторами. . . . . 158
2.2. Циркулярнi генератори . . . . . . . . . . . . . . . . . . . . . . . . . 171
2.3. Рiвномiрний розподiл комплексних чисел по модулю p
m в одиничному колi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
15
2.4. Послiдовностi ПВЧ, породженi елiптичною кривою над кiльцем Zpm 183
Висновки до роздiлу 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Роздiл 3. Асимптотичнi формули над кiльцем цiлих елементiв уявного квадратичного поля 192
3.1. Функцiя дiльникiв τ3(ω) в арифметичнiй прогресiї . . . . . . . . . . 192
3.2. Функцiя дiльникiв, зважена сумою Клостермана . . . . . . . . . . . 207
3.3. Норми гаусових цiлих чисел в арифметичнiй прогресiї i вузьких секторах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
3.4. Проблема елiпса на арифметичнiй прогресiї . . . . . . . . . . . . . . 226
3.5. Зображення натуральних чисел квадратичними формами . . . . . . 238
3.6. Перетворення Лапласа для пари Z-функцiй Гекке . . . . . . . . . . 249
Висновки до роздiлу 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
Висновки 259
Список використаних джерел 261
Додаток 278

Список літератури

ВИСНОВКИ
Дисертацiйна робота присвячена застосуванням методу тригонометричних сух
в проблемах генерування послiдовностей псевдовипадкових чисел, якi задовольняють умовам їх рiвномiрного розподiлу на вiдрiзку [0, 1), i розв’язанню проблем
побудови асимптотичних формул суматорних функцiй, асоцiйованих з мультиплiкативними функцiями цiлих рацiональних або цiлих гаусових чисел. Iнтерес
до цих проблем пов’язано з використанням псевдовипадкових чисел в задачах
моделювання реальних процесiв, а також для деяких мультиплiкативних функцiй над кiльцем уявного квадратичного розширення поля рацiональних чисел.
Умовно результати дисертацiйної роботи можна роздiлити на три частини: (i) будуються оцiнки повних та твiстових сум над кiльцем чисел поля Q(
√
−d); (ii)
застосовуються тригонометричнi суми спецального вигляду для оцiнки якiсностi
послiдовностей псевдовипадкових чисел, породжуваних iнверсними конгруентними генераторами; (iii) методом тригонометричних сум будуються асимптотичнi
формули для суматорних функцiй, пов’язаних з мультиплiкативними функцiями
над кiльцями цiлих рацiональних i цiлих гаусових чисел.
В першiй частинi роботи розглядаються норменi суми Клостермана над кiльцем цiлих чисел поля Q(
√
−d) та деякi узагальнення таких тригонометричних
сум.
Другий роздiл дисертацiї мiстить спецiальнi конгруенцiї, якi породжують послiдовностi псевдовипадкових чисел. Проводяться дослiдження дискрiпантної функцiї цих послiдовностей, за допомогою яких виявляється якiснiсть послiдовностей
ПВЧ.
В третьому роздiлi вивчається: (i) функцiя дiльникiв τ3(ω) в арифметичнiй
прогресiї; (ii) норми гаусових цiлих чисел в арифметичнiй прогресiї i вузьких секторах; (iii) перетворення Лапласа для пари Z-функцiй Геке; (iv) зображення
260
натуральних чисел квадратичними формами; (v) проблема елiпса на арифметичнiй прогресiї.
Основними науковими результатами дисертацiї є такi:
— оцiнки повних i змiшених тригонометричних сум над кiльцем цiлих гаусових чисел;
— новi оцiнки сум Клостермана n-го порядку над кiльцем цiлих гаусових
чисел;
— оцiнки узагальнених сум Клостермана над кiльцем цiлих гаусових чисел;
— норменi суми Клостермана n-го порядку;
— новi оцiнки дискрiпантної функцiї iнверсного генератора зi змiнним зсувом;
— побудованi iнверснi генератори другого порядку i знайденi оцiнки вiдповiдних дискрiпантних функцiй;
— побудовано сiмейство циркулярних генераторiв, доведена псевдовипадковiсть породжуваних ними послiдовностей псевдовипадкових чисел;
— дослiджено на псевдовипадковiсть послiдовнiсть, породжена лiнiйно-iнверсним генератором;
— побудовано асимптотична формула в проблемi елiпса на арифметичнiй
прогресiї;
— дослiджена асимптотична поведiнки суматорної функцiї для функцiї дiльникiв, зваженої тригонометричними одиницями;
— знайдена асимптотична формула для суматорної функцiї, асоцiйованої з
кiлькiстю зображень натуральних чисел k-тими степенями квадратичної
форми;
— дослiдженi аналiтичнi властивостi перетворення Лапласа для пари Z-функцiй Геке з зсувом