Спосіб формування некорельованої послідовності рівномірно розподілених чисел

Реферат: Спосіб формування некорельованої послідовності рівномірно розподілених чисел належить до обчислювальної техніки та використовується для формування непередбачуваної рівномірно розподіленої випадкової послідовності чисел з нульовою помилкою відтворення закону розподілу дискретної випадкової величини. UA 74628 U (54) СПОСІБ ФОРМУВАННЯ НЕКОРЕЛЬОВАНОЇ ПОСЛІДОВНОСТІ РІВНОМІРНО РОЗПОДІЛЕНИХ ЧИСЕЛ UA 74628 U UA 74628 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель належить до обчислювальної техніки та може бути використана для генерації некорельованої послідовності рівномірно розподілених чисел (слів). Для створення випадкових послідовностей чисел широко використовуються генератори послідовностей максимальної довжини (генератори М-послідовностей) і генератори конгруентних послідовностей чисел [1]. Проте жоден з цих класів генераторів випадкових чисел (ГВЧ) не дає ні рівномірного розподілу породжуваної послідовності чисел, ні некорельованої послідовності. Усі ці генератори дають циклічно повторювані послідовності з різною довжиною циклу. Так, генератори М-послідовності породжують цикл довжиною t c  2 m  1 (у циклі відсутня m-розрядна комбінація нулів). Генератори конгруентних чисел, що розв'язують ітераційне рівняння: Sn  Sn  1  K  C M (1) породжують цикли різної довжини, які визначаються значеннями параметрів К, C, M і S(0). Генератор, що розв'язує рівняння (1), за простого М породжує один нуль-цикл (цикл, що складається з одного елементу) і d циклів, які не перетинаються, з t неповторюваними числами в кожному з них, при цьому dt  M  1 [2]. За фіксованих параметрів К, С, М залежно від параметра S(0), що завантажується в генератор на початку роботи і називається вектором початкового завантаження (ВПЗ), генератор породжує або нуль-цикл, або один з d циклів, а інші M-t чисел відсутні у вихідному потоці слів. Крім того, в силу взаємно-однозначного зв'язку породжувана послідовність чисел у будь-якого з цього класу генераторів корельована, що дозволяє по невеликому відрізку відновити всю послідовність і визначити параметри К, С, М. Цю властивість називають передбачуваністю послідовності. Для більшості практичних застосувань (імітаційне моделювання складних систем і процесів, оптимізація параметрів складних систем і ін.) необхідне створення (генерація) некорельованої рівномірно розподіленої послідовності чисел, а в практичних застосуваннях, пов'язаних з вирішенням криптографічних завдань, передбачуваність послідовності неприпустима. Ці обставини стимулюють процес створення нових способів і пристроїв формування випадкових непередбачуваних послідовностей чисел з поліпшеними властивостями, наприклад, з меншою (найкраще - з нульовою) помилкою відтворення закону розподілу дискретної випадкової величини. Відомий генератор рівномірно розподіленої послідовності чисел на основі генератора Мпослідовності [3], в якому зменшення помилки відтворення закону розподілу дискретної випадкової величини досягається за рахунок інверсії біт у ланцюзі зворотного зв'язку регістра зсуву генератора у випадкові моменти часу. Випадкова зміна біта в ланцюзі зворотного зв'язку еквівалентна випадковій зміні вектора початкового завантаження, у тому числі такій, яка створює m-розрядне слово з одних пулів. Запропонований спосіб дозволяє поліпшити статистичні властивості генерованої послідовності чисел, але не гарантує рівномірного розподілу слів у потоці. Найбільш близьким за сукупністю ознак є генератор рівномірно розподілених чисел на основі генератора конгруентної послідовності чисел [4], у якому за простого М породжується один нуль-цикл і d циклів, що не перетинаються, довжиною t кожен, a dt  M  1. У цьому генераторі для забезпечення рівномірного розподілу чисел на відрізку [0,М-1] проводиться об'єднання всіх циклів, що породжуються генератором, у надцикл. Для цього апріорі, наприклад, у процесі виготовлення, визначають і записують у пам'ять по одному представнику кожного з циклів. У процесі застосування генератора під час формування надциклу вибирають числа з пам'яті у випадковому порядку без повторень і пропусків і використовують їх у якості векторів початкового завантаження. Загальним недоліком зазначених генераторів є кореляція слів у циклі і, як наслідок, її передбачуваність. Разом з тим, той факт, що за простого М породжується один нуль-цикл і d циклів, що не перетинаються, довжиною t кожен, створює передумови для створення ГВЧ з поліпшеними характеристиками. Цей факт свідчить, що за фіксованих параметрів К і С генератор конгруентних чисел виконує розбиття множини з М чисел на підмножини, що не перетинаються. При цьому d підмножин містять t різних слів, а одна підмножина містить тільки одне слово - нуль-цикл. Суттю пропонованої корисної моделі є конкатенація (об'єднання) всіх циклів генератора в один надцикл, у якому кожне слово відрізка [0,М-1] відтворюється тільки один раз, при цьому в кожному з надциклів випадковим чином змінюється порядок чергування слів. Досягнутий технічний результат - формування непередбачуваної рівномірно розподіленої випадкової послідовності чисел з нульовою помилкою відтворення закону розподілу дискретної 1 UA 74628 U 5 10 15 20 25 30 35 40 45 випадкової величини. Такий технічний результат досягається за рахунок конкатенації всіх циклів графа в єдиний надцикл з М слів і зміни порядку чергування слів у кожному з надциклів. Генератор рівномірно розподілених випадкових чисел складається з генератора випадкових чисел, що реалізує рівняння (1), запам'ятовуючих пристроїв (ЗУ) першого, другого і третього, які зберігають, відповідно, представників циклів, перерахованих у випадковому порядку чисел {1, 2, 3 … d+1} і перерахованих у випадковому порядку чисел {1, 2, 3 … t}, пристрій, що слугує для перемішування в кожному з надциклів порядку слів у ЗУ другому і третьому, і керуючого пристрою. До початку застосування (наприклад, при виготовленні) генератора в перше ЗУ вносяться отримані розрахунковим шляхом представники циклів, включаючи представника нуль-циклу. У друге ЗУ вносяться розміщені у випадковому порядку числа {1, 2, 3 … d+1}, а в третє ЗУ 4 вносяться розміщені у випадковому порядку числа {1, 2, 3 … t}. З початком застосування генератора керуючий пристрій вибирає з ЗУ другого і четвертого по одному слову, утворюючи пару {di, ti}. З першого ЗУ вибирається представник циклу, що знаходиться в комірці di. Якщо цей представник не породжує нуль-цикл, то він завантажується як вектор початкового завантаження в генератор, який обчислює слово, віддалене на ti кроків від вектора початкового завантаження. Отримане слово видається на вихід пристрою, генерація першого слова завершена. Якщо число di є адресою елемента, що породжує нуль-цикл, то з першого ЗУ цей елемент видається безпосередньо на вихід генератора і пристрій переходить до генерації наступного слова. Під час генерації наступних слів процедура повторюється. У процесі формування надциклу керуючий пристрій виконує: - контроль однократного включення в породжувану на виході генератора послідовність елемента, що породжує нуль-цикл, і блокування спроб його повторного включення в надцикл; - контроль одноразового застосування кожної з пар {dі, tі} і блокування спроб введення в генератор однойменних пар в межах надциклу. Після завершення формування надциклу за командою керуючого пристрою пристрій перестановки виконує перестановку слів в ЗУ другому і третьому. Далі процес формування випадкової послідовності чисел повторюється. Використання випадкового порядку формування слів у кожному надциклі, а також однократне застосування пар {d і, tі} у надциклі гарантують рівну імовірність появи слів у послідовності на виході генератора і, відповідно, нульову помилку відтворення закону розподілу дискретної випадкової величини на відрізку [0,М-1]. Перелік джерел: 1. Иванов М.А. Теория, применение и оценка качества генераторов псевдослучайных последовательностей / М.А. Иванов, И.В. Чугунков. - М.: КУДИЦ-ОБРАЗ, 2003.-240 с. - (СКВ специалисту по компьютерной безопасности). 2. Митянкина Т.В. Рандомизация последовательности конгруэнтных чисел / Т.В. Митянкина, В.В. Швыдкий, А.И. Щерба // Вестник Инженерной академии Украины.-2008. - № 2. - С. 107-111. 3. Пат. 36108 Україна, МПК G06F 7/58, G07C 15/00. Спосіб генерації випадкових чисел та пристрій для його здійснення / Торба О.О.; заявник та патентовласник Харківський державний технічний університет радіоелектроніки - № 99116006; заявл. 02.11.1999; опубл. 16.04.2001, Бюл. № 3. 4. Пат. 41079 Україна, МПК G06F 7/58. Спосіб рандомізації послідовності конгруентних чисел / Мітянкіна Т.В.; Швидкий В.В.; Щерба А.І.; Мітянкін М.О.; заявник та патентовласник Черкаський державний технологічний університет - № u200808187; заявл. 17.06.2008; опубл. 12.05.2009, Бюл. № 9. ФОРМУЛА КОРИСНОЇ МОДЕЛІ Спосіб формування некорельованої послідовності рівномірно розподілених на відрізку 0,M  1 50 чисел Sn , шляхом розв'язування ітераційного рівняння Sn  Sn  1  K  C M генератором 55 конгруентних чисел, де K , C , M - наперед задані фіксовані параметри обчислювача, граф станів якого для простого M утворює один нуль-цикл і d циклів, що не перегинаються, з t неповторюваними елементами в кожному циклі, який відрізняється тим, що апріорно, наприклад, розрахунковим шляхом, визначаються по одному представнику кожного циклу, включаючи нуль-цикл, і запам'ятовуються в оперативній пам'яті, формуються допоміжна випадкова послідовність із d  1 чисел без повторень і пропусків на відрізку 1 d  1 і допоміжна , випадкова послідовність з t чисел без повторень і пропусків на відрізку 1 t , з яких у процесі , формування послідовності зчитується пара значень di, ti , що визначають номер комірки пам'яті 2 UA 74628 U di , яка зберігає представника циклу, а також номер елемента циклу t i , що підлягає обчисленню, причому, якщо в комірці di зберігається представник не нуль-циклу, виконується процедура формування елемента послідовності шляхом обчислення ti -гo елемента циклу, який видають 5 на вихід обчислювача, якщо в комірці di зберігається представник нуль-циклу, це слово, минаючи обчислювач, виводиться в вихідний потік відразу після його зчитування з запам'ятовуючого пристрою один раз у надциклі з M чисел, після завершення формування кожного надциклу допоміжні послідовності з d  1 і t чисел піддаються перестановці для зміни порядку чергування слів у наступному надциклі. Комп’ютерна верстка І. Мироненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3