Дослідження та порівняльний аналіз алгоритмів генерації псевдовипадкових чисел

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

Міністерство освіти та науки України

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

Кафедра технічної кібернетики

Спеціальність 7.091402 «Гнучкі комп'ютеризовані системи та робототехніка»

ДИПЛОМНА РОБОТА

Дослідження та порівняльний аналіз алгоритмів генерації псевдовипадкових чисел

Студента групи ГКС-04-д

Ільяшенко Наталії Ігорівни підпис

Керівник роботи доц., к. ф-м. н.

Китова Валентина Олексіївна

Кривий Ріг 2009



ЗАВДАННЯ

на дипломну роботу студента Ільяшенко Наталії Ігорівни

1. Тема роботи: Дослідження та порівняльний аналіз алгоритмів генерації псевдовипадкових чисел

2. Термін здачі студентом закінченої роботи 01.06.09.

3. Вхідні дані до роботи: Матеріали наукових досліджень; математичні моделі генераторів псевдовипадкових чисел та статистичних критеріїв їх оцінки

4. Зміст розрахунково-пояснювальної записки (перелік питань, що підлягають розробці): Постановка завдання, Загальний огляд засобів генерації випадкових та псевдовипадкових чисел; Теоретичне дослідження алгоритмів генерації псевдовипадкових чисел та засобів їх тестування; Середовище DELPHІ як засіб розробки гнучких комп'ютеризованих систем; Програмна реалізація та експериментальне дослідження алгоритмів генерації псевдовипадкових чисел; Економічне обґрунтування доцільності розробки програмного продукту; Охорона праці.

5. Перелік графічного матеріалу (з точними вказівками обов'язкових креслень)

5.1 Логіко-функціональна схема роботи системи;

5.2 Вікно системи в режимі демонстрації результатів роботи основних алгоритмів

5.3 Область вводу параметрів при обраному методі Фібоначчі з запізнюванням

5.4 Візуалізація роботи статистичного критерію „-квадрат”

5.5 Генерація випадкових чисел на фотонному рівні - блок-схема швейцарської експериментальної розробки

5.6 АГВЧ на основі мікросхеми підсилювача й формувача сигналів інтерфейсу RS-232

5.7 Графік: Множина пар послідовних точок

6. Консультанти з роботи, з вказівками розділів роботи, що належать до них

Розділ	Консультант	Підпис, дата
		Завдання видав	Завдання прийняв
Спеціальна частина	Старіков О.М.
Програмна частина	Мурашко А.Г.
Економічна частина	Тимко Є.В.
Охорона праці	Климович Г.Б.

Календарний план

№ п/п	Найменування етапів дипломної роботи	Термін виконання етапів роботи	Примітки
	Отримання завдання на дипломну роботу	31.10.08
	Пошук літературних джерел	21.02.09
	Теоретичне та експериментальне дослідження якості алгоритмів генерації псевдовипадкових чисел	28.03.09
	Програмна частина (постановка задачі, створення програмного забезпечення, опис алгоритму рішення задачі, проектування та опис інтерфейсу користувача, опис програми)	25.04.09
	Оформлення пояснювальної записки	14.05.09
	Оформлення графічної документації	25.05.09
	Оформлення електронних додатків до диплому	27.05.09
	Представлення дипломної роботи до захисту	01.06.09

АНОТАЦІЯ

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

Розділів 7, схем та малюнків 17, таблиць 9, бібліографічних посилань 33, загальний обсяг - 103.



АННОТАЦИЯ

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

Разделов 7, схем и рисунков 17, таблиц 9, библиографических ссылок 33, общий объем - 103.



THE SUMMARY

Research and comparative analysis of pseudorandom number generator algorithms and most widespread methods of their testing is the purpose of diploma work. The software product, which allows visual representation of testing results of algorithms implementation and doing the statistical analysis of their work, was developed during implementation of experimental researches.

Sections 7, circuits and figures 17, tables 9, bibliographic references 33, total amount - 103.



ЗМІСТ

• ВСТУП
• 1. ПОСТАНОВКА ЗАВДАННЯ
• 1.1 Найменування та галузь застосування
• 1.2 Підстава для створення
• 1.3 Характеристика розробленого програмного забезпечення
• 1.4 Мета й призначення
• 1.5 Загальні вимоги до розробки
• 1.6 Джерела розробки
• 2. ЗАГАЛЬНИЙ ОГЛЯД ЗАСОБІВ ГЕНЕРАЦІЇ ВИПАДКОИХ ТА ПСЕВДОВИПАДКОВИХ ЧИСЕЛ
• 2.1 Проблема генерації випадкових чисел в історичному аспекті
• 2.2 Апаратні генератори випадкових чисел
• 2.3 Загальні характеристики генераторів псевдовипадкових чисел
• 2.4 Випадкові числа й теорія імовірності
• 3. ТЕОРЕТИЧНЕ ДОСЛІДЖЕННЯ АЛГОРИТМІВ ГЕНЕРАЦІЇ ПСЕВДОВИПАДКОВИХ ЧИСЕЛ ТА ЗАСОБІВ ЇХ ТЕСТУВАННЯ
• 3.1 Метод середини квадрата
• 3.2. Лінійний конгруентний метод
• 3.2.1 Практична реалізація лінійного конгруентного методу в стандартних бібліотеках різних компіляторів
• 3.2.2 Генератор псевдовипадкових чисел RANDU
• 3.3 Метод Фібоначчі із запізненням
• 3.4 Алгоритм Блюма - Блюма - Шуба
• 3.5 Вихор Мерсенна
• 3.6. Статистичні критерії оцінки якості алгоритмів
• 3.6.1 Критерій «Хі-квадрат»
• 3.6.2 Короткий огляд емпіричних критеріїв
• 3.7 Тести Diehard
• 4. СЕРЕДОВИЩЕ DELPHІ ЯК ЗАСІБ РОЗРОБКИ ГНУЧКИХ КОМП'ЮТЕРИЗОВАНИХ СИСТЕМ
• 4.1 Загальні характеристики середовища Delphi
• 4.2 Високопродуктивний компілятор у машинний код
• 4.3 Delphі як об'єктно-орієнтована мова
• 4.4 Основні концепції створення додатків у середовищі Wіndows
• 4.5 Особливості написання програм у середовищі Delphі
• 4.6 Огляд палітри компонентів
• 4.7 Вікно форми
• 4.8 Вікно дерева об'єктів
• 4.9 Вікно інспектора об'єктів
• 4.10 Вікно коду програми
• 4.11. Типи змінних
• 4.11.1 Цілочисельний тип
• 4.11.2 Дійсний тип
• 4.11.3 Символьний тип
• 4.11.4 Строковий тип
• 4.11.5 Булевий тип
• 5. ПРОГРАМНА РЕАЛІЗАЦІЯ ТА ЕКСПЕРЕМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ АЛГОРИТМІВ ГЕНЕРАЦІЇ ПСЕВДОВИПАДКОВИХ ЧИСЕЛ
• 5.1 Вимоги до проектованої системи та коло задач, що вона вирішує
• 5.2 Розробка логіко-функціональної схеми
• 5.3 Опис елементів інтерфейсу користувача
• 5.4 Програмна реалізація та опис основних процедур і функцій розробленої системи
• 6 ЕКОНОМІЧНЕ ОБҐРУНТУВАННЯ ДОЦІЛЬНОСТІ РОЗРОБКИ ПРОГРАМНОГО ПРОДУКТУ
• 7. ОХОРОНА ПРАЦІ
• 7.1 Аналіз небезпечних і шкідливих факторів в обчислювальному центрі
• 7.2 Заходи щодо нормалізації шкідливих і небезпечних факторів
• 7.3 Пожежна безпека
• ВИСНОВКИ
• СПИСОК ЛІТЕРАТУРИ

ДОДАТОК А - Вихідний текст файлів системи



ВСТУП

Сучасна інформатика широко використовує випадкові й псевдовипадкові числа в самих різних додатках.

Найпоширеніші сфери застосування випадкових чисел:

- Імітаційне моделювання;

- Криптографія;

- Ігрова індустрія;

- Рішення прикладних математичних завдань.

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

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

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

При цьому від якості використовуваних генераторів випадкових або псевдовипадкових чисел прямо залежить якість одержуваних результатів. Ця обставина підкреслює відомий афоризм Роберта Р. Кавью: «Генерація випадкових чисел занадто важлива, щоб залишати її на волю випадку».



1. ПОСТАНОВКА ЗАВДАННЯ

1.1 Найменування та галузь застосування

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

1.2 Підстава для створення

Підставою для розробки є наказ № 62С-01 від 29 жовтня 2008 р. по Криворізькому інституту КУЕІТУ.

Початок робіт: 31.10.08. Закінчення робіт: 01.06.09.

1.3 Характеристика розробленого програмного забезпечення

Розроблений програмний продукт призначений для ілюстрації дослідження властивостей найбільш поширених алгоритмів генерації псевдовипадкових чисел. В розробленому програмному забезпеченні були використані наступні найбільш відомі та поширені алгоритми:

· "Середини квадрата" фон Неймана;

· Лінійний конгруентний;

· Фібоначчі з запізненням;

· Алгоритм Блюма -- Блюма -- Шуба

· Вихор Мерсенна.

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

В ході розробки програмного продукту було використана середа програмування Turbo Delphi 2006 Explorer.

До складу надбудови входять:

- Random.exe - виконавчий файл системи;

- help.hlp - довідковий файл, який містить загальні відомості про розробку.

1.4 Мета й призначення

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

1.5 Загальні вимоги до розробки

Вимоги до програмного забезпечення:

· Робота в середовищі операційних систем Windows 2000/XP;

· Простота й зрозумілість інтерфейсу.

Мінімальні вимоги до апаратного забезпечення:

· IBM-сумісний комп'ютер, не нижче Pentium IІ, RAM-128Mb, SVGA-800*600*16bit; Вільний простір на жорсткому диску не менш 2 Мб.

1.6 Джерела розробки

Джерелами розробки дипломної роботи є:

· довідкова література;

· наукова література;

· технічна література;

· програмна документація.

2. ЗАГАЛЬНИЙ ОГЛЯД ЗАСОБІВ ГЕНЕРАЦІЇ ВИПАДКОИХ ТА ПСЕВДОВИПАДКОВИХ ЧИСЕЛ

2.1 Проблема генерації випадкових чисел в історичному аспекті

Протягом багатьох років ті, кому випадкові числа були необхідні для наукової праці, змушені були тягати кулі з урни, попередньо добре перемішавши їх, або кидати гральні кості, або розкладати карти. Таблиця, що містить більше 40 000 узятих навмання випадкових цифр зі звітів про перепис, була опублікована в 1927 році Л.X.К. Типпеттом.

З тих пор були побудовані механічні генератори випадкових чисел. Перша така машина була використана в 1939 році М.Ж. Кендаллом і Б. Бабінгтон-Смітом (В. Babington-Smith) для побудови таблиці, що містить 100 000 випадкових цифр. Комп'ютер Ferranti Mark I, уперше запущений в 1951 році, мав вбудовану програму, що використовувала резисторний генератор шуму та поставляла 20 випадкових бітів на суматор. Цей метод був запропонований А.М. Тьюрингом. В 1955 році. RAND Corporation опублікувала широко використовувані таблиці, у яких утримувався мільйон випадкових цифр, отриманих за допомогою інших спеціальних пристроїв. Відомий генератор випадкових чисел ERNIE застосовувався протягом багатьох років для визначення виграшних номерів британської лотереї.

Після винаходу комп'ютерів почалися дослідження ефективного способів одержання випадкових чисел, убудованих програмно в комп'ютери. Можна було застосовувати таблиці, але користі від цього методу було мало через обмежену пам'ять комп'ютера й необхідного часу уведення, тому таблиці могли бути лише занадто короткими; крім того, було не дуже приємно укладати таблиці й користуватися ними.

Генератор ERNIE міг бути убудований у комп'ютер, як в Ferranti Mark I, але це виявилося незручно, оскільки неможливо точно відтворити обчислення навіть відразу по закінченні роботи програми; більше того, такі генератори часто давали збої, що було вкрай важко виявити.

Технологічний прогрес дозволив повернутися до використання таблиць в 90-ті роки, тому що мільярди тестованих випадкових байтів можна було розмістити на компакт-дисках. Дж. Марсалья (George Marsaglia) допоміг пожвавити табличний метод в 1995 році, підготувавши демонстраційний диск із 650 Мбайт випадкових чисел, при генеруванні яких запис шуму діодного ланцюга сполучалася з певним чином скомпонованою музикою в стилі "реп". (Він назвав це "білим і чорним шумом".)

Недосконалість перших механічних методів спочатку розбудило інтерес до одержання випадкових чисел за допомогою звичайних арифметичних операцій, закладених у комп'ютер. Джон фон Нейман (John von Neumann) першим запропонував такий підхід близько 1940 року. Його ідея полягала у тому, щоб піднести до квадрата попереднє випадкове число й виділити середні цифри. Метод середин квадратів фон Неймана фактично є порівняно бідним джерелом випадкових чисел, однак він послужив відправною точкою наступних досліджень у цій області.

2.2 Апаратні генератори випадкових чисел

Ця категорія "джерел випадковості" - сама екзотична й від "чистого" програмування досить далека. Вся справа в тому, що з ряду причин всі програмні реалізації генераторів випадкових чисел варто правильно називати винятково генераторами псевдовипадкових чисел (до слова, цей причинно-наслідковий зв'язок має строге математичне обґрунтування). Що означає - навіть неймовірно гарний програмний генератор завжди буде підпадати під визначення Гейла Гесрема (автора одного із самих потужних програмних інструментальних комплектів, призначених для тестування апаратних генераторів випадкових чисел - АГВЧ): «Ніщо не випадкове, а тільки не визначене». Для розроблювачів систем шифрування з високої кріптостійкістю це твердження є синонімом або до твердого вердикту "не годиться", або до більше м'якого формулювання "підходить із обмеженнями". Коротше кажучи, "псевдо-" - воно і є "псевдо-". І було б дивно, якби розроблювачі цього не знали й таке знання не переросло в потребу в одних із самих незвичайних периферійних пристроїв - апаратних генераторах випадкових чисел. А раз є потреба - виходить, подібні пристрої неодмінно виникнуть. І вони, природно, існують, причому розмаїття використовуваних технічних прийомів і рішень у цій області здатно дійсно вразити уяву. Найпростіші АГВЧ засновані на тих властивостях елементів електронних схем, з якими так довго й завзято боролися інженери-схемотехніки. Це властивість - власні шуми електронного приладу - завжди доставляло чимало турбот при проектуванні високочутливої електроніки. Але для творців АГВЧ "шумливий" елемент є ключовим. Будь то незграбно виготовлений резистор, фотодіод або звичайний діод - він у тому або іншому ступені придатний для створення АГВЧ (тому клас подібних АГВЧ можна сміло назвати "паразитним").

Рис.2.1 АГВЧ на основі мікросхеми підсилювача й формувача сигналів інтерфейсу RS-232

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

В окремий підклас подібних АГВЧ варто винести екзотичні розробки, засновані на тому ж принципі (використання власних шумів електронного приладу), але радикально відрізняються складністю цього приладу. Тут замість дискретного електронного компонента застосовується куди більше складне джерело природної випадковості. Наприклад, в "відокремившомуся" від лабораторій знаменитої SGI проекті Lavarnd як джерело шуму застосовується ПЗС-матриця звичайної побутової комп'ютерної відеокамери QuickCam. Поміщена в спеціальний футляр при повній відсутності світла ПЗС-матриця камери "заганяється" керуючою програмою в найгірший (як для відеокамери) режим, при якому шумові характеристики максимальні й картинка чистого, природного хаосу (для неї достатня тільки одна складова сигналу - яскравість) придатна до подальшої обробки. Нетривіальне технічне рішення дозволяє мінімізувати витрати на апаратні засоби, реалізувавши програмно весь тракт подальшого формування послідовності випадкових чисел із двомірної картини хаосу.

Рис. 2.2 "Джерело ентропії" проекту Lavarnd



Рис. 2.3 Загальний вид продукту компанії Lavarnd

Другому великому класу АГВЧ найкраще підійде назва "функціональний". Тут у якості "джерела ентропії" використаються фундаментальні функціональні властивості електронних приладів, наприклад лічильників Гейгера-Мюллера. В іншому, по великому рахунку, технічні нюанси побудови АГВЧ залишаються такими ж, як й у класі "паразитних" АГВЧ (хіба що можуть відрізнятися вимірювані величини, на підставі яких формуються випадкові числа, але в даній ситуації це несуттєво). Правда, неприємною особливістю подібних пристроїв є необхідність застосування радіоізотопних джерел - у принципі, можна обійтися й без них, за рахунок природного радіаційного тла, але генератор випадкових чисел, що видає кілька значень за пару десятків секунд, нецікавий навіть власникові ігрових закладів. А якщо врахувати, що, наприклад, у Лабораторіях Фермі подібний АГВЧ "схований" у підземний басейн ємністю 70 тис. літрів... такій екзотиці дійсно важко знайти комерційне застосування, які би не були гарні її технічні показники.

Третій клас АГВЧ найбільш екзотичний. Настільки екзотичний, що комерційні вироби, які можна до нього віднести, практично відсутні на ринку. Він представлений усього декількома експериментальними розробками академічної науки. "Фундаментальний" - ніяких інших підходящих слів для його назви знайти просто неможливо.

Найбільш яскравий представник "фундаментальних" АГВЧ - розробка групи дослідників Женевського університету "оптичний квантовий генератор випадкових чисел". Треба віддати належне академічній науці Швейцарії - незважаючи на всю "екзотику", цей АГВЧ з'єднується з комп'ютером цілком "одомашненим" й актуальним інтерфейсом USB. А от "фундаментальність", схована під коробкою скромного розміру... У цьому АГВЧ випромінюваний надто слабким імпульсом лазерного світлодіода потік фотонів направляється у двометровий сегмент звичайного одномодового оптоволокна (що забезпечує фактично незалежність потоку фотонів на протилежному "виході" такої системи від різних флуктуацій параметрів випромінювача).

Рис.2.4 Генерація випадкових чисел на фотонному рівні - блок-схема швейцарської експериментальної розробки

За "вихідним зрізом" першого сегмента оптоволокна на відстані декількох міліметрів розташовуються один до одному два оптоволоконних сегмента різної довжини, на "виході" одного з яких фотон з'являється на 60 нс пізніше. Саме ця затримка й дозволяє "виявити хаос" - вона дає можливість визначити, по якому відрізку (короткому або довгому) багатомодового оптоволокна "пробіг" фотон - а вже це є справа чистого випадку. Виявлення окремих фотонів покладено на пасивно охолоджуваний кремнієвий лавинний фотодіод (Si APD). Ще один, без сумніву, нетривіальний пристрій, у якому фундаментальні фізичні принципи, наносекундна синхронізація й найсучасніша електроніка підлеглі рішенню самого утилітарного завдання - одержанню випадкових чисел, що обновляються 100 тис. раз у секунду.

Четвертий клас АГВЧ можна умовно назвати "паразитним персональним-комп'ютерним". У його представниках використаються ті огидні нюанси "поводження" фактично стандартних компонентів звичайного сучасного ПК (у першу чергу - звукових адаптерів), з якими так старанно борються їхні розроблювачі. До цих нюансів ставляться, насамперед, теплові шуми й флуктуації в підсистемі аналогового уведення/виводу звукового адаптера. Привабливість представників такого класу, природно, полягає й у характеристиці "cost for nothing" ("безкоштовно"), і в можливості розвиненої програмної реалізації самих витончених механізмів обробки для одержання майже ідеального ГВЧ. Але й тут є свої "але" - подібні АГВЧ (одна з найрозвиненіших розробок цього класу - АГВЧ turbid Джона Денкера, доступна користувачам Unix-подібних систем на умовах Open Source) мають потребу в ретельних процедурах настроювання й калібрування.

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

АГВЧ-файли - це записані в великі файли результати роботи апаратних генераторів випадкових чисел і висококласних фахівців математичної статистики й теорії ймовірностей, і, нарешті, потужних інструментальних засобів. Коротше кажучи, це фрагменти хаосу, ретельно перевірені на хаотичність. Їх можна легально безкоштовно завантажити, наприклад, із сайту www. random.org/files/ або з персонального ресурсу Гейла Гесрема.

АГВЧ-сервери - це сервери публічного доступу, що рятують розроблювача прикладного ПЗ від необхідності використати власний АГВЧ (наприклад, на етапах тестування й налагодження). Найбільш відомий подібний ресурс - www.random.org - надає в розпорядження програмістів сервіс АГВЧ за допомогою HTTP-протоколу або як вилучений CORBA-компонент, а також цілий букет готових фрагментів клієнтських програм у вихідних текстах (від Perl до C#).

2.3 Загальні характеристики генераторів псевдовипадкових чисел

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

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

У більшості завдань прикладної математики, розв'язуваних стохастичними методами, винятково важливим є досить специфічна властивість "рівномірності розподілу" випадкових чисел, що генерують ГПВЧ. Специфічне тому, що воно радикально відрізняється від поняття, описуваного тим же терміном у математичній статистиці. Щоб не було подібної плутанини, термін "рівномірність розподілу" часто заміняють на "гарну розподіленість" і підкреслюють, що він ставиться саме до послідовності чисел ("добре розподілена послідовність" або "well distributed sequence"). Як й у випадках з АГВЧ, коли хоча й неявно, але малося на увазі, що за апаратними засобами ГВЧ стоїть потужна й складна програмна підтримка, так й в обчислювальних застосуваннях ГПВЧ навіть над таким зробленим генератором, як Mersenne Twister (Вихор Мерсенна), для одержання високих показників треба "надбудовувати" програмний прошарок, що формує з послідовності випадкових чисел добре розподілену послідовність.

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

Будь-який ГПВЧ із обмеженими ресурсами рано або пізно зациклюється -- починає повторювати ту саму послідовність чисел. Довжина циклів ГПВЧ залежить від самого генератора й у середньому становить близько 2^n/2, де n -- розмір внутрішнього стану в бітах, хоча лінійні конгруентні й LFSR-генератори мають максимальні цикли порядку 2ⁿ. Якщо ГПВЧ може сходитися до занадто коротких циклів, такий ГПВЧ стає передбачуваним й є непридатним.

Більшість простих арифметичних генераторів хоча й мають велику швидкість, але страждають від багатьох серйозних недоліків:

· Занадто короткий період.

· Послідовні значення не є незалежними.

· Деякі біти «менш випадкові», чим інші.

· Нерівномірний одномірний розподіл.

· Зворотність.

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

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

Хоча багато які криптостійкі ГПВБ або потокові шифри пропонують набагато більше «випадкові» числа, такі генератори набагато повільніше звичайних арифметичних і можуть бути непридатні у всякого роду дослідженнях, що вимагають, щоб процесор був вільний для більше корисних обчислень.

У військових цілях й у польових умовах застосовуються тільки засекречені синхронні криптостойкі ГПВЧ (потокові шифри), блокові шифри не використаються. Прикладами відомих криптостойких ГПВЧ є RC4, ISAAC, SEAL, Snow, зовсім повільний теоретичний алгоритм Блюма, Блюма й Шуба, а так само лічильники із криптографічними кеш-функціями або криптостійкими блоковими шифрами замість функції виводу.

2.4 Випадкові числа й теорія імовірності

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

Приклади.

Випробування - кидання монети, випадкова подія - випадання герба.

Випробування - участь у грі “Російське лото”, випадкове подія - виграш.

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

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

Випробування - спостереження за погодою протягом дня, випадкова подія - протягом дня був дощ.

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

Нехай деяке випробування зроблене раз й у результаті цього пов'язане з ним випадкова подія (позначимо його через А) відбулася раз. Тоді відносною частотою випадкової події А, назвемо відношення к. Іншими словами .

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

Стійкість відносної частоти була виявлена й багаторазово підтверджена експериментально натуралістами в 17-19 століттях. Найбільш вражаючим є результат К. Пирсона, що кидав монету 12000 разів, потім здійснив ще одну серію кидань - 24000 разів. У цих серіях він підраховував кількість випадань герба й одержав значення відносної частоти для нього 0,5016 й 0,5005, що відрізняються друг від друга на 0,0011.

Для випадкових подій, що мають властивість стійкості, відносну частоту настання події природно вважати ступенем можливості настання випадкової події.

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

Спочатку визначимо ймовірність регулярної випадкової події як число, біля якого коливається відносна частота в довгих серіях випробувань. Потім уведемо поняття рівноможливості, рівноймовірності двох подій. Зміст цього поняття ясний інтуїтивно, ціль введення - ми хочемо визначити математично поняття ймовірності зводячи його до більше простого не обумовленого поняття рівноможливості. Наявність рівноймовірності деяких подій що є результатами деякого випробування встановлюється з “загальних міркувань”, не доводиться математично й не може бути доведено, не має потреби в доказі як первинне. Наприклад, при киданні гральної кістки випадання 1, 2, … , 6 очків уважають подіями рівноймовірності (або “майже” рівноймовірності) виходячи з передбачуваної фізичної однорідності матеріалу кості й геометричної правильності, тобто вважаючи кістку ідеальним кубом. Якщо в результаті випробування можливе настання рівноможливих подій, ніякі дві з яких не можуть наступити одночасно, то ймовірність кожного із цих подій визначається як , а самі події називаються елементарними подіями або елементарними результату.

Якщо, подія А ініціюється одним з елементарних результатів, а самих результатів по колишньому , то ймовірність події А позначувана як , визначається як відношення к. Інакше: .

Це і є формула класичної ймовірності, які ми будемо надалі використати в наших дослідженнях.

Зародження теорії ймовірностей і формування перших понять цієї галузі математики відбулося в середині 17 століття, коли Паскаль, Ферма, Бернуллі спробували здійснити аналіз завдань, пов'язаних з азартними іграми новими методами. Незабаром стало ясно, що виникаюча теорія знайде широке коло застосування для рішення багатьох завдань виникаючих у різних сферах діяльності людини.



3. ТЕОРЕТИЧНЕ ДОСЛІДЖЕННЯ АЛГОРИТМІВ ГЕНЕРАЦІЇ ПСЕВДОВИПАДКОВИХ ЧИСЕЛ ТА ЗАСОБІВ ЇХ ТЕСТУВАННЯ

3.1 Метод середини квадрата

Першим алгоритмічний метод одержання рівномірно розподілених псевдовипадкових чисел запропонував Джон фон Нейман (один з основоположників кібернетики). Метод одержав назву "метод середини квадрата".

Суть методу: попереднє випадкове число зводиться у квадрат, а потім з результату витягаються середні цифри.

Наприклад:

(3.1)

Як видно метод середини квадрата досить добре повинен "перемішувати" попереднє число. Однак він має недоліки:

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

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

Властивість "зациклюватися" властиво всім послідовностям, побудованих по рекурентній формулі x_i+1=f(x_i). Повторюваний цикл називається періодом. Довжина періоду в різних послідовностей різна. Чим більше, тим краще.

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

Деякі вчені експериментували з методом середин квадратів на початку 50-х років. Працюючи із чотиризначними числами замість восьмизначних, Дж. Е. Форсайт випробував 16 різних початкових значень і виявив, що 12 з них приводять до циклічних послідовностей, що закінчуються циклом 6100. 2100, 4100, 8100, 6100....., у той час як два з них приводять до послідовностей, що вироджується в нульові.

Більш інтенсивні дослідження, головним чином у двійковій системі числення, провів Н. К. Метрополис. Він показав, що якщо використати 20-розрядне число, то послідовність випадкових чисел, отримана методом середин квадратів, вироджується в 13 різних циклів, причому довжина найбільшого періоду дорівнює 142.

3.2. Лінійний конгруентний метод

У цей час найбільш популярними генераторами випадкових чисел є генератори, у яких використається схема, запропонована Д. Г. Лехмером в 1949 році - лінійний конгруентний метод.

Виберемо чотири "чарівних числа":

- m, модуль; 0 < m;

- а, множник; 0 < a < m;

- с, приріст; 0 < з < m;

- X₀, початкове значення; 0 < X₀ < m.

Потім одержимо бажану послідовність випадкових чисел (Х_n), маючи на увазі

X_n+1 = (а* X_n+ с) mod m, n > 0. (3.2)



Ця послідовність називається лінійною конгруентною послідовністю. Одержання залишків по модулю m почасти нагадує зумовленість, коли кулька попадає в осередок колеса рулетки. Наприклад, для m = 10 й X₀ = а = з = 7 одержимо послідовність 7,6,9,0,7,6,9,0,.... (3.3)

Як показує цей приклад, така послідовність не може бути "випадкової" при деяких наборах чисел m, а, з і Х₀. У прикладі ілюструється той факт, що конгруентна послідовність завжди утворить петлі, тобто обов'язково існує цикл, що повторюється нескінченне число раз. Ця властивість є загальною для всіх послідовностей виду Х_n+1 = f(Х_n), де f перетворить кінцеву множину саме в себе.

Цикли, що повторюються, називаються періодами; довжина періоду послідовності (3.3) дорівнює 4. Безумовно, послідовності, які ми будемо використати, мають відносно довгий період.

Заслуговує на увагу випадок, коли с = 0, тому що числа, що генеруються, будуть мати менший період, чим при с ? 0. Ми переконаємося надалі, що обмеження с = 0 зменшує довжину періоду послідовності, хоча при цьому усе ще можливо зробити період досить довгим. В оригінальному методі, запропонованому Д. Г. Лехмером, с вибиралося рівним нулю, хоча він і допускав випадок, коли с ? 0, як один з можливих. Той факт, що умова с ? 0 може приводити до появи більше довгих періодів, був установлений В. Е. Томсоном (W. Е. Thomson) і незалежно від нього А. Ротенбергом (А. Rotenberg). Багато авторів називають лінійну конгруентну послідовність при с = 0 мультиплікативним конгруентним методом, а при с ? 0 - змішаним конгруентним методом. Для спрощення формул уводимо константу: b = а-1.

Можна відразу відкинути випадок, коли а = 1, при якому послідовність Х_n може бути представлена у вигляді Х_n = (Х₀ + с) mod m і поводиться явно не як випадкова послідовність. Випадок, коли а = 0 навіть гірше. Отже, для практичних цілей припускаємо, що

а>2, b>1. (3.4)

Зараз можна узагальнити формулу (3.2)

(3.5)

де (n + k)-й член виражається безпосередньо через n-й.

Випадок, коли n = 0, у цьому рівнянні також вартий уваги. З (3.5) можна зробити висновок, що підпослідовність, що містить кожний k-й член послідовності X_n, є також лінійною конгруентною послідовністю, множник якої дорівнює

а^k mod m і приріст дорівнює ((а^k - l)c/b) mod m. Важливим наслідком з (3.5) є те, що загальна послідовність, визначена за допомогою а, с і Х₀, може бути дуже просто виражена в термінах спеціального випадку, коли с = 1 і Х₀= 0. Нехай:

Y₀ = 0, Y_n+1= (aY_n + 1) mod m (3.6)

Відповідно до (2.19) одержимо Y_k = (а^k - 1)/b (по модулю m). Виходить, послідовність, наведена в (2.18), буде мати вигляд

X_n = (AY_n + Х₀) mod m, (3.7)

де A = (Х₀b + с) mod m

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

Лінійний конгруентний метод застосовується в простих випадках і не має криптографічну стійкість. Входить у стандартні бібліотеки різних компіляторів.

При практичній реалізації лінійного конгруентного методу вигідно вибирати m = 2^e, де e -- число біт у машинному слові, оскільки це дозволяє позбутися від відносно повільної операції приведення по модулі. Машинне слово - машиннозалежна й платформозалежна величина, вимірювана в бітах або байтах, рівна розрядності регістрів процесора й/або розрядності шини даних.

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

Таблиця 3.1

Параметри лінійних конгруентних генераторів

Компілятор	m	a	c
Numerical Recipes	232	1664525	1013904223
Borland C/C+ +	232	22695477	1
GNU Compiler Collection	232	69069	5
ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C+ +	232	1103515245	12345
Borland Delphi, Virtual Pascal	232	134775813	1
Microsoft Visual/Quick C/ C+ +	232	214013	2531011
Apple CarbonLib	231 - 1	16807	0

3.2.2 Генератор псевдовипадкових чисел RANDU

RANDU -- сумно відомий лінійний конгруентний генератор псевдовипадкових чисел, що ввійшов у вживання в 1960-х. Він визначається рекуррентным співвідношенням:

(3.8)

де V₀ - непарне.

Псевдовипадкові числа обчислюються в такий спосіб:

(3.9)

Популярна думка, що даний алгоритм - один з найменш продуманих генераторів псевдовипадкових чисел серед коли-небудь, запропонованих. Так, він не проходить спектральний тест при кількості вимірів, що перевищує 2.

Підставою для вибору параметрів генератора послужило те, що в рамках цілочисельної 32-бітної машинної арифметики операції по модулі 2³¹, зокрема, множення довільного числа на 65539 = 2¹⁶ + 3, виконуються ефективно. У той же час, такий вибір володіє й принциповим недоліком. Розглянемо наступне вираження (будемо думати, що всі операції виконуються по модулі 2³¹).

(3.10)

звідки, розкривши квадратичний співмножник, одержуємо:

(3.11)

що, у свою чергу, показує наявність лінійної залежності (а отже, і повної кореляції) між трьома сусідніми елементами послідовності:

(3.12)

3.3 Метод Фібоначчі із запізненням

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

У зв'язку із цим лінійний конгруентний алгоритм поступово втратив свою популярність і його місце зайняло сімейство алгоритмів Фібоначчі, які можуть бути рекомендовані для використання в алгоритмах, критичних до якості випадкових чисел. В англомовній літературі датчики Фібоначчі такого типу називають звичайно «Subtract-with-borrow Generators» (SWBG).

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

Один із широко розповсюджених датчиків Фібоначчі заснований на наступній ітеративній формулі:

(3.8)

де Xk -- речовинні числа з діапазону [0,1), a,b -- цілі позитивні числа, називані лагами. Для роботи датчику Фібоначчі потрібно знати max{a,b} попередніх генерованих випадкових чисел. При програмній реалізації для зберігання генерованих випадкових чисел використається кінцева циклічна черга на базі масиву. Для старту датчику Фібоначчі потрібно max{a,b} випадкових чисел, які можуть бути генеровані простим конгруентним датчиком.

Лаги a й b -- «магічні» й їх не слід вибирати довільно. Рекомендуються вибирати наступні значення лагів: (a,b)=(55,24), (17,5) або (97,33). Якість одержуваних випадкових чисел залежить від значення константи a. Чим воно більше, тим вище розмірність простору, у якому зберігається рівномірність випадкових векторів, утворених з отриманих випадкових чисел. У той же час, зі збільшенням величини константи a збільшується об'єм використовуваної алгоритмом пам'яті.

Значення (a,b) = (17,5) можна рекомендувати для простих додатків, що не використовують вектори високої розмірності з випадковими компонентами. Значення (a,b) = (55,24) дозволяють одержувати числа, задовільні для більшості алгоритмів, вимогливих до якості випадкових чисел. Значення (a,b) = (97,33) дозволяють одержувати дуже якісні випадкові числа й використаються в алгоритмах, що працюють із випадковими векторами високої розмірності. Описаний датчик Фібоначчі випадкових чисел (з лагами 20 й 5) використається в широко відомій системі Matlab.

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

(3.9),

де е -- число бітів у мантисі дійсного числа.

3.4 Алгоритм Блюма-Блюма-Шуба

Цей генератор псевдовипадкових чисел був запропонований в 1986 році Ленор Блюм, Мануелем Блюмом і Майклом Шубом.

Математичне формулювання алгоритму виглядає в такий спосіб:

(3.10)

де M = p*q є добутком двох більших простих p й q. На кожному кроці алгоритму вихідні дані виходять із x_n шляхом узяття або біта парності, або одного або більше найменш значимий біт x_n.

Два простих числа, p й q, повинні бути обоє порівнянні з 3 по модулю 4 (це гарантує, що кожне квадратичне відрахування має один квадратний корінь, що також є квадратичним відрахуванням) і найбільший загальний дільник НЗД повинен бути малий (це збільшує довжину циклу).

(3.11)

Цікавою особливістю цього алгоритму є те, що для одержання x_n необов'язково обчислювати всі n-1 попередніх чисел, якщо відомо початковий стан генератора x₀ і числа p й q, n-не значення може бути обчислене «прямо» використовуючи формулу:

(3.12)

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

3.5 Вихор Мерсенна

Із сучасних ГПВЧ широке поширення одержав вихор Мерсенна, запропонований в 1997 році Мацумото й Нишимурой. Їхня робота ґрунтується на властивостях простих чисел Мерсенна (звідси назва) і забезпечує швидку генерацію високоякісних псевдовипадкових чисел.

Перевагами цього методу є колосальний період (219937-1), рівномірний розподіл в 623 вимірах (лінійний конгруентний метод дає більш-менш рівномірний розподіл від сили в 5 вимірах), швидка генерація випадкових чисел (в 2-3 рази швидше, ніж стандартні ГПВЧ, що використають лінійний конгруентний метод). Однак існують складні алгоритми, що розпізнають послідовність, породжувану за допомогою вихрячи Мерсенна як невипадкову. Це робить вихор Мерсенна невідповідним для використання в криптографії.

Вихор Мерсенна є вітковим регістром зрушення з узагальненою віддачею (twisted generalised feedback shift register, TGFSR). «Вихор» - це перетворення, що забезпечує рівномірний розподіл псевдовипадкових чисел в 623 вимірах. Тому кореляція між послідовними значеннями у вихідній послідовності алгоритму „Вихор Мерсенна” дуже мала.

Існують ефективні реалізації алгоритму „Вихор Мерсенна”, що перевершують по швидкості багато стандартні ГПВЧ (зокрема, в 2-3 рази швидше лінійних конгруентних генераторів). Вихор Мерсенна реалізований у бібліотеці gLib і стандартних бібліотеках для PHP, Python і Рубі.

Генеровані алгоритмом „Вихор Мерсенна” псевдовипадкові числа успішно проходять тести DIEHARD, що говорить про їх гарні статистичні властивості.

3.6. Статистичні критерії оцінки якості алгоритмів

Наша основна мета - одержати послідовність, що поводиться так, начебто вона є випадковою. Вище розповідалося, як зробити період послідовності настільки довгим, що при практичних застосуваннях він ніколи не буде повторюватися. Це важливий критерій, але він не дає гарантії, що послідовність буде використатися в додатках. Як вирішити, чи досить випадковою буде послідовність?

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

Теоретична статистика надає деякі кількісні міри випадковості. Існує буквально нескінченне число критеріїв, які можна використати для перевірки того, чи буде послідовність випадковою. Обговоримо критерії, на наш погляд, найбільш корисні, найбільш повчальні й найбільш пристосовані до обчислень на комп'ютерах.

Якщо критерії 1, 2, ..., Т_п підтверджують, що послідовність поводиться випадковим образом, це ще не означає, загалом кажучи, що перевірка за допомогою Т_п+1 -го критерію буде успішною. Однак кожна успішна перевірка дає усе більше й більше впевненості у випадковості послідовності. Звичайно до послідовності застосовується біля напівдюжини статистичних критеріїв, і якщо вона задовольняє цим критеріям, то послідовність уважається випадковою (це презумпція невинності до доказу провини).

Кожну послідовність, що буде широко використатися, необхідно ретельно перевірити. Розрізняються два види критеріїв: емпіричні критерії, при використанні яких комп'ютер маніпулює групами чисел послідовності й обчислює певні статистики, і теоретичні критерії, для яких характеристики послідовності визначаються за допомогою теоретико-числових методів, заснованих на рекуррентних правилах, які використовуються для утворення послідовності.

3.6.1 Критерій «Хі-квадрат»

Критерій "хі-квадрат" (²-критерій), можливо найвідоміший із всіх статистичних критеріїв. Він є основним методом, що використовується у сполученні з іншими критеріями. Перш ніж розглядав ідею в цілому, проаналізуємо приватний приклад застосування ²-критерію до кидання гральної кістки. Використаємо дві "правильні" гральні кістки (кожна з яких незалежно допускає випадання значень 1, 2, 3, 4, 5 або 6 з рівною вірогідністю). У наступній таблиці дана ймовірність одержання певної суми s при одному киданні гральних кісток.

Значення s = 2 3 4 5 6 7 8 9 10 11 12

Ймовірність =

Наприклад, величина 4 може бути отримана трьома способами: 1+3, 2+2, 3+1; це займає з 36 можливих результатів.

Якщо кидати гральну кістку n раз, то в середньому ми одержимо величину s приблизно np_s раз. Наприклад, при 144 киданнях величина 4 випадає близько 12 разів. У наступній таблиці показано, які результати в дійсності отримані при 144 киданнях гральних костей.

Величина s = 2 3 4 5 6 7 8 9 10 11 12

Спостережуване число, = 2 4 10 12 22 29 21 15 14 9 6

Очікуване число, = 4 8 12 16 20 24 20 16 12 8 4

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

(3.13)

Припустимо, що кожне спостереження може належати однієї з k категорій. Проводимо n незалежних спостережень. Це означає, що результат одного спостереження абсолютно не впливає на результат інших спостережень. Нехай -- імовірність того, що каждое спостереження ставиться до категорії s, і нехай -- число спостережень, які дійсно належать до категорії s. Утворимо статистику

(3.14)

Підносячи до квадрата

в (3.15)

і з огляду на той факт, що

(3.15)

одержуємо формулу

(3.16)

яка часто спрощує обчислення V.

Повернемося до питання “Чому дорівнює прийнятне значення V?”. Його можна визначити за допомогою таких таблиць, як таблиця 3.2, що дає значення “ - розподілу з v ступенями волі” для різних значень v. Використаємо рядок таблиці з

v= , тому що число “ступенів волі” дорівнює , що на одиницю менше, ніж число категорій. (Інтуїтивно це означає, що , ,…, не є повністю незалежними, тому що формула (3.15) показує, що може бути обчислено, якщо

,…, відомі. Тому потрібно вважати, що число ступенів волі дорівнює . Ці аргументи не строгі, але вони підтверджуються теоретично.)

Якщо в таблиці вибрати число x, що розашоване на v-й рядку й у стовпці p, то “імовірність того, що значення V в (3.16) буде менше або дорівнює x, приблизно дорівнює p, якщо n досить велико”. Наприклад, 95-процентне значення в рядку 10 дорівнює 18.31; значення, такі, що , будуть з'являтися приблизно в 5% випадків.



Таблица 3.2

Процентні точки 2-розподілення

	p = 1%	p = 5%	p = 25%	p = 50%	p = 75%	p = 95%	p = 99%
v = 1	0.00016	0.00393	0.1015	0.4549	1.323	3.841	6.695
v =2	0.02010	0.1026	0.5754	1.386	2.773	5.991	9.210
v = 3	0.1148	0.3518	1.213	2.386	4.108	7.815	11.34
v = 4	0.2971	0.7107	1.923	3.357	5.385	9.488	13.28
v = 5	0.5543	1.1455	2.765	4.351	6.626	11.07	15.09
v = 6	0.8721	1.635	3.455	5.348	7.841	12.59	16.81
v = 7	1.239	2.167	4.255	6.346	9.037	14.07	18.48
v = 8	1.646	2.733	5.071	7.344	10.22	15.51	20.09
v = 9	2.088	3.325	5.899	8.343	11.39	16.92	21.67
v = 10	2.558	3.940	6.737	9.342	12.55	18.31	23.21
v = 11	3.053	4.573	7.384	10.34	13.70	19.68	24.72
v = 12	3.571	5.226	8.438	11.34	14.85	21.03	26.22
v = 15	5.229	7.261	11.04	14.34	18.25	25.00	30.58
v = 20	8.260	10.85	15.45	19.34	23.83	31.41	37.57
v = 30	14.95	18.49	24.48	29.34	34.80	43.77	50.89
v = 50	29.71	34.76	42.94	49.33	36.33	67.50	76.15

Тепер можна остаточно описати ²- критерій у такий спосіб. Підраховуємо число спостережень, що ставляться до кожної з k категорій, і величину V, наведену у формулах (3.14) і (3.16). Потім V порівнюємо із числами з таблиці 3.2 при . Якщо V менше 1% точки або більше 99% точки, відкидаємо ці числа як недостатньо випадкові. Якщо V лежить між 1% й 5% точками або між 95% й 99% крапками, то ці числа “підозрілі”; якщо (інтерполюючи таблицю) V лежить між 5% та 10% точками або 90% та 95% точками, числа можна вважати “майже підозрілими”. Перевірка за ²-критерієм часто проводиться три рази (і більше) з різними даними. Якщо принаймні два із трьох результатів виявляються підозрілими, то число розглядаються як недостатньо випадкові.