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

на правах рукописи

КАЛУГИН Александр Николаевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МНОГОМЕРНЫХ ГЕНЕРАТОРОВ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ ПСЕВДОСЛУЧАЙНЫХ ВЕКТОРОВ, ОСНОВАННЫХ НА ПРЕДСТАВЛЕНИИ ДАННЫХ В АЛГЕБРАИЧЕСКИХ ПОЛЯХ

.V

Специальность 05 13 17-Теоретические основы информатики

Автореферат

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

003171697

Самара 2008

003171697

Работа выполнена на кафедре геоинформатики государственного образовательного учреждения высшего профессионального образования "САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ им ак. С.П. КОРОЛЕВА" (СГАУ), и в ИНСТИТУТЕ СИСТЕМ ОБРАБОТКИ ИЗОБРАЖЕНИЙ РОССИЙСКОЙ АКАДЕМИИ НАУК

Научный руководитель

доктор физико-математических наук В.М.Чернов

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

СЛ.Шатских,

кандидат физико-математических наук, доцент Э.И.Коломиец.

Ведущая организация.

Омский государственный университет ■•^м ФМ Достоевского

Защита планируется " 20 " июня в 10 часов на заседании диссертационного совета Д 212.215 07 в Самарском государственном аэрокосмическом университете имени академика С.П.Королева по адресу. 443086, г. Самара, Московское шоссе, д 34

С диссертацией можно ознакомиться в библиотеке Самарского государственного аэрокосмического университета имени академика С.П Королева *

Автореферат разослан " 19 " мая 2008 г

Ученый секретарь диссертационного совета, д.т к., профессор

■»•¿чье"

И В Белоконов

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

Актуальность исследования. Разработка методов построения и исследование свопств детерминированных последовательностей точек многомерного пространства, обладающих признаками "случайности", понимаемой относительно того или иного вероятностного критерия, является фундаментальной задачей Для нее, с одной стороны, характерно использование развитых методов современной абстрактной математики (алгебра, теория чисел), а, с другой стороны, её прикладная значимость в информатике и вычислительной математике возрастает, в связи с бурным развитием методов численного моделирования с использованием высокоскоростных (в том числе и параллельных) вычислительных устройств и спецпроцессоров, развитием методов криптографии, использованием таких последовательностей при тестировании VLSI систем, в компьютерных играх, и т д

Теория генераторов псевдослучайных последовательностей (генераторов случа! ных чисел, ГСЧ) — детерминированных алгоритмов, порождающих последовательности, свойства которых "имитируют" свойства последовательности реализаций независимых одинаково распределенных случайных величин — берет свое начало в 1946 год) с предложенного Дж Фон Нейманом метода "средин квадратов" Возникнув изначально как попытка синтезировать метод генерации псевдослучайной выборки, лишенный недостатков физических датчиков случайных чисел и таблиц случайных чисел, методоюгия генерирования псевдослучайных последовательностей получила в дальнейшем б) оное развитие как самостоятельное направление Данные методы, исследовались мно.нми авторами П Лемером (Р Lehmer), КС Таусвортом (К С Tausworth), Д Кнутом (D Kutth) Г Нидеррайтером (НNiederreiter), П Хеллекалеком (Р Hellekalek), П Леквие (Р 1'Еылег) Дж Марсальей (С Marsaglia), С Вегенкиттлом (S Wegenkittl) и др К настоящему врепени разработаны различные методы генерации псевдослучайных последовательностей линейный конгруэнтный генератор (linear congruential generator), регистр сдвига с линейной обратной связью (linear feedback shift register), регистр сдвига с обобщенной обратной связью (generalizedfeedback shift register), генератор Фибоначчи с запаздываниями (lagged-FiboiuuLi generator), инверсный генератор (mversive generator), множественный рекурсивный генератор (multiple recursive generator) и др

Большинство разработанных и детально исследованных на настоящий момент генераторов являются одномерными Однако существуют вычислительные задачи (например численное вычисление значения многомерного определенного интеграла по метод) Монте Карло, задачи статистической физики и др), требующие генерации последоватечъности псевдослучайных векторов многомерного пространства Теория генерации псевдостуча шых векторов является относительно новым направлением, к настоящему моменту разработано лишь несколько "естественно" многомерных генераторов матричный конгруэнтный генератор (matrix generator), матричный инверсивный генератор (matrix inverse generator) матричный множественно-рекурсивный генератор (multiple-recursive matrix generator) генератор С. Вольфрама, основанный на использовании клеточного автомата Достоинством данной группы методов является теоретически доказанное и положенное в основ) метода генерирования соответствие порождаемого распределения теоретическому в многомерном пространстве размерности, равной размерности генерируемых векторов (относительно предварительно заданных критериев качества) К недостаткам этой группы можно отнести принципиальную невозможность эффективной параллельной реализации, так, например, ля матрично-рекурсивного метода для генерации сой координаты очередного

псевдослучайного вектора, (/ = 0,1,...,к-1, к— размерность генератора) необходимы значения всех координат предыдущих h векторов (AeN — параметр генератора, порядок матричного рекуррентного соотношения).

Альтернативным подходом к генерации многомерных (параллельных) псевдослучайных последовательностей являются методы "повышения размерности", основанные на распределении элементов одной или нескольких одномерных псевдослучайных последовательностей среди генерирующих процессоров (т. н. метод кругового обхода (leapfrog), метод блоков (sequence splitting), метод параметризации {sequence parameterization and initialization). Основной идеей, положенной в основу синтеза данных методов, является возможность их эффективной параллельной реализации на нескольких компьютерах / процессорах. Однако многомерное распределение синтезированных точек на выходе "параллелизованных" генераторов может иметь существенные отклонения от теоретического (уровень которых может варьироваться от едва заметных до абсурдно очевидных) в терминах широкого круга критериев. В качестве примера таких недостатков рассмотрим структуру множества элементов полного периода последовательности на выходе "параллелизованного" генератора Randu:

1 с.6 о.< о.; \

fffipT

1&Щ§ S ¡ь ?.«й!1й6 Щ } 0.6

ffiitf; О.й

\ iШШШмI 9 Я I ; 1 » ■¿щшИ I 1 iJjOTft 1 fell и Illllll 0.1 0.2

f f * О

Рис. I. Распределение трехмерных векторов, сформированных методом кругового обхода, из элементов последовательности Randu.

Актуальной и практически значимой представляется задача синтеза методов генерирования, комбинирующего положительные свойства как "естественно" многомерных, так и "параллельных" генераторов псевдослучайных последовательностей, лишенных описанных недостатков.

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

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

Научная новизна работы. В диссертационной работе получены следующие новые научные результаты:

1) предложена новая схема синтеза генераторов равномерно распределенных псевдослучайных векторов, экстраполирующая методы синтеза одномерных ГСЧ на многомерный случай, базирующаяся на использовании канонических систем счисления;

2) получены аналитические оценки, характеризующие распределение последовательностей

точек многомерных пространств, сгенерированных обобщенным ГСЧ Таусворта, на полном и неполном периоде, статистическую независимость элементов последовательности на выходе генератора, 3) доказана возможность параллельной реализации разработанного обобщенного метода Таусворта и получены оценки ее вычислительной сложности

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

Теоретическая значимость работы. В работе предложен новый общий подход к экстраполяции на многомерный случай методов синтеза одномерных генераторов псевдослучайных чисел, использующих представление данных в позиционных системах счисления, описана методология исследования обобщенных генераторов

Апробация работы. Основные результаты диссертации докладывались на 10 международных, всероссийских и региональных научных конференциях, в частности, международной конференции "Automation, Control, and Information Technologies" (ACIT). Новосибирск, 2005, научно-технической конференции с международным участием "Перспективные информационные технологии в научных исследованиях проектировании и обучении" (ПИТ), Самара, 2006,7-ой международной научной конференции "Monte Carlo and Quasi-Monte Carlo methods in Scientific Computing", Ульм, Германия, 2006, международной научной конференции "Graficon-2007", Москва, 2007

Исследования по теме диссертационной работы выполнялись при поддержке РФФИ (проекты №№, 03-01-00736, 06-01-00722), Американского фонда гражданских исследований и развития в рамках российско-американской программы "Фундаментальные исследования и высшее образование", министерства образования и науки Самарской области (грант 2005 года студентам, аспирантам и молодым ученым)

Публикации. По тематике, непосредственно связанной с содержанием диссертации, опубликовано 10 работ, из них 4 опубликованы в ведущих рецензируемых научных журналах и изданиях, определенных Высшей аттестационной комиссией Работы [1, 2, 3, 4, 5, 6, 7, 8] выполнены автором единолично, остальные работы написаны в соавторстве. На защиту выносятся только результаты, полученные лично соискателем

Структура диссертации. Диссертационная работа, содержащая 159 стр, состоит из введения, пяти глав, заключения, списка использованной литературы, составляющего 107 наименований

Краткое содержание работы

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

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

Основная идея. Элементы последовательностей на выходе одномерных ГСЧ, используемых для численного моделирования (как результат конечности разрядной сетки

вычислительной платформы, выбранной для реализации алгоритма генерации), являются рациональными числами множества Л:

л;(л)еЛ = [0,1)0^-2, и = 0,1,

где * —длина машинного слова, точность разрядной сетки компьютера.

В двоичной системе счисления каждый элемент А множества Л может быть представлен в виде

А = (!) где элементы разложения аг, г = 0,1, ,1-1 образуют бинарный з -мерный цифровой вектор а(Х):а = (а0,а>. ,в_,)е{0,1}', в,е{0,1}, г = 0,1, ,5-1.

Таким образом, можно считать, что на выходе любого одномерного ГСЧ порождается последовательность бинарных цифровых векторов 3(*(п))е {0,1}' размерности «.

Концепция позиционных систем счисления может быть обобщена на многомерный случай. В 1975 г. Катай (I КсИт) и Сабо (./ БгаЬд) в своей работе1 доказали существование систем счисления вида (-Я±1,{О В1)), В&1* и представимость любого целого гауссова числа (комплексного числа с целочисленными действительной и мнимой частью) в виде конечной суммы.

* ,

г = а + 6/ = £г (-В±«)/, 2,е{0 а,Ье2, В<=Х\ у-о

с некоторым к = к(г), зависящим от г

Исследование таких позиционных систем счисления было продолжено Й. Тусвандлером (./ ТИигна1с1пег), А Пето (А Ре1Ид), С. Акиямой (5 АЬуата), А Ковачем (А Кочасз) А Ковач в своей работе2 вводит понята^ канонических систем счисления (КСС) в многомерных решетках Л. Каждому элементу решетки в канонической системе счисления ставится в соответствие вектор цифр

Конструктивно доказано, что для любого к г 2, д-значные (д>£2, ^еН) канонические системы счисления существуют

Теория канонических систем счисления дает возможность использовать идеи, реализованные в одномерных генераторах псевдослучайных чисел, для построения их многомерных аналогов, а именно, при формальной замене в соотношении (1) основания обычной позиционной системы счисления на основание системы счисления в многомерной решетке заданной размерности, каждому цифровому вектору ставится в соответствие вектор многомерного пространства. Целесообразность такой замены с точки зрения качества равномерного распределения на выходе синтезированного генератора подлежит дальнейшему изучению, что и послужило мотивацией для постановки указанной выше цели работы и определило задачи диссертационного исследования

Задачи диссертационной работы: 1) теоретическое обоснование возможности синтеза генераторов псевдослучайных последовательностей векторов (КСС-генераторов) с использованием теории канонических систем счисления в решетках, синтез обобщенного генератора Таусворта.

1 Kauu, L Canonical number systems for complex integers [Text] /1 Katai, J Szabo // Acta Sci Math (Szeged) — 37— 1975 — pp 255—260

Kovacs A. On number expansions in lattices [Text] /A. Kovacs // Proc 5th Intemation Conference on Applied Informatics/ Eger, Hungary —2001

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

3) аналитическое исследование многомерного распределения на выходе предложенного обобщенного генератора Таусворта (на полном и неполном периоде), исследование статистической независимости отсчетов генерируемой последовательности,

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

5) численное исследование свойств последовательностей на выходе генератора на участке периода, сравнение предложенного генератора с существующими схемами

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

В первой главе представлены необходимые сведения из теории алгебраических полей, дискретных решеток Рассматриваются некоторые свойства показательных и рекуррентных функций в конечных полях, тригонометрические суммы и суммы характеров с показательными функциями Приводятся базовые определения и результаты из теории канонических систем счисления, теории множеств с малым отклонением

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

Определение 1.6}. Пусть {а^а,, ,а4_,} — множество линейно независимых векторов пространства R' Линейная оболочка с целыми коэффициентами Л векторов {50,а„ называется (дискретной) решеткой в R' с базисом а = {а0,5,, ,5,.,} Л = {|| | = #050 + #,5,+

где £ eZ, / = 0,1,

В разделе 1.4 рассматриваются канонические системы счисления (КСС) в решетках, введенные в работах венгерского математика А Ковача. Эти канонические системы счисления используются далее в диссертационной работе для синтеза многомерного обобщения одномерных ГСЧ

Пусть Л - решетка в Rr, ireN, М Л-»Л — линейное отображение такое, что det(A/)*0 и D —конечное подмножество Л, заданное соотношением

D = {аё\ё = (1,0,0, ,0), б Л, а = 0,1, ,|detM|-l) (2)

Определение 1.10. Тройка (Л,M,D) называется канонической системой счисления, если любой элемент х е Л может быть единственным образом представлен в виде

* = = EU'. d, еÓ, leti (3)

Оператор M при этом называется основанием системы счисления, D — множеством цифр, вектор Л/) - КСС-кодом элемента х.

Лемма 1.1. (Классы Ковача) Для множеств цифр D вида (2) и различных значений размерности **> 2 тройки (Z',Mf,D) являются системами счисления для следующих классов многочленов / е Z[x]

/ =х* +c,x+q, если и только если -lse, ¿q-2, q>2, q- p, (4)

/2 = x' + px"' + px"1 + +px + p, 2й peN, q = p , (5)

3 Нумерация определений, утверждений и таблиц в автореферате соответствует нумерации в диссертационной работе

ft= x'+x'~,+x"I + +X + P, 2SpeN , q = p\ (6)

+ 2ipeN, q — p'. (7)

В Разделе 1.5 приводятся основные определения теории отклонений, множеств с малым отклонением

Пусть Г = [0,1)"" — *■-мерный единичный гиперкуб. Пусть далее множество точек Р -г- подмножество 1К Р = {х1,х1, ,хк}, РсГ=[0,1)' Пусть В — произвольное подмножество Bel'. Определим величину

А(В,Р) = £ся(х.),

где с„ — характеристическая функция множества В. Таким образом, А(В,Р) — функция-счсгчик, значения которой равны количеству индексов л , \<.n<.N таких, что 3„ е В.

Пусть 2 — непустое семейство измеримых по Лебегу подмножеств единичного гиперкуба /'.

Определение 1.1. Отклонением {discrepancy) множества точек Р относительно семейства S называется величина, определенная соотношением

U(B,P)

D„CB,P) = sup

Btb

Card{P)

Определение 1.14. "Звездное" ^уклонение (star-discrepancy) D'„(P) = D'N(x„x2, ,5Д) множества точек Р определяется соотношением

Dl(P) = DAJ\P), (8)

»

где J' — семейство всех подмножеств единичного гиперкуба Jk вида J' = |~[[0,ц)

el

Также в разделе 1 5 приводится определение и формулировка основных результатов из теории (t,m,k) -сетей

Во второй главе рассматривается схема экстраполяции методов синтеза ГСЧ на многомерный случай (синтез КСС-генераторов).

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

Схема состоит из трех этапов. *

Этап 1. Генерация последовательности цифровых векторов с использованием некоторого рекуррентного процесса / (функции перехода)

У (л+т) = /(У (0), У (1), ,У(л+т-1)), ВДеО- =(Z,)\ л = 0,1, , *eN

Этап 2. Интерпретация цифровых векторов

У(л) = (Г»,У,(«), ,Г,-,("))> какКСС-кодов элементов в q-значной канонической системе счисления (Z'.M.D)

¿(и) = 2уу(л)(М'-'-'е-) , Zr, л = 0,1, (9)

у-о

Этап 3. Преобразование точки х(п) е Ъ", полученной на втором этапе, в точку регулярного множества/* (многомерного единичного гиперкуба) й(") = g(x(n)), й(л)еГ = [0,1)'.

Отметим, что на втором этапе цифровым векторам ?{п) ставится в соответствие

Рюмины х (п) решетки \ соответствующих всем возможным $ -мерным цифровым векторам.

Определение 2.3. Назовем фундаментальной областью И КСС-генератора множество ; сех возможных элементов решетки I", имеющих в качестве КСС-кода цифровой вектор размерности 5

| Г^йй^и/М'ё), и,€{0,...,9-1}|. 1 I

Фундаментальная область /ССС-генератора представляет собой множество со сложной геометрической конфигурацией (см. рис. 2).

Рассмотрим множество точек х(п) решетки

| Рис. 2 — Примеры фундаментальных областей КСС-генераторов, использующих к = 3 -! мерные канонические системы счисления (Ж* , М, О) с различными основаниями.

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

I Определение 2.4. Будем называть покрытием решетки 2*' множество :

Ли0(5)=и(5 + <5),Т«0(5) = г',

а множества Б, = (5+¿5) элементами покрытия (.!>), если выполняются условия: 1 ^ п ^ * 0, если и только если щ = 32, <а,, а>г е П, где £2 с 2К — некоторая решетка. 1 Теорема 2.1. Пусть /•" — фундаментальная область КСС-генератора, тогда

firiQlir-rilJ W —

"'в»

такая., что

существует ре множество Тез0(/Г) является покрытием решетки V.

Определение 2.5. Назовем унификацией фундаментальной области Г взаимнооднозначное отображение фундаментальной области КСС-генератора ^ в единичный гиперкуб Г: Р:->/".

В диссертационной работе, рассматривается метод построения унифицирующего отображения, а именно, выделение гиперкуба из покрытия решетки 2*' фундаментальными областями генератора. В этом случае отображение Р удовлетворяет соотношению:

1 \й, при йеа']*,

Р(и) = —, . , ,

q \ü' = ü + a, aeCl(F) :(й е q I' eq ¡k J при ü<tql .

(10)

i

В работе доказана следующая теорема

Теорема 2.2. Пусть задано количество цифр q и произвольная размерность канонической системы счисления лг е N Для КСС-генераторов, использующих размерность цифрового вектора ¡ = кг (/—параметр генератора, определяющий его период, и зависящий от используемой КСС) и канонические системы счисления, порожденные тремя из четырех классов Ковача (Лемма 1 1)

— многочленами /2=хк + рхк~* + рх*'1 + +рх + р, ц = р;

— многочленами /¡=х" + <7, если и только если <7 > 2, <7 = р ;

— многочленами /4= х'+ рх"]+р2х"'г + +р"'х + р', 2 5 р е N. <7 = рк., 2 й ре N.

= и Н0К(*г,*-+1)/*-,пбтЛ возможно эффективное вычисление координат унифицированного образа точки й е /г методом выделения куба из покрытия Те$(Г) решетки 2.к фундаментальными областями генератора с использованием соотношения

и^д-'й/тоад'), (11)

где й, - наименьший неотрицательный вычет класса и, (шос1 </).

Также в работе показано, что для КСС-генераторов, использующих канонические системы счисления, порожденные многочленами /, =*' +**"' + + +х+р, 2<реИ , ^-р прил- = 23, ,9, е {2,3,5,7}, г = 2, ,100, отображение (10) не является инъективным, и следственно не существует унификации методом выделения гиперкуба из покрытия Тев^) !

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

Определение 2.2. Назовем обобщенным генератором Таусворта (генератором КСС-генератор. использующий последовательность цифровых векторов {?(")), определенную соотношением,

У(п) = (у(пЦ,у(пЬ + \), ,д>(л£ + *-1)), л = 0,1, ,

где _!(/!) — линейная рекуррентная последовательность порядка т над полем

максимального периода Г = -1, удовлетворяющая соотношению

.\(п) + ат1,у(п-1)+ + а0у(п - т) = О, а0, ,ат_, еР,, ао*0, (_у(0), ,>(ш-1))*0, где £ назовем шагом генератора ЬРБ^СЫЗ, а — размерностью цифрового вектора

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

Третья глава работы посвящена аналитическому исследованию свойств многомерного распределения на выходе генератора ЬРБЯ-СЫБ.

Основными теоретическими тестами псевдослучайных последовательностей являются вычисление | периода псевдослучайной последовательности; исследование равномерности псевдослучайной последовательности (соответствие теоретическому распределению), исследование "геометрической" структуры последовательности на выходе генератора, исследование автокорреляции псевдослучайной последовательности В третьей главе получены следующие основные результаты Лемма 3 1. Если шаг I генератора удовлетворяет соотношению

НОД(Цдт-1) = 1, (12)

о последовательность на выходе ЬРБЯ-СМБ является последовательностью периода

Для исследования равномерности и статистической независимости множества точек на олном периоде генератора LFSR•CNS рассмотрим множество векторов |

/> = {*„,*„ /1 = 0,1, ,Г-1, I

де {*„} -- выходная последовательность обобщенного генератора.

В случае если к = 1, исследование равномерности распределения элементов множества Р соответствует исследованию равномерности распределения на выходе генератора ¿/З'Л-А/5 В случае если ¿>1, исследование равномерности распределения точек множества Р в ногомерном кубе эквивалентно исследованию статистической независимости элементов на ыходе генератора

Для генератора LFSR-CNS два случая требуют различного подхода при исследовании 1) случай низких размерностей (к^тИ) и (2) случай высоких размерностей (к\>тИ) В работе доказаны следующие утверждения

Лемма 3.1. Пусть кйтИ, пусть И е пГк Пусть далее 2(И) - количество

я'

ндексов п, 05л<Г = <7"-1, такое что Хп =А, тогда |

(п)

Из соотношения (13) следует, что на выходе генератора ¿/ЗД-СЖ генерируются все очки многомерного единичного куба, координаты которых являются рациональными телами со знаменателем <}' Если к = 1, т =«, то на выходе генератора порождаются все 1

очки множества — Ъ" п/*' , кроме нулевой, каждая по одному разу

Я I

Теорема 3.1. При ki.mlL, Сагё(Р) = Т, звездное отклонение 0^">\Р) множества очек Р удовлетворяет неравенствам

1-а _,-<)"

Я -1

н,1

1 (И)

Неравенство в правой части соотношения (14) является следствием удаления нуля из

ножества точек куба—7? п!"к В случае если множество Р дополнено нулевой I точкой, Я

оотношение (14) может быть переписано в виде I

= 1-(1-<Л" , (15)

Заметим, что отклонение множества точек на полном периоде, например, известного атричного генератора многомерных векторов, удовлетворяет соотношению (15) Если оординаты точек на выходе генератора LFSR-CNS являются рациональными числами со наменателем ц', данное соотношение является лучшим возможным, и является следствием дискретизации" координат точек на выходе генератора I

Если в качестве критерия равномерности используется /ССС-отклонение. то праведливо утверждение I

Теорема 3.5. При к = 1, для последовательности на выходе генератора ¿/^Д-СЛ'З, праведлива следующая верхняя оценка КСС-откпонения '

D" (Я) 2 С

JV

(16)

Из соотношения (16) следует, что определенные аналитические гарантии качества распределения точек на выходе генератора LFSR-CNS могут быть получены для участка периода длины N>J¥ При N < -Jf оценка(16) является более слабой, чем тривиальная

Для случая высоких размерностей (с использованием обобщения (t,m,k) -сетей) доказаны следующие утверждения

Теорема 3.6. к - мерное CNS-откяонение канонической (i,m,k)-cemu Р, card{P)=N в Fg по основанию 2 удовлетворяет соотношению

или

MJTVJS^JI^-L) (log Л')'"' +0(2'(logN)'~J)

Теорема 3 7. Для k>m/L, рассмотрим множество из q" точек

Р- {б,х0,*|, ,xrJ, где согласно определению генератора LFSR-CNS

где \„ — Э1емент последовательности LFSR-CNS с индексом п Множество Р образует обобщенную (t,m,k)-cemb в q-значной канонической системе счисления (Z*,M,D) с параметром /, удовлетворяющим соотношению

t = m-r«\A,s),

где г(1с\л —величина, зависящая от характеристического многочлена А используемого рекуррентного соотношения

Путем выбора характеристического многочлена А можно добиться увеличения или ¡.ченьшения величины D^ 'v,s(*1 для конкретного генератора.

В четвертой главе проводится дополнительное аналитическое исследование распределения координатных последовательностей на выходе генератора LFSR-CNS и зависимосги| свойств распределения на выходе генератора от его параметров Доказаны следующие основные утверждения

Лемма 4.2. Период координатных последовательностей на выходе генератора LFSR - CKS равен периоду многомерной последовательности LFSR-CNS Т(л = г = -1

Лемма 4.3. Пусть tj s {aq~' \ а = О,I, ,<?'"'} и пусть Z(rj) — количество различных значений индекса п. О <п < Т таких, что ии,(п) =;; Тогда справедливы соотношения ! (У-"""1", если

Ле.мма 4.4. Для множества 1 (л?)} справедливы следующие оценки отклонения

£>;({"w,(")» = <?"'. Dl,({u^{n)))>q-, N <Т Полученные выше значения отклонения также являются следствием дискретизации элементов последопательностей и не могут быть улучшены для фиксированных q и t

Для исследования статистической независимости элементов последовательности {ии)(п)} в работе рассматривается последовательность векторов

б(п) = {ии\п), ,и(у)(л+*-!)), ойп<Т, для которой справедливо следующее утверждение

Лемма 4.5. Пусть к<т/х, Ае[0,1)'п^"'г' и пусть 1(И)—количество различных значений индекса п, 0 £п<Т, таких что б(п) = Л Тогда справедливы соотношения

Из соотношений (17) следует, что звездное отклонение множества {£>(«)}, 0<.п<Т

(к < т/¡), значения отклонения являются следствием дискретизации значений элементов последовательности и не могут бьгть улучшены при фиксированных q и г

Также в главе 4 проведено исследование зависимости свойств бинарного генератора ¿ГОЛ-СЖот его параметров и получены следующие практические рекомендации.

• рекомендуется использовать значения £=« и $ = *■[£/*•];

• вычислительная эффективность (в терминах количества арифметических операций) алгоритма генерирования зависит от количества ненулевых коэффициентов характеристического многочлена Л(г), путем выбора^характеристического многочлена наперед заданные ограничения на вычислительную эффективность синтезированного алгоритма могут быть удовлетворены,

• при использовании участка генерируемой псевдослучайной последовательности длины //«Тг, использование примитивных характеристических многочленов с числом ненулевых коэффициентов, превосходящим т/2 (где т порядок многочлена), является предпочтительным использованию многочленов с малым числом ненулевых коэффициентов (например, трехчленов или пятичленов) с точки зрения критерия равномерности распределения элементов рассматриваемого участка псевдослучайной последовательности,

• при использовании участка псевдослучайной последовательности длины ЛГ«7г, предпочтительным, в терминах критерия равномерности распределения элементов последовательности, является использование генераторов ¿/=57?использующих каноническую систему счисления, порожденную вторым классом Ковача (5);

• при использовании участка псевдослучайной последовательности длины Нс/г, начальное состояние генератора рекомендуется инициализировать с использованием дополнительной бинарной псевдослучайной последовательности, начальные состояния с отношением количества нулей и единиц близким к 1/2

Пятая глава работы посвящена статистическому исследованию свойств последовательности на выходе генератора LFSR■CNS на участке периода и исследованию эффективности параллельного алгоритма генерации ¿/ЗЯ-СЛ/Б

В качестве обязательных этапов исследования любого генератора многими авторами рассматриваются теоретическое исследование последовательности на выходе генератора на полном и неполном периоде, статистическое тестирование участка псевдослучайной последовательности на неполном периоде, тестирование генератора в задачах, приближенных к реальным Очевидным и принципиальным методологическим недостатком численного (статистического) исследования псевдослучайных последовательностей является отсутствие

(17)

удовлетворяет соотношению ££((й(л)}) = То есть, в случае низких размерностей

ответа на вопрос о достаточности ("полноте") множества используемых статистических или практических тестов В диссертационной работе, статистическое исследование свойств генератора LFSR-CNS проведено с использованием т н "физических тестов" (высотный корреляционный тест, тест множественного случайного блуждания) Данные тесты пройдены генератором ЬРБЯ-СЫБ

Также в работе проведено численное исследование генератора с использованием вычисления многомерных интегралов рассматриваемых в известной монографии Н М Коробова4 В этих тестах результаты, показанные генератором, превосходят результаты, полученные с использованием методов Монте-Карло, использованных в работе Коробова В результате численного исследования генератора ¿гаЛ-СЖ с использованием библиотеки Тез11/01 (наиболее полной библиотеки статистических тестов ГСЧ5), получены результаты, свидетельствующие, что характеристики синтезированного генератора ¿^Л-СШ превосходят характеристики стандартных генераторов, доступных пользователям различных платформ (см. таблицы 5.1,5 2,5 4)

В таблицах 5 1 и 5 2 приведены результаты "физических тестов" Суть данного класса тестов, является максимально приближенное к практическому использованию генератора вычисление по методу Монте-Карло значений физических величин, для которых известны точные аналитические значения Точные значения величин ф и рассмотренных в работе равны 0 5. Диапазон значений, полученный, с использованием генератора ¿F5'Л-C^'S содержит точное значение, чего нельзя сказать о стандартных генераторах, использованных при тестировании.

Таблица 5 1- Оценки величины ф для высотного корреляционного теста различных

Генератор Ф Генератор Ф

RANLUX4 0,5001±0,0001 R250 0,4989±0,0002

RANMAR 0,5000±0,0001 R89 0,4984±0,0001

MZRAN 0,5000±0,0001 LFSR-CNS 0,5000±0 0001

Таблица 5 2— Оценки величины ¿1 для теста множественного случайного блуждания

Генератор d Генератор d

RANLUX4 0,5000±0 0001 RANMAR 0,5001±0 0001

RANLUX3 0,4999±0 0001 MZRAN 0,5000±0 0001

RANLUX2 0,5000±0 0001 R250 0,4984±0 0001

RANLUX1 0,4999±0 0001 R89 0,4981±0 0001

RANLUX0 0,4991±0 0001 LFSR-CNS 0,5000±0 0001

В Таблице 5 4 представлено количество непройденных тестов из наборов статистических тестов SmallCrush, Crush, BigCrush тестов библиотеки TestUOl различными генераторами

4 Коробов, Н М Теорстнко-числовые методы в приближенном анализе [Текст] / Н М Коробов / МЦНМО, Москва — 2004 -2889

5 TestUOl A Software Library in ANSI С for Empirical Testing of Random Number Generators [Electronic resource] 11 http .//www iro umontreal ca/~lecuyer

Таблица 5 4- Результаты тестирования генератора LFSR-CNS с использованием

библиотеки TestUOl 1

Генератор SmallCrush Crush BigCrush

LCG(2",65539, 1) 11 106 нет данных

Java util Random 1 9 21

Untx-random-32 5 101 нет данных

Umx-random-64 4 57 нет данных

Una-random-128 2 13 19

CFSR(250,i03) 1 8 14

Matlab-rand нет данных 5 8

WELL! 024(a) 0 4 4

LFSR-CNS 0 4 4

Непройденные тесты - это тесты, связанные с вычислением линейной сложности генерируемых последовательностей Данные тесты не пройдены в силу особенностей базового генератора Таусворта, что является общей характеристикой всех методов генерации, обобщающих метод Таусворта. В качестве примера может быть приведен комбинированный генератор WELL1024(a), не проходящий те же тесты.

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

Показано, что вычислительная сложность алгоритма генерирования LFSR-CNS эквивалентна вычислительной сложности базового генератора Таусворта, не зависит от количества компьютеров / процессоров, используемых для генерации, и является линейной относительно порядка рекуррентного соотношения Для матричного генератора, даже в случае использования рекуррентного соотношения первого порядка, вычислительная сложность зависит квадратично от количества параллельных процессоров, используемых для вычислений.

В работе показано, что характеристики равномерного распределения на выходе генератора LFSR-CNS являются лучшими по сравнению с генераторами, основанными на параллелизации одномерных схем, и сравнимыми с характеристиками! матричных генераторов.

Таким образом, на примере обобщенного генератора Таусворта, показано, что КСС-обобщение методов синтеза одномерных ГСЧ позволяет получить генераторы,! обладающие преимуществами как "естественно"-многомерных генераторов псевдослучайных точек, так и методов, основанных на параллелизации одномерных ГСЧ !

На защиту выносятся следующие результаты: ,

1) общий метод синтеза псевдослучайных последовательностей векторов многомерного пространства, основанный на использовании канонических систем счисления в многомерных решетках; |

2) исследование свойств фундаментальных областей предложенных многомерных генераторов, синтез эффективных алгоритмов унификации,

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

4) исследование свойств координатных последовательностей на выходе обобщенного генератора Таусворта, исследование зависимости свойств генератора от его параметров и начальных условий

/ь

Основные результаты опубликованы в следующих работах:

1) Калугин, А.Н. Реализация вычисления свертки по модулю составных чисел Мерсенна [Текст] / А Н Калугин // Новые информационные технологии тезисы докладов XI Международной студенческой школы-семинара Т 1 / МГИЭМ — Москва, 2003 — С 354-355

2) Калугин, А.Н. Алгоритм безошибочного вычисления свертки в расширениях конечных полей [Текст] / А Н Калугин //Компьютерная оптика—2003 —Выпуск 25 —С 134-140

3) Kalouguine, A.N. Fast parallel algorithms for convolution in canonical number systems [Текст] / A N Kalouguine// 7-th International conference on Pattern Recognition and Image Analysis New information Technologies (PRIA'2004) Conference Proceedings (vol 1-3) Vol 1 / St Petersburg Electrotechnical University - St Petersburg, 2004 — pp 252-255

4) Chernov, V. Factorization Ambiguity in Algebraic Number Fields SchOnhage-Strassen Algorithm [Электронный ресурс] / V Chernov, A KaIouguine//Abstracts of the 4th European Congress of Mathematics — KTH, Stockholm — 2004

5) Kalouguine, A.N. 3D generalization for LSFR random point generator [Текст] / A Kalouguine, V Chernov // Proceedings of The 2-nd IASTED International Multi-Conference on Automation, Control and Information Technology (ACIT 2005), conference «Signal and Image Processing» / ACTA Press — Novosibirsk, 2005 j

6) Калуги и, Л H. Трехмерное обобщение генератора LFSR случайных точек [Текст] /АН Калугин //Компьютерная оптика —2005 —Выпуск 27 —С 131-134

7) Калугин, Л Н. Модификация многомерных псевдослучайных последовательностей с использованием пары двойственных LFSR-CNS генераторов [Текст] /А Н Калугин //Компьютерная оптика. — 2006 — Выпуск 28 — С 112-118

8) Калугин, А II. Генератор LFSR-CNS Экспериментальные исследования многомерной псевдослучайной последовательности [Текст] /А Н Калугин // Перспективные информационные технологии в научных исследования, проектировании и обучении (ПИТ-2006) Труды научно-технической конференции с международным участием, Том 2 / Самара, 2006 — С 101-106

9) Калугин, А.Н. Генератор LSFR-CNS Аналитическое исследование равномерности

еделения [Текст] / А Н Калугин //Компьютерная оптика —2007 —Выпуск 31 —С 58-

10) Kalouguine, A.N. Fractal Fundamental Domains of Canonical Number Systems Some Applications to Monte Carlo and Randomized Quasi-Monte Carlo Methods m Realistic Image Synthesis [Текст] / A N jKalouguine // Proceedings of the 17lh International Conference, Graphicon-2007 Russia, Moscow, June 22-27. 2007/МГУ, Москва —2007

Подписано » печать 16.05. 2008 Формат 60 \ В4 1/16

Б\мага офсетна* Уст печ л 1,0 Тираж 100 эю

ВВЕДЕНИЕ.

ГЛАВА 1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ.

1.1 Линейные рекуррентные последовательности над конечными полями.

1.2 Тригонометрические суммы и суммы характеров с показательными функциями.

1.3 Приведенные базисы решеток.

1.4 Канонические системы счисления.

1.5 Множества с малым отклонением, -сети.

ГЛАВА 2. МЕТОДЫ СИНТЕЗА МНОГОМЕРНЫХ ГЕНЕРАТОРОВ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ.

2.1 Обобщение одномерных схем синтеза генераторов на многомерный случай.

2.2 Методы генерации последовательности цифровых векторов.

2.3 Методы синтеза точек многомерной решетки, ассоциированных с цифровыми векторами.

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

2.5 Унификация фундаментальных областей.

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

2.5.2 Выделение гиперкуба, из покрытия многомерной решетки фундаментальными областями.

2.5.3 Эффективные алгоритмы реализации унификации.

2.5.4 Специальный частный случай, не допускающий унификации

ГЛАВА 3. АНАЛИТИЧЕСКОЕ ИССЛЕДОВАНИЕ СВОЙСТВ ОБОБЩЕННОГО ГЕНЕРАТОРА ТАУСВОРТА.

3.1 КСС-отклонение.

3.1.1 Понятие КСС-отклоиения.

3.1.2 Понятие канонических (Ч,т,к)-сетей.

3.2 Определение максимального периода генерируемой последовательности.

3.3. Исследование распределения многомерных точек на полном периоде генератора и^К-С^ (Случай 1).

3.4. Распределение многомерных точек на неполном периоде генератора и^Я-СИЗ (Случай 1).

3.5 Исследование распределения генерируемой последовательности многомерных точек (Случай 2).

ГЛАВА 4. ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКИХ СВОЙСТВ КООРДИНАТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ МНОГОМЕРНОГО ОБОБЩЕННОГО ГЕНЕРАТОРА ТАУСВОРТА. ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ ГЕНЕРАТОРА.

4.1 Исследование периода координатных последовательностей.

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

4.3 Исследование статистической независимости элементов координатных последовательностей с использованием критерия серий

4.4 Специальный случай: синтез генератора, реализуемого в негабинарной системе счисления.

4.5 Оптимизация генератора ЬР8К-С^.

ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКИХ СВОЙСТВ И ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ГЕНЕРАТОРА ЬГвК-СТЧв.

5.1 «Физические тесты» генератора.

5.1.1 Высотный корреляционный тест.

5.1.2 Тест, использующий множественное случайное блуждание.

5.2 Вычисление значений многомерных определенных интегралов по методу Монте Карло.

5.3 Статистические тесты батареи ТезШО!.

5.4 Сравнительное исследование вычислительной сложности генератора и^-С^.

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

Актуальность темы. Методы статистического моделирования, методы Монте Карло получили большое распространение и применяются в различных областях: от моделирования сложных физических явлений (распространения излучения в земной атмосфере, субъядерных процессов физики высоких энергий, неламинарного течение жидкости и разреженного газа, химической кинетики и процессов горения [1]) до теоретического анализа эффективности различных финансовых инструментов, решения задач эконометрики и предсказания значений индекса Доу-Джонса [3]. Разработаны вычислительные методы Монте Карло для решения стохастических дифференциальных уравнений , задач с граничными условиями для уравнений в частных производных [2], интегральных уравнений, вычисления значений многомерных интегралов и интегралов по контуру [4].

К методам Монте Карло можно отнести численные методы статистического моделирования, основанные на получении большого числа реализаций случайного процесса с вероятностными характеристиками, совпадающими с гипотетическими характеристиками решаемой задачи. Несмотря на применение метода (в наивной форме) в течение нескольких столетий, историю метода Монте Карло принято отсчитывать с публикаций Уламом и Метрополисом в 1944 году работы [6]. За последующие десятилетия своего существования метод был развит до состояния мощного математического аппарата, используемого для решения сложных вычислительных задач [4].

В отличие от классических методов исследования реальных физических или математических систем, центральное место среди которых занимает численное решение обыкновенных дифференциальных уравнений или уравнений в частных производных, описывающих поведение физической или математической системы, метод Монте Карло моделирует эволюции физической или математической системы непосредственно, при условии что исследуемая величина может быть рассмотрена как случайная величина в некотором вероятностном пространстве.

Метод Монте Карло состоит из следующих этапов:

Этап I. Определение области (множества) входных значений (параметров) и вероятностных характеристик входных параметров.

Этап 2. Формирование (многократное) случайной выборки входных значений из заданной области, и вычисление выходного значения (решения задачи, соответствующего сформированной выборке).

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

Пример 0.1. В качестве примера применения метода Монте Карло рассмотрим вычисление значения определенного интеграла. где 5сК\ 0<<со. Здесь и далее Я, будем обозначать 5-мерную меру Лебега. Для / е!1^), оценка значения многомерного интеграла по методу Монте Карло удовлетворяет соотношению:

Здесь {йн} -- множество узлов квадратурной формулы (множество случайных векторов равномерно распределенных в В).

Заметим, что эффективность моделирования (0.2) по методу Монте Карло определяется не только адекватностью стохастической модели физической или математической системы (этап 1), но и, в значительной степени, свойствами используемой случайной выборки (этап 2) [9]. Развитие методов Монте Карло дало толчок теории, методологии и вычислительным методам формирования случайных выборок. Применение случайных последовательностей для реализации алгоритмов на базе метода Монте Карло является классическим. В настоящее время случайные последовательности и выборки находят новые области применения: используются в вычислительной статистике, при реализации вероятностных алгоритмов, тестировании сверхбольших интегральных схем, в задачах криптографии, в компьютерных играх [9].

0.1)

0.2)

В обобщенном виде, задача формирования случайной выборки может быть сформулирована следующим образом:

Пусть задана случайная величина X с функцией распределения F{x) = Р(.\- < X). Требуется сформировать мноэ/сество чисел {.vj свойства которого имитируют (в терминах определенных критериев качества) свойства множества независимых pecuiu3aiçuii случайной величины X.

Существует множество различных подходов [7] к формированию случайной выборки: от использования таблиц случайных величин и физических датчиков случайных чисел до выполняемых на компьютере детерминированных алгоритмов генерации псевдослучайных последовательностей.

На начальных этапах развития генерации случайных выборок те, кому были необходимы случайные числа (векторы), вынуждены были [7] бросать игральные кости, либо раскладывать карты. В 1927 г (L.H.C. Tippett) была опубликована таблица, содержащая более 40000 чисел «взятых наудачу» из отчетов о переписи. В 1939 году были опубликованы таблицы, содержащие 100000 случайных чисел (M.G. Kendall), в 1955 году содержащие уже миллион чисел (RAND Corporation). Для генерации этих таблиц применялись устройства, называемые механическими (физическими) датчиками случайных чисел.

Действительно, свойства последовательностей, генерируемых физическими датчиками случайных чисел очень близки свойствам «истинно» случайных последовательностей. Физические датчики случайных чисел могут быть основаны как на микроскопических (тепловой шум, фотоэлектрический эффект, квантовые эффекты) так и на макроскопических физических процессах/эффектах (вращение колеса рулетки, бросание игральных костей, и т д).

Тем не менее, физические датчики обладают следующими недостатками, значимыми для статистического моделирования:

1) физические датчики относительно медленны;

2) нередко распределение последовательности на выходе физического датчика значительно отличается от требуемого;

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

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

Попытки синтезировать метод, лишенный перечисленных недостатков, породили методологию генерации псевдослучайных последовательностей [7], то есть детерминированных (обычно рекурсивных) алгоритмов (функций), производящих на выходе последовательность чисел или точек {л'„}, имитирующую последовательность реализаций случайной величины X.

История генераторов псевдослучайных чисел (ГСЧ) берет свое начало в 1946 году, когда Дж. Фон Нейман предложил метод средин квадратов [7].

В общем виде последовательность (л;,) на выходе генератора псевдослучайных чисел (точек) может быть представлена в виде: где —детерминированная функция, аргументами которой служат предыдущие порожденные псевдослучайные значения, значение функции интерпретируется как следующий элемент последовательности. При этом считается, что начальные элементы последовательности {х,,}, необходимые для корректного однозначного вычисления значения функции Ч' известны.

Критика генераторов псевдослучайных чисел очевидна: генерируемые последовательности по построению не являются случайными; каждое генерируемый элемент полностью определяется предыдущими элементами и параметрами генератора. Однако, в случае если априорная информация о методе генерирования последовательности чисел, или участка этой последовательности, неизвестна, но задана последовательность (или конечное множество) {.г,,} чисел или векторов многомерного пространства, можно ли, используя лишь элементы этой последовательности, определить, является она (или ее участок, т.е. конечное множество) случайной или нет?

Правомерность и способы проверки гипотезы случайности заданного множества или последовательности, выбор «меры случайности», «критериев качества» являются предметом длительной дискуссии математиков и философов [7], [9].

Приведем лишь нескольких высказываний о мере случайности заданной последовательности чисел1.

Определение» 0.1. (Лехмер Д. Г., цитируется по [7]). «Случайная последовательность является смутным понятием, олицетворяющим идею последовательности, в которой каждый член является непредсказуемым для непосвященных и значения которой проходят определенное количество проверок, традиционных у статистиков и отчасти зависящих от пользователей, которым предложена последовательность».

Определение» 0.2. (Франклин Д. Н., цитируется по [7]) «Последовательность случайна, если она обладает любыми свойствами, присущими всем бесчисленным последовательностям независимых выборок . случайных величин».

Несмотря на неполноту и неточность данных высказываний, суть их очевидна: истинно случайная последовательность должна удовлетворять всем возможным критериям качества. Дальнейший анализ этого требования и попытки его формализации привели [10] к неутешительным выводам - такого объекта как истинно случайная последовательность не существует. Какова бы ни была последовательность {*„} и способ ее генерации, всегда можно построить критерий относительного которого данная последовательность не будет достаточно случайной. Всегда можно построить определенную меру (критерий), относительно которого используемая генерируемая последовательность будет «несостоятельна» [7]. Как следствие, несмотря на то, что генераторы псевдослучайных последовательностей могут использовать произвольные детерминированные алгоритмы, для любого генератора можно утверждать, что он не может быть с одинаковой эффективностью применен для всех практических задач.

В результате попытки конструктивного разрешения этой проблемы, были выработаны (эвристические) рекомендации к «оценке качества» псевдослучайных последовательностей [84], [106], [107].

1 Следует отметить, что приведенные ниже высказывания не должны рассматриваться как корректные, а уж, тем более, математически строгие определения понятия «случайной последовательности».

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

2. Гипотеза о соответствии свойств псевдослучайной последовательности требуемым, должна быть исследована численно с применением как можно более обширного набора тестов.

3. Если возможно, генератор, планируемый для использования в для решения определенной вычислительной задачи, должен быть использован для решения аналогичной задачи, правильное решение которой заранее известно (может быть вычислено аналитически)2.

Решение о «уровне качества» псевдослучайной последовательности (обычно по сравнению с другими ГСЧ) принимается на основании результатов, полученных с использованием всех трех описанных подходов.

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

Применяемые в настоящее время критерии могут быть классифицированы [9] по следующим признакам:

1. Структурные критерии. К данной группе относятся требования к длине периода псевдослучайной последовательности, требования к геометрической структуре множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др. 2

Заметим, что данный способ анализа очень редко реализуем на практике, так как если аналогичная задача может быть решена аналитически, достаточно высоки шансы, что аналитическое решение может быть получено и для реальной задачи [41].

2. Статистические (теоретико-вероятностные) критерии. К данной группе относятся критерии согласия «эмпирического» закона распределения множества на выходе ГСЧ теоретическому (наперед заданному) закону распределения в одномерном пространстве а также согласия распределения множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др.

3. Критерии теории сложности. К данной группе критериев относятся теоретико-информационные критерии, интерпретирующие случайность последовательности, как «непредсказуемость» последующих отчетов [87].

4. Системо-технические критерии. К данным критериям относятся показатели эффективности реализации генератора на ЭВМ: длина программной реализации алгоритма генерации, время выполнения, требуемый объем памяти, кросс-платформенная переносимость [85].

Рассмотрим, какие критерии различных групп используются при оценке качества псевдослучайных последовательностей для статистического моделирования3. Наибольшее практическое значение имеют генераторы псевдослучайных последовательностей равномерно распределенных в некотором «регулярном» множестве. Для одномерных генераторов таким регулярным множеством является (см. [41]) отрезок [0.1], для многомерных генераторов — гиперкуб [0,1]Л .

1. Длина периода.

Пусть генератором псведослучайных чисел порождается последовательность {*„}, /7 = 0,1,. Величина периода Т псевдослучайной последовательности, то есть наименьшее Т е N, такое что является важным параметром, характеризующим качество генератора. Для решения практических задач с использованием генераторов различных классов, рекомендуется использовать не более чем 4т последовательных отсчетов на выходе последовательности. Отметим, что подобные рекомендации являются чисто

3 Иные критерии предъявляются, например, к псевдослучайным последовательностям, используемым в криптографии. Для последних большое значение имеют теоретико-сложностные критерии. эвристическими [65], [66], [67], [68], [69], [70]. Определенные аналитические оценки характеристик распределения множества чисел/точек на выходе генераторов различных семейств, возможно получить только для ее участков, длина которых превосходит

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

Для генерируемой псевдослучайной последовательности должны быть получены аналитические гарантии соответствия (согласия) «эмпирического» распределения генерируемых отсчетов теоретическому. Па практике, таким теоретическим распределением часто является равномерное распределение в регулярной структуре.

В качестве критериев согласия используются критерий (критерий

Пирсона), двусторонняя статистика Колмогорова-Смирнова, различные меры отклонения (экстремальное отклонения, «звездное» отклонение), статистика Андерсона-Дарлинга, Крамера-фон-Мизеса и другие.

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

3. Исследование статистической независимости элементов псевдослучайной последовательности.

Анализ статистической независимости элементов псевдослучайной последовательности является важнейшим методом теоретического анализа. Разработаны критерии качества генераторов, которые позволяют делать надежные предсказания о поведении генерированных отсчетов в реальных вычислениях (тем не менее, реальность все же может отличаться от прогноза [84]),

Наиболее распространенным методом исследования независимости элементов псевдослучайной последвоательности является исследование распределения многомерных векторов, составленных из последовательных отсчетов псевдослучайных последовательностей (так называемый критерий серий).

Пусть {*„} - последовательность равномерно распределенных в [0,1) отсчетов на выходе генератора псевдослучайных точек. Элементы данной последовательности должны представлять собой реализации последовательности независимых равномерно распределенных в единичном полуотрезке случайных величин {Хп}. Рассмотрим {хп} последовательность ¿/-мерных векторов

-Ч(,'7) = (-Ч,„ • -V мх/{п+пч). (0.3)

Если элементы последовательнсти {хп} являются статистически независимыми, последовательность (0.3) векторов {хп} должна быть равномерно распределена в <Л -мерном кубе [0,1)1'.

Таким образом, исследование равномерности распределения последовательности (0.3) может быть интерпретировано как исследование статистической независимости элементов псевдослучайной последовательности у >

Совершенно ясно, что конечность величины (I не позволяет исследовать независимость всех возможных наборов случайных элементов псевдослучайной последовательности. В частности, не г никаких гарантий, что последовательность будет лишена корреляций между удаленными отсчетами, которые могут сказаться в задачах, использующих параллельные алгоритмы основанные на разбиении одномерной последовательности на блоки. [72], [73], [74], [75], [76], [77].

Исследование равномрности полно-периодических последовательностей {.х^}, л = 0,1,.,Г-1 в отношении некоторых критериев качества в пространствах различной размерности <Л позволяют делать предположения о поведении участка одномерной последовательности в реальных задачах. Эвристические результаты в пользу такого вывода приведены, например в работах [78], [81], [66]. Теоретических результатов в данной области на данной момент не получено.

Для некоторых ГСЧ, например линейных конгруэнтных генераторов, [10], множество векторов - элементов последовательности - в пространствах различной размерности с1 порождают т.н. «решетчатую структуру» [71]. Т.е. существует такая дискретная решетка А с К'', чго векторы последовательности {х^} являются узлами этой решетки (формальное определение решетки в ЕА дано в разделе 1.3). Очевидно, что наличие подобной решетчатой структурой является недостатком метода генерирования, однако, в случае если в рамках определенной схемы генератора, решетчатая структура неизбежна, возможно сравнение качества различных генераторов с использованием дополнительных критериев, учитывающих структуру решетки Л (например, с использованием т.н. спектрального критерия, [7], [88]).

В общем случае, к исследованию равномерности распределения элементов на участках многомерных последовательностей {х//5}, применяются критерии согласия аналогичные критериям, применяемым в одномерном случае, например двусторонняя статистика Колмогорова-Смирнова или критерий %2 Пирсона. [82], [77], [65]. Двусторонняя статистика Колмогорова-Смирнова известна под названием звездного отклонения [83], [9], [77] (см. раздел 1.5).

Следует также отметить, что при выполнении гипотезы о статистической независимости элементов последовательности, {х„} равномерность распределения элементов последовательностей {х^1} является лишь одним из следствий, хотя и достаточно сильным. Если возможно определить статистику У, распределение которой известно, когда элементы последовательности {хп} являются реализациями статистически независимых равномерно распределенных случайных величин, соответствие эмпирического распределения статистики У теоретическому может быть использовано для проверки гипотезы о равномерности и статистической независимости элементов последовательности {х„}. Данный принцип положен в основу методов синтеза всех статистических тестов псевдослучайных последовательностей.

5. Вычислительная эффективность

Принимая во внимание огромные количества случайных чисел/точек, используемых в современных численных экспериментах по методу Монте-Карло, эффективность генерации псевдослучайной последовательности выходит на первый план. Именно для генераторов ГСЧ, используемых при статистическом моделировании, вычислительная эффективность имеет большое значение. Для ГСЧ, применяемых в других задача, например в криптографии, данное требование является менее значимым.

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

1. Линейный конгруэнтный генератор (linear congruent generator, впервые предложен в работе [10]). Элементы последовательности {.v„} на выходе данного генератора, удовлетворяют соотношениям

Уп =аУп-1 +b (modM), х»=Ъ> (0-4) М где в (0.4), в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов (modM).

Линейные конгруэнтные генераторы являются простейшими генераторами псевдослучайных чисел, основанными на рекуррентном соотношении первого порядка. Максимальный период линейного конгруэнтного генератора ( если Ь = 0 и а'0^0) является (М-1). Для генераторов этого типа характерна решетчатая структура распределения векторов в многомерном пространстве.

В работах [7], [79], [80] представлены параметры лучших линейных конгруэнтных генераторов в терминах спектрального теста и звездного отклонения.

2. Множественный рекурсивный генератор.

Последовательность {хп} на выходе этого генератора, удовлетворяет соотношениям

У„и = 2>Л+/ (modM), п = 1,2,. I х»=77> (0-5) м где величины k, aQ,av.,ak{, М являются параметрами генератора, в (0.5) в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов (modM), начальные значения генератора уй,ух,.ук^ предполагаются ненулевыми.

Данный генератор детально исследован в [9]. 3. Метод Фибоначчи с запаздываниями (lagged Fibonacci generator, [7], [9]). Последовательность {*„} на выходе данного генератора удовлетворяет соотношениям y„ - У„-j Oy„-k (mod Af),

0.6) где О — некоторая бинарная битовая операция, например сложение по модулю 2, величины j,ke N, М являются параметрами генератора, в (0.6) в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов (modM), начальное состояние генератора Су0, Vp—>.Ишахо,*н) предполагается ненулевым.

4. Генератор Таусворта (регистр сдвига с линейной обратной связью, linear feedback shift register generator, Tausworthe generator, [14]).

Последовательность на выходе генератора, удовлетворяет соотношениям где величины т, а0,а,,, М, я, I являются параметрами генератора, в (0.7) в качестве чисел уп берутся наименьшие неотрицательные вычеты соответствующих классов {тоАМ), начальное состояние генератора .у,,.,.>>„, предполагаются ненулевыми.

5. Мерсениовский вихрь

Данный генератор, разработанный Матсумото и Нишимурой, и описанный в [15], на настоящий момент является одним из лучших ГСЧ. Его формальное описание требует формулировки значительного числа предварительных утверждений. Данный метод представляет собой пример гибридных ГСЧ, комбинирующих различные подходы.

Особое место среди ГСЧ занимают криптографические генераторы псевдослучайных чисел, к которым предъявляются дополнительные требования качества. В частности, данные генераторы должны выдерживать различные типы криптоаналитических атак, даже если часть их начального состояния (и/или параметров) известна атакующему. т-1

У„+к =Т*а1У«+1 (modM), /7 = 1,2,.

1=0 v-I

0.7)

В частности, каждый криптографический ГСЧ должен удовлетворять теоретико-сложностному критерию «тест следующего бита», суть которого в том что если заданы к бит псевдослучайной последовательности, не должно существовать алгоритма с полиномиальной сложностью, способного определить (к +1) бит последовательности с вероятностью, превышающей 1/2. Эндрю Яо доказал [21], важные свойства данного теста криптографических ГСЧ. Кроме того, например, каждый криптографический генератор должен выдерживать тест «продолжения состояния генератора» (в случае если всё (или часть) состояния генератора известна, должно быть невозможно восстановить последовательность псевдослучайных чисел, предшествующих данному состоянию).

Следует отметить, что генераторы ГСЧ общего назначения не удовлетворяют требованиям, предъявляемым к КГСЧ.

Одним из самых известных КГСЧ, является генератор Blum-Blum-Shub, описанный в работе [20]. Последовательность, порождаемая генератором, удовлетворяет следующему рекуррентному соотношению =(*„-i )2 (modpg), где p,q достаточно большие целые простые числа, удовлетворяющие некоторым дополнительным условиям.

К числу недостатков большинства КГСЧ, включая Blum Blum Shub, следует отнести их высокую вычислительную сложность. В силу данного недостатка, КГСЧ не применяются в задачах статистического моделирования по методу Монте Карло, хотя свойства распределения чисел на выходе генератора являются «более сильными» по сравнению с большинством ГСЧ общего назначения. Далее в работе, криптографические генераторы случайных чисел рассматриваться не будут.

Описанные выше генераторы псевдослучайных последовательностей являются одномерными, однако существуют задачи (например, вычисление оценки значения многомерного определенного интеграла с использованием соотношения (0.2) ) требующие генерации последовательности псевдослучайных векторов с многомерным равномерным распределением.

Теория генерации псевдослучайных последовательностей многомерных векторов (или точек) является относительно новым направлением, и к настоящему моменту разработано лишь несколько «естественно» многомерных генераторов:

1. Матричный метод генераг(гш (Нидеррайтер, [9]). Последовательность А:-мерных векторов {и,} на выходе генератора, удовлетворяет соотношениям:

Матрица А е , простой модуль М являются параметрами генератора, начальное состояние г0 предполагается ненулевым.

2. Матричный инверсивный метод генерации.

Пусть для заданной размерности к>2, выбирается большое простое число р, и пусть К — конечное поле из д = рк элементов. Для у е ^, определим у = у~\ если уф 0, и у-0, если у-0. Далее, определим последовательность /о,?',,. элементов Г нелинейным рекуррентным соотношением первого порядка:

Если {Д,Д,.,Д} — базис в Гч над и Тг обозначает след из ^ в ^ (см. раздел 1.1), то последовательность {г7я| равномерно распределенных векторов в 1к может быть определена соотношением:

Данный метод предложен в монографии Г. Нидеррайтера [9]. 3. Матрично-рекурсивный метод.

Последовательность к-мерных векторов {«„) на выходе генератора удовлетворяет соотношениям

2„+1=г„А(тос1М), Ае^ М гп+1 =оу„ +Ь, если п>0. йп=-{Тг{/317п).Тг(Д7„))е/\ Р кгк м

0.8)

Величина М, т, матрицы А^в^*' являются параметрами генератора, начальное состояние г0 предполагается ненулевым. Данный метод впервые предложен в монографии Г. Нидеррайтера [9].

К достоинствам «естественно» многомерных методов относится заложенное конструктивно качество многомерного распределения псевдослучайных векторов в пространстве размерности к.

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

Для вычислительно эффективной реализации алгоритмов, основанных на использовании последовательности многомерных псевдослучайных векторов, применяются параллельные методы генерации псевдослучайных последовательностей векторов. Монте Карло. Действительно, многие алгоритмы Монте Карло являются «естественно» параллельными [86], что обуславливает применение параллельных генераторов псевдослучаных последовательностей многомерных векторов.

Традиционным методом параллелизации, параллельного синтеза псевдослучайной последовательности, является, например, «повышение размерности» одной или нескольких одномерных псевдослучайной последовательностей одним из следующих методов [18]:

1. Метод кругового обхода.

Пусть {.хп} — последовательность на выходе одномерного генератора псевдослучайной последовательности, к — размерность многомерного вектора, количество процессоров параллельного алгоритма. Тогда элементы последовательности псевдослучайных векторов {гп}, генерируемых параллельным алгоритмом, определяются соотношением (Х„):*Хпк+1.)

Данный принцип увеличения размерности одномерной последовательности до размерности 3 проиллюстрирован на рис. ОЛ. Одномерная последовательность как бы «наматывается» по спирали на координатные компоненты многомерной последовательности.

Рис. 0.1 - Увеличение размерности одномерной последовательности методом кругового обхода. Горизонтальные линии обозначают координаты многомерного пространства.

2. Разбиения одномерной последовательности на блоки.

Пусть {*„} — последовательность на выходе одномерного генератора псевдослучайной последовательности, к — требуемая размерность многомерного вектора, количество процессоров параллельного алгоритма, тогда элементы последовательности псевдослучайных векторов {г,,} удовлетворяют соотношению:

Здесь ¿ — параметр параллельной схемы, длина блока последовательных значений одномерной последовательности, производимых на одном процессоре. Данный метод проиллюстрирован на рисунке 0.2.

Рис. 0.2- метод увеличения размерности псевдослучайной последовательности методом разбиения последовательности на блоки. Горизонтальные линии обозначают координаты многомерного пространства.

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

Пусть к — количество процессоров параллельной схемы, требуемая размерность многомерной псевдослучайной последовательности векторов. Пусть далее {л£0)}( — различные псевдослучайные последовательности, полученные с использованием различных методов, или с использованием одного метода генерации, но инициализированные различными начальными состояниями.

Тогда элементы последовательности псевдослучайных векторов {гп} удовлетворяют соотношению:

Иллюстрация данного метода, представлена на рисунке 0.3.

Рис. 0.3 —Метод повышения размерности одномерной последовательности путем использования различных одномерных последовательной для различных процессоров параллельной схемы. Горизонтальные линии обозначают координаты многомерного пространства.

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

Однако многомерное распределение элементов псевдослучайных последовательностей векторов, полученных с использованием методов параллелизации, может иметь существенные недостатки. В качестве наглядного примера очевидно недостаточных случайных свойств многомерной последовательности приведем последовательность, полученную методом кругового обхода из последовательности Капс1и , [18]. На рис. 0.4 проиллюстрировано распределение векторов этой многомерной последовательности в единичном кубе.

Рис. 0.4 — Элементы трехмерной псевдослучайной последовательности, полученные путем кругового обхода из последовательности Randu.

Причиной возникновения подобных артефактов является статистическая зависимость между элементами одномерной последовательности на выходе базового генератора Randu псевдослучайных точек. Следует отметить, однако, что для некоторых генераторов, подобные артефакты не наблюдаются вплоть до очень высоких размерностей, например для Мерсенновского вихря (Mersenne twister, [15]) многомерное распределение удовлетворяет критериям эквираспределенности в пространствах размерности вплоть до 623.

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

1. Схема генерации должна быть работоспособна для любого количества используемых процессоров - требуемой размерности псевдослучайных векторов

2. Последовательности, генерируемые на каждом из процессоров (координатные последовательности), должны удовлетворять критериям качества, предъявляемым к одномерным псевдослучайным последовательностям.

3. Распределение элементов многомерной последовательности векторов должно быть равномерным, координатные последовательности, должны быть статистически независимы между собой.

4. Алгоритм генерации должен быть вычислительно эффективен.4

Следует отметить, что как существующие методы генерации «естественно» многомерных последовательностей пседвдослучайных векторов, так и методы параллельной генерации псевдослучайной последовательности имеют определенные достоинства и недостатки, перечисленные в Таблице 0.1.

Таблица 0.1 -Достоинства и недостатски «естественно» многомерных .методов и методов увеличения размерности одномерной последовательности.

Метод Достоинства/ недостатки «Естественно» многомерные методы Увеличение размерности (параллелнзация) одномерных последовательностей

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

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

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

Основная идея. Последовательность на выходе одномерных генераторов псевдослучайных последовательностей. используемых для численного моделирования, состоит из действительных чисел полуотрезка [0,1). Однако, принимая во внимание конечность разрядной сетки компьютера, на котором

4 На практике это требование означает, что передача данных между процессорами, участвующими в вычислениях, должна отсутствовать. Будучи инициализированным, каждый процессор должен генерировать псевдослучайную последовательность независимо. реализован алгоритм генератора, можно считать, что генераторы производят рациональные числа множества Л: где л' — длина машинного слова, точность разрядной сетки компьютера.

Заметим, что

Сагс1(К) = Г < оо;

В двоичной системе счисления каждый элемент Л решетки Л может быть представлен в виде г=О где элементы разложения аг, г = 0Л,—,л-1 образуют бинарный ¿--мерный цифровой вектор а(Л). а = (ао,аг.,а1,)е{0,1}', оге{0,1}, г = 0,1,.,5-1.

Таким образом, можно считать, что на выходе любого одномерного генератора псевдослучайных чисел порождается последовательность бинарных векторов а{х(п)) е {0,1}л размерности

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

Система счисления как объект исследования интересует математиков уже в течение очень длительного периода. Помимо естественных «натуральных» оснований, уже в XII веке (Грюивальд) математики рассматривали системы счисления с такими «экзотическими» основаниями как '-2' (т.н. негабинарные системы счисления). Д. Кнут в своей монографии [7], со ссылкой на работу Питти (РМ), указывает на возможность представления любого комплексного числа с целочисленными компонентами (т.н. целого гауссова числа) в виде конечной суммы степеней основания с коэффициентами из множества {0,1}:

2 = а + 6/ = 5>Д-1±/У , г, ={0,1}, а,Ьег,

7=0 с некоторым к = к(г), зависящим от г .

В 1975 г. Катай (I. К&а!) и Ковач (Коуасэ) в работе [16] доказали существование систем счисления вида (~В±1,{0.В2}), и представимость любого целого гауссова числа в виде конечной суммы: к г = а + Ы = ^г]{-В±1У , г, е [о.В2], а,Ь е Ъ, В е с некоторым к = , зависящим от г .

В работах [11], [12], [13], продолжающих развитие теории канонических систем счисления, Ковач вводит понятие канонических систем счисления (КСС) для Ъкхк и КАхА. Каждому элементу г е в КСС ставится в соответствие вектор цифр:

В работах [11], [12], [13] показано, что для любого к> 2, ^-ичные {(¡>.2, д е N) канонические системы счисления существуют.

Теория КСС дает возможность использовать идеи, реализованные в одномерных генераторах псевдослучайных чисел, для построения их многомерных аналогов. Используя сходство представления чисел в одномерных позиционных системах счисления и элементов многомерной решетки в канонических системах счисления, любой одномерный генератор может быть положен в основу соответствующего многомерного генератора псевдослучайной последовательности. Для этого достаточно лишь интерпретировать элементы состояние генератора как коэффициенты £ в разложения (1.31) элемента ^еГ, 0

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

Задачи диссертационной работы:

1) теоретическое обоснование возможности синтеза генераторов псевдослучайных последовательностей векторов (КСС-генераторов) с использованием теории канонических систем счисления в решетках, синтез обобщенного генератора Таусворта.

2) исследование свойств множества точек на выходе КСС-генераторов, возможности унифицирующего преобразования данного множества к виду, удобному для практического использования в задачах моделирования по методу Монте Карло;

3) аналитическое исследование многомерного распределения на выходе предложенного обобщенного генератора Таусворта (на полном и неполном периоде); исследование статистической независимости отсчетов генерируемой последовательности,

4) исследование свойств координатных последовательностей на выходе генератора, анализ влияния параметров генератора и начальных условий на его свойства;

5) численное исследование свойств последовательностей на выходе генератора на участке периода, сравнение предложенного генератора с существующими схемами.

Краткое содержание диссертации. Диссертационная работа, содержащая 159 страниц, состоит из введения, пяти глав, заключения и списка использованной литературы, составляющего 107 наименований.

Заключение

В работе предложен метод синтеза многомерных генераторов псевдослучайных точек, обобщающих базовые одномерные ГСЧ с использованием теории канонических систем счисления в решетках. Исследовано множество точек многомерной решетки Ък, порождаемых Л'СС-генераторами. Найдены условия, при которых обобщенный ЖГОгеператор может быть эффективно применен для решения практических задач моделирования по методу Монте-Карло.

Синтезирована схема генератора ЬРБК-СЫБ, обобщающего одномерный генератор Таусворта. С использованием введенного понятия Л'СС-отклонения и разработанного аппарата канонических (/,/«,к )-сетей проведено теоретическое исследование последовательности на участке, соответствующем полному и неполному периоду. Дополнительно проведено аналитическое исследование координатных последовательностей ЬРЗЯ-СМБ, зависимости характеристик генерируемого распределения от параметров и начальных условий генератора, проведено статистическое тестирование генератора ЬРЗЯ-СМЗ.

Синтезирован параллельный алгоритм генерации ХКЗД-СМ!?, проведено сравнительное исследование его интенсивности в терминах количества арифметических операций. Основные результаты диссертационной работы

1. общий метод синтеза псевдослучайных последовательностей векторов многомерного пространства, основанный на использовании канонических систем счисления в многомерных решетках;

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

3. аналитическое исследование многомерного распределения на выходе обобщенного генератора Таусворта на полном и неполном периоде, исследование статистической независимости отсчетов генерируемой многомерной последовательности;

4. исследование свойств координатных последовательностей на выходе обобщенного генератора Таусворта, исследование зависимости свойств генератора от его параметров и начальных условий.

1. Rubinstein, R.Y. Simulation and the Monte Carlo Method (second edition) Text. / R.Y. Rubinstein, and D.P. Kroese. —New York: John Wiley & Sons —2007.

2. Tezuka, Sh. Financial Applications of Monte Carlo and Quasi-Monte Carlo methods Text./ Shu Tezuka // Random and Quasi-Random Point Sets / P. Hellekalek, G. Larcher, eds. —Lecture notes in statistics, 138. — Berlin: Springer, 1998.

3. Ермаков, С. M. Метод Монте-Карло и смежные вопросы Текст. / С.М. Ермаков. — М.: Наука, 1971.

4. Соболь, И. М. Численные методы Монте-Карло Текст. / И.М. Соболь. — М.: Наука, 1973.

5. Metropolis, N. The Monte Carlo Method Text. / N. Metropolis, S. Ulam// J. Amer. statistical assoc. — 1949. — 44, № 247.— pp. 335—341.

6. Кнут, Д. Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms Текст./Д. Кнут. — 3-е изд. — M.: «Вильяме», 2007. — 832 с.

7. Neumann, J. von. Various techniques used in connection with random digits Text./ J. von Neumann // Applied Mathematics Series. — 1951. — no. 12.— pp. 36-38.

8. Neiderreiter, H. Random Number Generation and Quasi-Monte Carlo Methods Text. / H.Niederreiter. — Philadelphia, SI AM. — 1992.

9. Lehmer, D.H. Mathematical methods in large-scale computing units Text./ D.H.Lemer // Proc. 2nd Sympos. on Large-Scale Digital Calculating Machinery/ Harward University Press, Cambridge, MA— 1951. — pp. 141-146.

10. Kätai, 1. Generalized Number Systems in Euclidean Spaces Text. /1. Kätai// Mathematical and Computer Modeling. — 2003 — pp. 883-892.

11. Kovacs, A. Generalized binary number systems Text. / A. Koväcs //Annales Univ. Sei. Budapest, Sect. Comp. — 2001. — № 20. — pp. 195-206.

12. Kovacs, A. On number expansions in lattices Text. / A. Koväcs // Proc. 5th lnternation Conference on Applied Informatics / Eger, Hungary. —2001.

13. Tausworthe, R. C. Random Numbers Generated by Linear Recurrence Modulo Two Text. / R.C. Tausworthe // Mathematics of Computation. — №19. — 1965. — pp. 201-209.

14. B. Koväcs //Acta Mathematica Academiae Scientarium Hungaricae. —1981. — 37(1-3). —pp. 159-164.

15. Wolfram. S. Random sequence generation by cellular automata Text. / S. Wolfram //Adv. Appl. Math. —1986. — № 7, 123.

16. Hellekalek. P. Don't trust parallel Monte-Carlo Electronic Resource. / P. Hellekalek / http://random.mat.sbii.ac.at/

17. Hellekalek, P. The Weighted Spectral Test: Diaphony Text. / P. Hellekalek, H. Niederreiter // ACM Trans, on Model, and Comp. Simul. — 1998. — Vol 8., No. 1, —pp. 43-60.

18. Blum, L. A Simple Unpredictable Pseudo-Random Number Generator Text. / Lenore Blum, Manuel Blum, and Michael Shub//SIAM Journal on Computing. 1986. — volume 15. — pp. 364-383.

19. Yao, A. Probabilistic computations: Toward a unified measure of complexity Text. / Andrew Yao //Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS). — 1977. — pp. 222-227.

20. Mascagni, M. Serial and Parallel Random Number Generation Text. / M. Masagni // Quantum Monte Carlo in Physics and Chemistry! P. Nightingale and

21. C. Umrigar, editors. — Springer-Verlag: New York. Berlin. 1999.— pp. 277-288.

22. Лидл, P. Конечные поля Текст./ P. Лидл, Г. Нидеррайтер. — М.: Мир, 1998.

23. Golomb, S.W. Shift Register sequences Text. / S.W. Golomb. — Holden-Day, San Francisco, 1967.

24. Гантмахер, Ф.Р. Теория матриц Текст. / Ф.Р. Гантмахер. 4-е изд. - М.: Наука, Гл. ред. физ.-мат. лит., 1988. - 552 с.

25. Thuswardner, J. Elementary properties of canonical number systems in quadratic fields Text. /J. Thuswardner // Applications of Fibonacci Numbers / G.E.Bergum et al. (eds.). — Volume 7.— pp. 405-415.

26. Lehmer, D.H. A machine method for solving polynomial equations Text. /

27. D.H. Lehmer /J. ACM 2. — 1961, pp. 151-162.

28. L'Ecuyer, P. Maximally equidistributed combined Tausworthe generators Text. / P.L'Ecuyer //Mathematics of Computation. — 1996. — 65, 213 — pp. 203-213.

29. Tezuka, S. On the discrepancy of GFSR pseudorandom numbers Text. / Shu Tezuka // J. ACM. — 1987. — 34(4). — pp. 939-949.

30. Tezuka, S, Walsh-Spectral Test for GFSR Pseudrorandom Numbers Text./ S. Tezuka//Commun. ACM. — 1987. — 30(8) — pp. 731-735.

31. Koväcs, A. On Construction of Number Systems Text. / L. German, A. Koväcs //Acta Mathematica Hungarica. — 2007. — Vol. 115 (1 -2). — pp. 155-167.

32. Koväcs, В. Canonical number systems in algebraic number fields Text. / B. Koväcs // Acta Math. Acad. Sei. Hungar. — 1981. — Vol. 37. — pp. 405-407.

33. Akiyama, S. New criteria for canonical number systems Text. / S. Akiyama and

34. H. Rao //Acta Arithm. — 2004. — Vol. 111 — pp. 5-25.

35. Дэвенпорт, Дж. Компьютерная алгебра Текст. / Дж. Дэвенпорт, И. Сирэ, Э. Турнье. — М.: Мир, 1991.-352 с.

36. Касселс, Дж. Введение в геометрию чисел Текст. / Дж. Касселс.-М.: Мир, 1965.-428 с.

37. Pohst, М. Algorithmic algebraic number theory Text. / M. Pohst, H. Zassenhaus. — Cambridge.: Cambridge University Press, 1989.

38. Василенко, O.H. Теоретико-числовые алгоритмы в криптографии Текст. / О.Н. Василенко. М.: МЦНМО, 2003. - 328 с.

39. Boas, Р. van Em de. Another NP-complete partition problem and the complexity of computing short vectors in lattice Text. : Tech. Report 81-04 / P. van Em de Boas. — Dpt. of Mathematics, Univ. of Amsterdam. — Amsterdam, 1980.

40. Ajtai, M. A sieve algorithm for the shortest lattice vector problem Text. /М. Ajtai, R. Kumar, and D.Sivakumar // Proc. 33rd STOC / ACM, 2001. — pp. 601610.

41. Кейперс, Jl. Равномерное распределение последовательностей Текст.: пер. с англ. / Л. Кейперс, Г. Нидеррейтер; под ред. С.М. Ермакова. М.: Наука, Гл. ред. физ.-мат. лит., 1985 -408 с.

42. Random and Quasi-Random Point Sets Text. / Lecture notes in statistics P. Hellekalek, G. Larcher, eds. 138. — Springer, 1998.

43. Hellekalek, P. The Weighted Spectral Test: Diaphony Text. / P. Hellekalek, H. Niedderreiter // ACM Trans, on Model, and Comp. Simul. — 1998— Vol 8., No.1. —pp. 43-60.

44. Ripley, B. Stochasitc Simulation Text. / B. Ripley. — Wiley, New York. — 1987.

45. Айерлэнд, К. Классическое введение в современную теорию чисел Текст. / К. Айерлэнд, М. Роузен. — М.: Мир, 1987.-416 с.

46. Zinterhof, Р. Über einige Abschätzungen bei der Approximation von Funktionen met Gleivhverteilundsmethoden Texte. / P. Zinterhof // Sitzungsber. Österr. Akad. Wiss. Math.-Natur. — 1976. — Kl. II 185, — pp. 121-132.

47. Коробов, H.M. Теоретико-числовые методы в приближенном анализе Текст./ Н.М. Коробов. — М.:МЦНМО, 2004. 288 с.

48. Rütti, М. A Random Number Generator Test Suite for the С++ Standard, RNGTS электронный ресурс. // http://www.comp-phys.org.

49. Lemieux, C. Randomized polynomial lattice rules for multivariate integration and simulation, extended version Electronic resource. / C. Lemieux and P. L'Ecuyer // http://www.iro.umontreal.ca/~lecuyer.

50. Ferrenberg, A.M. Monte Carlo simulations: Hidden errors from "good" random number generators Text. /A.M. Ferrenberg, D.P. Landau and Y.J. Wong // Phys. Rev. Lett. — 1992. — 69, 3382.

51. Vattulainen I., Framework for testing random numbers in parallel calculations Text. /1. Vattulainen //Phys. Rev. E —1999. —59, 6, 7200.

52. Duplantier, B. Conformal invariance and intersection of random walks Text. / Duplantier, B. Kwon, K.-H // Phys. Rev. Lett. — 1988— Vol. 61. — pp.2514-2517.

53. Krug. J. Origins of scale invariance in growth processes Text. / J. Krug, // Adv. Phys. — 1997. — 46. — pp. 139-282.

54. Lewis, T. G. Generalized feedback shift register pseudorandom number algorithm Text. / T. G. Lewis and W. H. Payne // J. Assoc. Comput. Mach. — 1973. —20,— pp. 456-468.

55. Ziff, R. M. Spanning probability in 2D percolation Text. / R.M.Ziff// Phys. Rev. Lett. — 1992. —69 — pp. 2670.

56. Marsaglia, G. Toward a Universal Random Number Generator Text. / G. Marsaglia, A. Zaman and W.W. Tsang // Stat. Prob. Lett. — 1990. — 8. — pp. 35-39.

57. Marsaglia, G. Some Portable Very-Long-Period. Random Number Generators Text. / Marsaglia, G. and A. Zaman //Compt. Phys.— 1994. — 8.— pp. 117- 121.

58. LUscher, M. A portable high-quality random number generator for lattice field theory simulations Text. / M. Liischer // Computer Phys. Commun. — 1994. — 79. —pp. 100- 110.

59. Larralde, H. Number of Distinct Sites Visited by N Random Walkers / H. Larralde, P. A. Trunfio, S. Havlin, H. E. Stanley, and G. H. Weiss // Phys. Rev. A. — 1992, —45. —p.7128.

60. Eichenauer-Herrmann, J. Statistical independence of a new class of inversive congruential pseudorandom numbers Text. / J. Eichenauer-Herrmann // Math. Comp.—1993. — 60.— pp.375-384.

61. Grunvvald, V. Number systems with negative bases Text. / Vittorio Grunwald//Giornale di Matematiche di Battaglini. —1885. — 367. — pp. 203221.

62. Pawlek, Z. Nega-positional number systems Text. / Z. Pawlek and A. Wakulicz //Serie des sciences techniques. — J 959. — 7. — pp. 713-721.

63. Hellekalek, P. Inversive pseudorandom number generators: concepts, results and links Text. / P.Hellekalek //Proceedings of the 1995 Winter Simulation

64. Conference/ C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman, editors. — 1995.—pp. 255-262.

65. Leeb, H. Inversive and linear congruential pseudorandom number generators in selected empirical tests Text. / H. Leeb and S. Wegenkittl //ACM Trans. Modeling and Computer Simulaion. — 1999. — 7. — pp. 272-286.

66. L'Ecuyer, P. Close-point spatial tests for random number generators Text. / P. L'Ecuyer, J.-F. Cordeau and R. Simard //Acm. Tran. Operation Research. — 2000 — 48(2). — pp. 308-317.

67. L'Ecuyer, P. Entropy tests for random number generators / P. L'Ecuyer. A.Compagner and J.-F. Cordeau Electronic resource. // Submitted to ACM Tomacs. —1997.

68. L'Ecuyer, P. Random Number Generators and Empirical Tests Text. / P. L'Ecuyer //Lecture Notes in Statistics. — 1998. —127.—pp. 124—138.

69. MacLaren, N.M. A limit on the usable length of a pseudrandom sequence Text. / N.M. MacLaren // J. Statist. Comput, Simul. — 1992. — 42.— pp. 47-54.

70. L'Ecuyer, P. Random number generation Text. / P. L'Ecuyer // Handbook on Simulation/ Jerry Banks, editor. — New York: Wiley, 1997.

71. DeMatteis, A. Long-range correations in linear and non-linear random number generators Text. / A.DeMatteis and S. Pagnutti // Paralel Computing. — 1990. — 14,—pp. 207-210.

72. Entacher, K. Bad subsequencs of well-known linear congruential pseudrandom number generators Text./ K.Entacher / ACM Trans. Modeling and Computer Simulation. — 1998. — 8.— pp. 61 -70.

73. Entacher, K. A Collection of selected pseudorandom number generators with linear structure Text. /K. Entacher //Technical report series, ACPC. Austrian Center for Parallel Computation, 1997.

74. Eichenauer-Herrmann. J. Statistical independence of a new class of inversive congruential pseudorandom numbers Text. / J. Eichenauer-Herrmann //Math. Comp. — 1993. — 60. — pp. 375-384.

75. Niederreiter, H. On a new class of pseudorandom numbers for simulation methods Text. / H. Neiderreiter // J. Comp. Appl. Math. — 1994. — 56. — pp. 159-167.

76. Fishman, G.S. A statistical evaluation of multiplicative congruentil random number generators with modulus 23l-lText. / G.S.Fishman and L.R.Moore// J. Amer. Statist. Assoc. — 1982. — 77,—pp. 129-136.

77. Fishman, G. S. An exhaustive analysis of multiplicative congruential random number generators with modulus 2l -1 Text. / Fishman, G. S. and Moore 111, L.S. // SIAM J. Sei. And Stat. Comput. — 1986. — 7, 1. — pp. 24-45.

78. Fishman, G. S. Multiplicative congruential random number generators with modulus : an exhaustive analysis for P = 32 and a partial analysis for P = 48. Text. / Fishman, G. S. // Math. Comput. — 54, 189 (Jan 1990). — pp. 331- 344.

79. L'Ecuyer, P. Testing random number generators Text./ P. L'Ecuyer// Proc. 1992 Winter Simulation Conference (Arlington, Va., 1992) / J.J. Swain et al, editor. — IEEE Press, Piscataway, N.J., 1992,—pp. 305-313.

80. Kiefer, J. On large deviations of the empiric d.f, of vector chance variables and a law of iterated logarithm Text./J. Kiefer//Pacific J. Math.— 1961.— II.—pp. 649 660.

81. Niederreter, H. Low-discrepancy and low-dispersion sequences Text. / H. Niederreiter //J. Number theory. — 1998. — 30. — pp. 51 -70.

82. Hellekalelc, P. On the Assessment of Random and Quasi-Random Point Sets Text. / P. Hellekalelc// Random and Quasi-Random Point Sets / P. Hellekalelc, G. Larcher, eds. ■— Lecture notes in statistics, 138.— Berlin: Springer, 1998.

83. Coddington, P. Random Number Generators for Parallel Computers / P. Coddington Electornic resource.// NHSE Review, Second Issue, Northeast Parallel Architectures Center. — http://nhse.cs.rice edu/NHSEreview/RNG/

84. Beth, T. On the complexity of pseudo-random sequences Text. // Advances in Cryptology/ J.J.Quisquater and J. Vanderwalle, eds.; Eurocrypt'89. — Berlin: Springer, 1990. —pp. 533-543.

85. Leeb, H. Strong and weak laws for the spectral test and related quantities / H. Leeb and P. Hellekalek Text.// Preprint, submitted, 1998.

86. Larcher, G. A bound for the discrepancy of digital nets and its application to the analysis of certain pseudorandom number generators Text. / G, Larcher // Acta Arith. — 1998, —83. —pp. 1-15.

87. Grothe, H. Matrix generators for pseudo-random vector generation Text. / H. Grothe // Statist. Papers. — 1987. — 28. — pp. 233-238.

88. Panneton, F. Improved long-period generators based on linear recurrences modulo 2 Text. / F.Panneton and P. L'Ecuyer // ACM Transactions on Mathematical Software 2006. — 32, 1. — pp. 1- 16.

89. Chung, K.L. An estimate concerning the Kolmogoroff limit distribution Text.// K.L. Chung // Trans. Amer. Math. Soc. — 1949. — 67. — pp.36-50.

90. Marsaglia, G. Diehard, a battery of tests for random number generators Electronic resource. /G. Marsaglia // ftp://stat.fsu.edu/pub/diehard/.

91. The nist statistical test suite Electornic resource. / N1ST Computer Security Division Website, 2005.

92. Теория, применение и оценка качества генераторов псевдослучайных последовательностей Текст. / М.А. Иванов, И.В. Чугунков. М. : Кудиц-Образ, 2003. - 240 с. - (СКБ - специалистам по компьютерной безопасности. Кн.2).

93. Математические и компьютерные основы криптологии. Учебное пособие Текст. / Харин Ю. С., Берник В. И., Матвеев Г. В., Агиевич С. В. -М.: Новое издание, 2003.