Генерування послідовностей інверсних конгруентних псевдовипадкових чисел

Размещено на http://www.allbest.ru/

Київський національний університет імені Тараса Шевченка

УДК

ГЕНЕРУВАННЯ ПОСЛІДОВНОСТЕЙ ІНВЕРСНИХ КОНГРУЕНТНИХ ПСЕВДОВИПАДКОВИХ ЧИСЕЛ

01.01.08 -- математична логіка, дискретна математика і теорія алгоритмів

А В Т О Р Е Ф Е Р А Т дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Варбанець Сергій Павлович

Київ 2010

Дисертацією є рукопис.

Роботу виконано на кафедрі математичного забезпечення комп'ютерних систем Одеського національного університету імені І.І. Мечникова

кандидат фізико-математичних наук, доцент ПЕТРУШИНА Тетяна Іванівна доцент Одеського національного університету імені І.І. Мечникова, м. Одеса, Україна

доктор фізико-математичних наук, професор ЛАУРИНЧИКАС Антанас, Вільнюський університет, завідувач кафедри теорії ймовірності і теорії чисел;

доктор фізико-математичних наук, провідний науковий співробітник ГЛАЗУНОВ Микола Михайлович, Київський національний авіаційний університет, професор кафедри інженерії програмного забезпечення.

Захист відбудеться "12" квітня 2010 року о 14.00 годині на засіданні спеціалізованої вченої Ради Д 26.001.18 при Київському національному університеті імені Тараса Шевченка за адресою: 03127, м. Київ, проспект академіка Глушкова, 6, Київський національний університет імені Тараса Шевченка, механіко-математичний факультет.

З дисертацією можна ознайомитись в бібліотеці Київського національного університету імені Тараса Шевченка (вул. Володимирська, 58).

Автореферат розіслано "4" березня 2010 р.

Вчений секретар

спеціалізованої вченої ради В.В. Плахотник

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Псевдовипадкові числа являють собою важливу складову стохастичного моделювання і сучасної криптографії. Випадкові біти необхідні не тільки для генерування криптографічних ключів, але часто вони становлять головну частину криптографічних алгоритмів. Як правило, на сьогоднішній день джерелом випадковості є псевдовипадковий числовий генератор, який являє собою детермінований алгоритм, що породжує послідовність чисел з певними статистичними властивостями, і насамперед, розподіленість за даним законом та статистична незалежність (непередбачуваність). Генератори псевдовипадкових чисел є елементами кожної системи захисту інформації, вони використовуються для розв'язання багатьох задач, таких як

* генерування гаміруючих послідовностей при перетворенні інформації за схемою найбільш близькою до схеми абсолютно стійкого шифру;

* хешування інформації;

* формування ключової інформації, на секретності і якості якої будується стійкість шифру;

* внесення невизначеності в роботу засобів захисту інформації і так далі.

Відомо, що з рівномірно розподіленій послідовності чисел можна отримати послідовність чисел з потрібним законом розподілу.

Дослідження на рівнорозподіленість і непередбачуваність послідовностей псевдовипадкових чисел (ПВЧ) суттєво cпираються на оцінки спеціальних тригонометричних сум таких, як класичні та узагальнені суми Клостерманівського типу, оцінки яких cпираються на роботи А. Вейля, П. Деліня і Е. Бомб'єрі.

Актуальність теми. Важливою вимогою до генераторів псевдовипадкових чисел є невелика обчислювальна складність реалізації алгоритму побудови членів послідовності псевдовипадкових чисел. Цій вимозі відповідають як лінійний, так і інверсний конгруентні генератори, які вивчались в роботах Лемера, Ейченауера, Лехна, Гроса, Нідеррайтера та ін. Дисертація поповнює список таких досліджень. У статтях [2],[4],[7],[8], що містять відображені в дисертації результати автора, доведено, що узагальнені генератори двох типів, які запропоновані автором, породжують послідовності псевдовипадкових чисел з властивостями рівномірнорозподіленості та непередбачуваності, причому обчислювальна складність принципово не змінюється.

У статтях автора [3],[5],[6] визначена нормена сума Клостермана над кільцем цілих гаусових чисел, яка має певні застосування в теорії псевдовипадкових комплексних чисел одиничного кола і в задачах розподілу значень деяких арифметичних функцій.

Зв'язок з науковими програмами, планами, темами. Тематика дисертації прямо пов'язана з основними дослідженнями кафедри Математичного забезпечення комп'ютерних систем Одеського національного університету імені І.І. Мечникова, які проводяться у рамках науково-дослідницької теми "Розробка методів інтелектуального аналізу даних та програмного забезпечення інформаційних і розподіленних систем" (номер державної реєстрації 0106U006199).

Мета та задачі дослідження. Побудова узагальнених інверсного та лінійно-інверсного конгруентних генераторів зі сталим та змінним зсувом. Зображення елементів послідовності псевдовипадкових чисел у вигляді поліномів від номера елемента в послідовності та початкового(ініціального) елемента. Дослідження періоду послідовності інверсних конгруентних псевдовипадкових чисел в залежності від параметрів генератору. Побудова верхніх та нижніх оцінок дискріпансії послідовностей s-мірних точок, асоційованих з послідовністю інверсних псевдовипадкових чисел. Отримання оцінок степеневої та норменої сум Клостермана над кільцем цілих гаусових чисел. Побудова асимптотичних формул для суматорних функцій для функції дільників,, з нормами в арифметичній прогресії та для, зваженої функцією або функцією. дискріпансія інверсний конгруентний генератор

Методи дослідження. Метод -адичного аналізу (для зображення ПВЧ у вигляді поліномів), метод тригонометричних сум (для оцінки дискріпансії і дослідження узагальнених сум Клостермана), методи теорій випадкових і псевдовипадкових чисел, методи аналітичної теорії чисел.

Наукова новизна одержаних результатів. У дисертації отримані такі нові результати.

* Побудовані два нових типа генераторів за модулем, - просте число: зі змінним зсувом (І тип) і лінійно-інверсний (ІІ тип), обчислювальна складність яких співпадає з обчислювальною складністю інверсного конгруентного генератора за модулем. Ці типи генераторів містять, як часний випадок, генератори, які раніш вивчались Ейченауером, Нідеррайтером та ін.

* Доведено, що для узагальнених генераторів елементи відповідних послідовностей ПВЧ мають зображення у вигляді поліномів від номеру елемента та початкового елемента послідовності, причому вид поліномів залежить від парності номера відповідного елемента.

* Знайдено нове доведення теореми про період послідовноств ПВЧ у термінах параметрів генератора.

* Отримані оцінки тригонометричних сум на послідовностях ПВЧ, породжених узагальненими генераторами за модулем як на повному періоді, так і на частині періоду. Ці оцінки покращують результати Нідеррайтера і Шпарлінського.

* Покращені верхні і знайдені нижні оцінки дискріпансії послідовностей інверсних конгруентних ПВЧ за модулем з максимальним періодом. Верхня і нижня оцінки відрізняються лише множником степені логарифма.

* Досліджені два типи узагальнених сум Клостермана над кільцем цілих гаусових чисел: степенева та нормена, причому нормені суми Клостермана не мають аналогів в кільці цілих раціональних чисел. Побудовані нетривіальні оцінки таких сум.

* Досліджено розподіл значень арифметичної функції (кількість зображень натурального сумою двох квадратів цілих чисел), зваженої тригонометричним множником.

* Побудована нова асимптотична формула для середнього значення функції дільників над кільцем цілих гаусових чисел з нормами в арифметичній прогресії.

* Знайдено аналог результату М. Ютіли для функції дільників, зваженої множником над .

* Доведено рівномірність розподілу значень добутку, де -- кількість різних простих дільників гаусового числа у вузьких секторах та коротких шарах.

Практичне значення одаржаних результатів. Результати дисертаційної роботи в основному мають теоретичний характер. Їх доцільно застосовувати для генерування послідовностей псевдовипадкових чисел великих періодів (за рахунок зростання простого і натурального ), для побудови криптографічних ключів симетричних та несиметричних криптосистем, а також в дослідженнях розподілу значень арифметичних функції над та . Результати роботи можуть також бути застосовані при дослідженнях аналітичних властивостей різноманітних функцій, котрі використовуються в аналітичній теорії псевдовипадкових чисел.

Особистий внесок здобувача. Всі резльтати дисертації отримані автором самостійно. Із спільних публікацій в дисертацію включені лише ті результати, що належать автору.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались і обговорювались на таких міжнародних конференціях: 5th International Algebraic Conference in Ukraine (Odessa, Ukraine, 2005), 9th Vilnius Conference on Probab. Theory (Vilnius, Lithuania, 2006), XI Міжнародна наукова конференція імені академіка М. Кравчука (Київ, Україна, 2006), Fourth International Conference in Honour of J. Kubilius (Palanga, Lithuania, 2006), 6th International Algebraic Conference in Ukraine (Kamyanets-Podolsky, Ukraine, 2007), XII Міжнародна наукова конференція імені академіка М. Кравчука (Київ, Україна, 2008), Numbers, functions, equations '08 (De La Motte Castle, Noszvaj, Hungary, 2008), International Conference celebrating the 60th birthday of prof. A. Laurincikas (Siauliai, Lithuania, 2008), 4th International Conference on Analytic Number Theory and Spatial Tessellations (Kyiv, Ukraine, 2008), IV Міжнародна наукова конференція для молодих вчених "Сучасні проблеми математики та її застосування у природничих науках та інформаційних технологіях" (Харків, Україна, 2009), 7th International Algebraic conference in Ukraine (Kharkiv, Ukraine, 2009), Український математичний конгрес-2009 (Київ, Україна, 2009), Humboldt Cosmos: Science and Society(-Kiev2009) (in memoriam Alexander von Humboldt 1769-1859, Kiev, Ukraine, 19-22 November, 2009).

Публікації. Результати дисертації опубліковані в 8 статтях([1]-[8]) у вітчизняних журналах із списку, затвердженого ВАК України, та провідних міжнародних фахових виданнях. Окрім того, результати деяких журнальних публікацій попередньо опубліковані в матеріалах міжнародних конференцій у вигляді тез ([9]-[17]), які додані до загального списку як свідчення опробації результатів дисертації.

Структура та обсяг роботи. Дисертація складається зі вступу, огляду літератури та результатів дисертації, двох розділів, розбитих на підрозділи, висновків і списку використаних джерел. Обсяг дисерації -- 179 сторінок. Список використаних джерел обсягом 9 сторінок включає 109 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

Вступ містить огляд літератури та результатів дисертації.

Інверсний конгруентний генератор ПВЧ за модулем задається рекурсією.

Параметри ,, вибираються такими, що забезпечують нескінченність послідовності , а значить і нормованої послідовності.

Генератор (1) був введений Ейченауером і Лехном у 1986р. і досліджувався багатьма авторами, в тому числі, Ейченауером, Лехном, Топузоглу, Гросом, Нідеррайтером, Шпарлінським та ін.

В дисертаційній роботі розглянуті узагальнення інверсних конгруентних генераторів, які містять, як спеціальний випадок, генератори (1). А саме досліджуються генератори двох типів (І) і (ІІ): за умовами -- просте число,-- натуральне.

Метою дослідження є доведення того, що відповідні послідовності ПВЧ задовільняють статистичним тестам на рівномірність та непередбачуваність.

Цей генератор уперше був досліджений Д. Лемером у 1951 р. Але для криптографічних застосувань послідовність псевдовипадкових чисел повина бути незалежною (непередбачуваною), тобто за попередніми значеннями не можна визначити . На жаль, властивість непередбачуваності не притамана лінійному конгруентному генератору. Ця обставина мотивувала пошуки нелінійних конгруентних генераторів Eichenauer J. and Lehn J. A non-linear congruential pseudorandom numbers generator, Statist. Hefte.- 27.- 1986.- P.315-326;

Eichenauer J., Lehn J. and Topuzolu A. A nonlinear congruential pseudorandom number generator with power of two modulus //Math. Comp.- 1988.- 51.- P.757-759;

Knuth D.E. The Art of Computer Programming II: seminumerical algorithms / Addison-Wesley.- 1998;

L'Ecuyer P. Uniform random number generation // Ann. Oper. Res..- 1994.- 53.- P.77--120;

Niederreiter H. Random Number Generation and Quasi-Monte Carlo Methods / SIAM, Philadelphia.- 1992..

Статистичні тести послідовностей ПВЧ, які генеруються рекурсіями (I) і (II), базуються на оцінках тригонометричних сум на елементах послідовностей псевдовипадкових чисел. З метою розповсюдження методів побудови генераторів послідовностей псевдовипадкових комплексних чисел одиничного кола та методів дослідження таких послідовностей вивчаються тригонометричні суми Клостерманівського типу над кільцем цілих гаусових чисел (так звані нормені суми Клостермана). Такі суми не мають аналогів в кільці цілих раціональних чисел. Отримані оцінки нормених сум Клостермана застосовуються також для побудови асимптотичних формул для суматорної функції і для арифметичних функцій (кількість зображень сумою двох квадратів) та зваженої функції дільників , .

Таким чином, можна вивести, що проблеми побудови нових генераторів псевдовипадкових чисел дослідження їх властивостей, розробки методів оцінок спеціальних тригонометричних сум над а також оцінок залишкових членів в асимптотичних формулах для арифметичних функцій над та, ще довгий час будуть залишатись актуальними.

Оскільки рекурсія (1)(або (I),(II)) використовується для побудови псевдовипадкових чисел і псевдовипадкових векторів, то вельми інтенсивно вивчається проблема визначення: коли послідовність має максимально можливий період. В цьому напрямку важливі результати отримані Чоу Chou W.-S. On inversive maximal period polynomials over finite fields. // Appl. Algebra Engrg. Comm. Comput.-- Vol. 6.-- 1995.-- P.245-250; The period lengths of inversive congruential recursions. // Acta Arith.-- 73(4).-- 1995.-- P.325-341., Ейченауером і Лехном Eichenauer J. and Lehn J. A non-linear congruential pseudorandom numbers generator, Statist. Hefte.-- 27.-- 1986.-- P.315-326., Флахівом і Нідеррайтером Flahive M., Niederreiter H. 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. Shine(eds.), Marcel Dekker, New York.-- 1992.-- P.75-80..

В данній роботі ця проблема також вирішується для генераторів (I) та (II).

Тому метою дослідження першої глави дисертації було побудова оцінок та для інверсного генератора типу (I), а також для лінійно-інверсного генератора типу (II). Наведемо деякі нові твердження, отримані в розділі 1.

Нехай на протязі всього розділу 1 виконуються умови -- просте число, -- натуральне,

ТВЕРДЖЕННЯ 1. Нехай послідовність породжена рекурсією д(це твердження міститься в лемах 6 та 7 з §1).

НАСЛІДОК. Для генератора (6) найменша довжина періоду породжуваної послідовності не перевищує, причому, якщо

ТВЕРДЖЕННЯ 2. Нехай послідовність породжена генератором (6). Тоді майже для всіх і кожного (див., Теорема 3, §1).

де супремум береться по всім інтервалам, -- кількість значень, які належать інтервалу , а -- довжина .

ТВЕРДЖЕННЯ 3. Нехай -- просте число і -- ціле, та нехай. Тоді для кожного і справедлива оцінка

ТВЕРДЖЕННЯ 4. Для генератора (6) майже для всіх і кожного, справедлива оцінка

Результати тверджень 1-4 кращі ніж відповідні результати подібного роду Нідеррайтера і Шпарлинського.

Узагальненням генераторів (3) і (6) є генератори типу (I). Вибір такого узагальнення викликан тим, що в криптографічних застосуваннях відповідна послідовність ускладнює спроби зловмисника відбудувати параметри генератора (I) навіть, якщо зловмиснику відомі два послідовні значення , але не відомі номери цих чисел в послідовності. І в той же час складність алгоритму (I) така ж, як і для алгоритмів генерування (3) і (6). Більш того, як доведено в лемі 2, §2 гл.1, елементи , які згенеровані рекурсією (I)(генератор інверсних конгруентних чисел зі змінним зсувом), мають зображення аналогічні тим, що вказані вище (див., формули (2),(3)). За допомогою цих зображень отримані наступні твердження.

ТВЕРДЖЕННЯ 5. Нехай -- довжина періоду послідовності для генератору зі змінним зсувом,

ТВЕРДЖЕННЯ 6. Нехай,. Справедлива наступна оцінка де -- функція Ойлера.

ТВЕРДЖЕННЯ 7. Нехай -- довжина періоду послідовності, причому,. Для, ми маємо (Твердження 6 і 7 містяться в теоремах 1-3, §2, розділ 1).

За допомогою цих тверджень отримані верхні та нижні оцінки дискріпансій послідовностей -мірних точок.

Метою третього параграфу розділу 1 було побудувати узагальнений нелінійний генератор з властивостями інверсного конгруентного генератора. Ми досліджуємо генератор псевдовипадкових чисел, визначений рекурсією (II) з умовою

Доведені такі твердження

ТВЕРДЖЕННЯ 8. Нехай. Справедливі наступні оцінки

НАСЛІДОК. Нехай, і нехай найменша довжина періоду послідовності,, яка породжується рекурсією (II). Тоді максимальне значення періоду досягається, якщо

ТВЕРДЖЕННЯ 9. Нехай -- послідовність, породженна рекурентною формулою (II), і нехай

Твердження 8, його Наслідок та Твердження 9 складають зміст Теорем 3.1-3.4.

Знайдені оцінки тригонометричних сум та дозволяють отримати досить точні верхню та нижню оцінки функції розкиду.

ТВЕРДЖЕННЯ 10. Нехай просте, і нехай і -- цілі,. Припустимо, що

ТВЕРДЖЕННЯ 11.

Твердження 9 та 10 показують, що, у загальному випадку, верхня границя для досягається з точністю до степені логарифму для узагальненої конгруентної послідовності, , визначеної рекурсією (II). Дійсно, узагальнена конгруентна послідовність з дискріпансією.

В другому розділі досліджуються тригонометричні суми Клостерманівського типу, які можуть бути застосовані для обґрунтування рівномірності розподілу та непербачуваності послідовності гаусових чисел одиничного кола або одиничного квадрату, які генеруються інверсною конгруентною рекурсією над кільцем цілих гаусових чисел . Оцінки узагальнених сум Клостермана мають і самостійний інтерес. До того ж, як доведено в дисертації, за допомогою узагальнених сум Клостермана можна вивчати розподіл значень арифметичних функцій над .

Ми називаємо узагальненою степеневою сумою Клостермана, а - норменою сумою Клостермана.

Ключовою лемою для оцінки сум (7) і (8) є наступна

ЛЕМА. Нехай -- просте число, і нехай -- множина класів лишків за модулем кільця , які мають норми, конгруентні за модулем із . Тоді -- циклічна група порядку.

НАСЛІДОК. Всі зведені класи лишків за модулем, які мають рівні норми за модулем , ми можемо записати у вигляді

Оскільки лише прості раціональні числа виду залишаються простими в, то для кожного має місце розклад в добуток простих гаусових чисел

ТВЕРДЖЕННЯ 12. Для тривіального мультиплікативного характера за модулем має місце оцінка

Це твердження міститься в теоремах 5.1-5.4.

ТВЕРДЖЕННЯ 13. Нехай -- просте гаусове число і нехай мультиплікативний характер поля класів лишків. Тоді

де -- кількість різних простих дільників натурального .

ТВЕРДЖЕННЯ 14. Нехай,. Тоді для будь-яких гаусових цілих, справедлива оцінка

ТВЕРДЖЕННЯ 15. Нехай p -- просте число, натуральне, -- гаусові цілі,. Тоді для

ТВЕРДЖЕННЯ 16. Нехай -- просте число і нехай.

ТВЕРДЖЕННЯ 17. Нехай - просте число

Твердження 14-17 складають зміст Теорем 6.2-6.5.

Слід зауважити, що нормені суми Клостермана не мають аналогу в кільці цілих чисел .

В заключних параграфах другого розділу застосовуються сформульовані вище оцінки узагальнених степеневих і нормених сум Клостермана для дослідження суматорної функції для функції дільників, яка зважена тригонометричною функцією або функцією .

Справедливі наступні твердження

ТВЕРДЖЕННЯ 18.

Цей результат можна розглядати, як аналог результатів М. Ютіли та О. Гунявого відносно середнього значення функції дільників , зваженої тригонометричним множником, і суттєво спирається на оцінки тригонометричних сум за методом Ван дер Корпута. Наслідком Твердження 18 є

ТВЕРДЖЕННЯ 19.

За схемою роботи Де Кьонинка і Катаі доведені такі твердження

ТВЕРДЖЕННЯ 20. Нехай

Тоді існують обчислювальні константи такі, що для справедлива асимптотична формула

ТВЕРДЖЕННЯ 21. Нехай. Тоді ми маємо

де та -- обчислювальні константи.

ВИСНОВКИ

В дисертації досліджується проблема побудови послідовності псевдовипадкових чисел(ПВЧ), яка задається рекурсивно за допомогою конгруенцій за модулем степені простого числа. Такі важливі характеристики як рівномірність розподілу на відрізку та непередбачуваність послідовності ПВЧ вивчається методом тригонометричних сум Клостерманівського типу. Ці суми складають важливу частину методів асимптотичної теорії чисел, за допомогою яких сьогодні досліджується розподіл значень арифметичних функцій над кільцем або.

В першому розділі були досліджені властивості узагальненого інверсного конгруентного генератора псевдовипадкових чисел. Були знайдені умови, при яких послідовність псевдовипадкових чисел має максимально можливий період. Побудовані описи елементів узагальненої інверсної конгруентної послідовності псевдовипадкових чисел як поліномів від номера елемента, або як поліномів від початкового значення послідовності. За допомогою таких описів знайдені нові оцінки тригонометричних сум на елементах псевдовипадкової послідовності і покращені оцінки зверху для функцій розкиду одно-, двох-, трьохмірних точок, які породжуються згенерованою відповідним інверсним генератором послідовністю. Причому ці оцінки функцій розкиду(дискріпансій) близькі до оптимальних. Такі оцінки дозволяють стверджувати, що узагальнені інверсні генератори (розглянуті в I розділі) проходять дво- і трьохмірні серіальні тести на непередбачуваність. Доведено, що для кожного, і майже для всіх ініціальних значень інверсної конгруентної послідовності періоду функція розкиду не перевищує.

В другому розділі визначені нові тригонометричні суми Клостерманівського типу над - нормені суми Клостермана, які не мають аналогу в кільці . Побудовані нетривіальні оцінки таких сум (теореми 5-9). Знайдена нова асимптотична формула для суматорної функції, яка асоційована з функцією дільників над кільцем цілих гаусових чисел у вузьких секторах та з нормами в арифметичній прогресії (з розтучою різницею прогресії). Побудован аналог асимптотичних оцінок М. Ютіли та О. Гунявого для середнього значення функції (число зображень натурального сумою двох квадратів), зваженої функцією (для широкого класу функцій). За допомогою цього результату досліджено розподіл значень функції.

Побудована асимптотична формула відповідної суматорної функції. Такого типу результати важливі для вивчення -функції Геке із зсувом.

Крім того, методом Де Кьонінка-Катаі за допомогою аналогу теореми Рамачандри досліджена поведінка середнього значення функції у вузьких секторах для і коротких інтервалах для. Результати глави II можуть бути застосовані для генерування псевдовипадкових комплексних чисел і для вивчення вижливих арифметичних функцій над.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

[1] Prosyanjuk N. On the average order of over the Gaussian integers [text] / N. S. Prosyanjuk, S. P. Varbanets // Proc. Sci. Seminar Fac. Phys. Math. 2005. Vol.8. P.104-125.

[2] Varbanets S. Exponential sums on the sequences of inversive congruential pseudorandom numbers [text] / S. Varbanets // Љiauliai Math. Semin. 2008. 3(11). P.247-261.

[3] Varbanets S., General Kloosterman sums over ring of Gaussian integers [text]/ S. Varbanets // Укр. Мат. журн. 2007. 59, №9. С. 1179-1200.

[4] Varbanets S., On inversive congruential generator for pseudorandom numbers with prime power modulus [text] / S. Varbanets // Annales Univ. Sci. Budapest, Sect. Comp. 2008. 29. P. 277-296.

[5] Varbanets S., The Norm Kloosterman Sums Over Z[i] [text]/ S. Varbanets // Anal. Probab. Methods Number Theory. 2007. P. 225-239.

[6] Varbanets P., On divisor function over Z[i] [text] / P. Varbanets, S. Varbanets // Annales Univ. Sci. Budapest, Sect. Comp. 2007. 27. P. 75-90.

[7] Varbanets P., Exponential sums on the sequences of inversive congruential pseudorandom numbers with prime-power modulus [text] / P. Varbanets, S. Varbanets // VoronoЇ's Impact on modern science, Proceedings of the 4th International Conference on Analytic Number Theory and Spatial Tessellations, Book 4, Volume 1, Kyiv, Ukraine. September 22-28, 2008. P. 112-130.

[8] Varbanets S. P. Inversive congruential generator with prime power modulus [text] / S. P. Varbanets// Вісник Одеського нац. ун-ту. 2008. Т. 13.- Вип. 17. Матем. і механ. С. 86--102.

[9] Briginets A. On some cryptosystem based on cyclical codes [text] / A. Briginets, S. Varbanets // 5th International Algebraic Conference in Ukraine, 2005, Odessa, Ukraine.

[10] Varbanets S. The weighting function of divisors over Z[i] in the narrow sectors [text] / S. Varbanets // 5th International Algebraic Conference in Ukraine, 2005, Odessa, Ukraine.

[11] Varbanets P. General Kloosterman sums over Z[i] [text] / P. Varbanets, S. Varbanets // 9th Vilnius Conference on Probab. Theory, 2006, Vilnius, Lithuania.

[12] Варбанець С.П. Нормені суми Клостермана та їх застосування в криптографії [текст] / С. П. Варбанець // XI Міжнародна наукова конференція імені академіка М. Кравчука, 2006, Київ, Україна.

[13] Varbanets S. Carmichael function over the ring of the Gaussian integers [text] / S. Varbanets //6th International Algebraic Conference in Ukraine, 2007, Kamyanets-Podolsky, Ukraine.

[14] Varbanets S. Distribution of inversive congruential pseudorandom numbers with prime-power modulus [text] / S. Varbanets // XII Міжнародна наукова конференція імені академіка М. Кравчука, 2008, Київ, Україна.

[15] Varbanets S. Exponential sums on the sequences of inversive congruential pseudorandom numbers [text] / S. Varbanets // 7th International Algebraic conference in Ukraine, 18-23 August, 2009.

[16] Варбанець С.П. Інверсні конгруентні генератори псевдовипадкових чисел [Електронний ресурс]. Режим доступу: http://www.imath.kiev.ua/congress2009/Abstracts/Varbanetz.pdf / С.П. Варбанець // Український математичний конгрес. 2009.

[17] Varbanets S. General Kloosterman Sums over and their Applications [text] / S. Varbanets // International Conference of Humboldt-Kolleg Series in Kiev "Humboldt Cosmos: Science and Society"(-Kiev2009), Kiev, Ukraine, 19-22 November, 2009.

АНОТАЦІЯ

Варбанець С.П. Генерування послідовностей інверсних конгруентних псевдовипадкових чисел. -- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 - математична логіка, дискретна математика і теорія алгоритмів. -- Київський національний університет імені Тараса Шевченка, Київ, 2010.

Дисертація присвячена задачам побудови послідовності псевдовипадкових чисел (ПВЧ) за допомогою рекурсії, яка задається конгруенціями лінійно-інверсного типу за модулем степені простого числа, і огрунтуванню рівнорозподіленості і непередбачуваності породженої послідовності. Інверсні конгруентні генератори за модулем степені простого числа дозволяють суттєво збільшити довжину періоду породжуваємої послідовності ПВЧ в порівнянні з довжиною періоду послідовності ПВЧ за модулем простого числа, причому властивість непередбачуваності покращується. Знайден конструктивний опис елементів послідовності ПВЧ узагальнених генераторів в термінах поліномів від номеру елемента послідовності та її ініціального значення, що призвело до побудови нового доведення теореми про мінімальну довжину максимального періоду послідовності ПВЧ, а також дозволило знайти покращені верхні оцінки і нові нижні оцінки дискрипантної функції. Введені поняття степеневої та норменої сум Клостермана над кільцем цілих гаусових чисел. Знайдені нетривіальні оцінки таких сум. За допомогою узагальнених сум Клостермана побудовані асимптотичні оцінки суматорної функції для функції числа дільників цілих гаусових чисел, які зважені спеціальними арифметичними функціями.

Ключові слова: інверсний генератор псевдовипадкових чисел, непередбачуваність елементів послідовності, дискрипантна функція, тригонометрична сума, цілі гаусові числа, нормена сума Клостермана, функція дільників.

АННОТАЦИЯ

Варбанец С.П. Генерирование последовательностей инверсных конгруэнтных псевдослучайных чисел. -- Рукопись.

Дисертация на соискание ученной степени кандидата физико-математических наук по специальности 01.01.08 -- математическая логика, дискретная математика и теория алгоритмов.-- Киевский национальный университет имени Тараса Шевченка, Киев, 2010.

Диссертация посвящена задачам построения последовательностей псевдослучайных чисел(ПСЧ) с помощью рекурсий, задаваемых конгруэнциями линейно-инверсного типа по модулю степени простого числа, и обоснованию равнораспределенности и непредсказуемости порожденной последовательности, причем особое внимание уделяется вопросам оценки специальных тригонометрических сумм Клостермановского типа, которые имеют много приложений, и, в частности, в проблеме построения нетривиальных оценок дискрипантной функции получаемой последовательности.

Инверсные конгруэнтные генераторы по модулю степени простого числа позволяют существенно увеличить длину периода порождаемой последовательности ПСЧ по сравнению с длиной периода последовательности ПСЧ по модулю простого числа. Этим вопросам посвящены исследованию Эйченауэра, Лехна, Топузоглу, Гроса, Ниддерайтера, Шпарлинского и др. Мы обобщаем генераторы ПСЧ, изучаемые указанными авторами, причем вычислительная сложность обобщенных генераторов не изменяется, но качество непредсказуемости ПСЧ обобщенных генераторов улучшается.

Найдено конструктивное описание элементов последовательности ПСЧ обобщенных генераторов в терминах многочленов от номера элемента последовательности и ее инициального значения, что позволило дать новое доказательство теоремы о минимальной длине максимального периода последовательности ПСЧ, а также получить улучшенные верхние оценки и новые нижние оценки для дискрипантной функции сгенерированной последовательности ПСЧ.

Вводится понятие степенной суммы Клостермана над кольцом целых гауссовых чисел как обобщение введенного Канемицу, Танигава, Юанем и Венпенгом понятия общей суммы Клостермана над кольцом целых чисел, а также введено понятие норменной суммы Клостермана над кольцом целых гауссовых чисел, аналога которой нет в кольце целых рациональных чисел. Получены нетривиальные оценки таких сумм (возможно эти оценки неулучшаемы). Эти суммы найдут применение в задачах оценки дискрипантной функции последовательности ПСЧ в единичном круге комплексных чисел.

С помощью найденных оценок обобщенных сумм Клостермана исследован ряд задач о распределении значений арифметических функций над кольцом целых гауссовых чисел, в частности, построены асимптотические оценки сумматорной функции для функции числа делителей целых гауссовых чисел, взвешенной специальными арифметическими функциями, что является обобщением результатов М. Ютилы, О. Гунявого, Де Кенинка и Катаи.

Ключевые слова:инверсный генератор псевдослучайных чисел, непредсказуемость элементов последовательности, дискрипантная функция, тригонометрическая сумма, целые гауссовые числа, норменная сумма Клостермана, функция делителей.

SUMMARY

Varbanets S.P. Generation of the sequences of inversive congruential pseudorandom numbers.-- Manuscript.

Thesis of the degree of Candidate of Physics and Mathematics in speciality 01.01.08 -- the mathematical logic, the discrete mathematics and the theory of algorithms.-- Taras Shevchenko National University of Kyiv, Kyiv, 2010.

The thesis is devoted to problems of construction of the sequences of inversive congruential pseudorandom numbers (PRNs) generated by the congruences of linear-inversive type with prime-power modulus, and the substantiation of equidistribution and unpredictability of generated sequence. The inversive congruential generators with prime-power modulus permit to increase essentially the length of period of the generated sequence of PRNs comparatively with the length of period of the inversive congruential sequence of PRNs with prime modulus? where the property of unpredictability ameliorates. We give the constructional description of elements of the sequence of PRNs of generalized such generator in terms of the polynomials of number of an element of the sequence and its initial value. That permit to obtain a new proof of the theorem on the least period length of the possible values of periods of the inversive congruential sequence of PRNs, and also permit to find the improved upper estimates and new lower estimates the discrepancy. We introduced the notations of the power and norm Kloosterman sums over the ring of Gaussian integers and give the non-trivial estimates for such sums. These estimates are applied to a construction of the asymptotic formulas for summatory functions for the divisor function weighted by the special arithmetic functions.

Keywords: inversive generator of PRNs, unpredictability of elements of sequence, discrepancy, exponential sum, norm Kloosterman sum, divisor function.

Размещено на Allbest.ru