тегорію, як Ys. Сформуємо статистику
(3.4)
Для оцінки отриманого результату використовуються таблиці розподілу. У рядках боковика (лівого стовпця) цих таблиць зазначено число ступенів свободи, а в графах - імовірності, р. Сенс таблиць в наступному: якщо в деякій рядку таблиці в стовпці знаходиться число х, то це означає, що значення V, що визначається за вищенаведеною формулою при даному V, буде більше х з імовірністю p.
Наприклад, для p=5% і v=10 таблиця дає значення х=18.31; це означає що V> 18.31 тільки в 5% всіх випадків.
Для аналізу отриманого результату використовуються різні підходи. В [43] пропонується наступний. Якщо V менше значення, відповідного р=99%, або більше значення, відповідного р=1%, то результати бракуються, як недостатньо випадкові. Якщо р лежить між 99 і 95% або між 5 і 1%, то результати вважаються «підозрілими», при значеннях, укладених між 95 і 90% або 10 і 5%, результати «злегка підозрілі»; в інших випадках результати вважаються випадковими.
Однак при такому підході буде забракована і по-справжньому випадкова послідовність, для якої ймовірність буде прагнути до 100%. Крім того, нижня межа проходження тестів взята невиправдано малою. Тому логічніше оцінювати результати наступним чином. Залежно від вимоги до генератора вибирається нижня межа Рd. Результати, для яких виконується p
б) Перевірка частот. Тест перевіряє рівномірність появи символів у досліджуваній послідовності. Підраховується, скільки разів зустрічається кожен символ - Ns (s =), після чого застосовується критерій з числом категорій, рівним 256, і ймовірностями 1/256 в кожній категорії
(3.5)
де m - число аналізованих байтів. Отримані результати аналізуються за допомогою таблиці розподілу з числом ступенів свободи, рівним 255. Має сенс провести і перевірку частот появи напівбайтів. Для цього підраховується, скільки разів зустрічається кожен напівбайт - Ns (s =), після чого застосовується критерій з числом категорій, рівним 16, і ймовірностями 1/16 у кожній категорії
(3.6)
де m - число аналізованих байтів. Отримані результати аналізуються за допомогою таблиці, розподілу з числом ступенів свободи, рівним 15.
в) Аналіз перестановок. Тест перевіряє рівномірність розподілу чисел у вихідній послідовності. Розділимо вихідну послідовність на n груп по t елементів. У кожній групі можливо t! варіантів відносного розташування чисел. Підраховується, скільки разів зустрічається кожне конкретне відносне розташування - Ns, після чого застосовується критерій з числом категорій, рівним t!, І ймовірностями 1 / t! у кожній категорії.
(3.7)
де m - число аналізованих байтів. Отримані результати аналізуються за допомогою таблиці розподілу з числом ступенів свободи, рівним t!- 1.
г) Перевірка сегментів. Даний тест перевіряє рівномірність розподілу символів у вихідній послідовності. Конкретне значення байта [0 .. 255] може належати різним сегментам, [0 .. 127] і [128 .. 255] наприклад. Аналізуються наступні один за одним пари чисел, і визначається приналежність кожного числа до певного сегмента.
Нехай є два сегменти [0 .. 127] і [128 .. 255]. Кожна пара розподіляється за категоріями: - обидва байта в парі належать першому сегменту; - один байт належить першому сегменту, а інш...
