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

Реферат: Спосіб формування послідовності випадкових чисел використовує регістр зсуву зі зворотними зв'язками. Крім цього, апріорно для заданого порядку генераторного полінома визначаються і заносяться в постійну пам'ять генератора генераторні поліноми, які породжують цикли, що підлягають конкатенації, значення довжин всіх циклів для кожного з генераторних поліномів, представників кожного із циклів і загальне число циклів, що породжуються кожним генераторним поліномом; у процесі формування послідовності в регістр зсуву зі зворотними зв'язками по черзі завантажуються генераторний поліном, що визначає структуру зворотних зв'язків регістра зсуву, і представник циклу, що підлягає генерації, після чого виконується формування циклу, довжина якого визначається значенням, що зчитується з пам'яті генератора; після завершення формування циклу проводиться заміна представника циклу і виконується формування наступного циклу, зазначений процес повторюється до тих пір, поки не будуть сформовані всі цикли поточного генераторного полінома. UA 86705 U (54) СПОСІБ ФОРМУВАННЯ ПОСЛІДОВНОСТІ ВИПАДКОВИХ ЧИСЕЛ UA 86705 U UA 86705 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель стосується обчислювальної техніки і може бути використана для створення таблиць підстановок і перестановок, для задання випадкових дестабілізуючих факторів під час моделювання поведінки складних систем і об'єктів, під час обміну конфіденційними даними каналами зв'язку будь-якої фізичної природи та інших застосувань. Відомий спосіб формування рекурентних послідовностей чисел максимальної довжини (або М-послідовностей), породжених регістром зсуву зі зворотним зв'язком [1]. Така m псевдовипадкова послідовність символів (слів) рівномірно розподілена в діапазоні [1,2 -1], де m m - степінь генераторного полінома, і періодична з періодом Т = 2 -1 за умови, що генераторний поліном G(x) є незвідним (ділиться тільки на себе і одиницю) і примітивним (є дільником T m m полінома x +1 тільки для Т = 2 -1 і не може бути дільником для Т < 2 -1). Практична реалізація генераторів М-послідовності дуже проста, а їх швидкодія досить велика. Ці послідовності відтворювані - фрагмент послідовності і вся послідовність відтворюються абсолютно точно при зміщенні подій у просторі та часі. Ця сукупність факторів визначила широке застосування М-послідовностей у всіх областях комп'ютерної техніки і техніки зв'язку. Разом з тим, такий принцип генерації випадкової послідовності має суттєві недоліки: - нерівномірний розподіл символів послідовності в діапазоні [0, М-1], де М - верхня межа області визначення дискретної випадкової величини, оскільки в послідовності відсутній символ "0"; - такі послідовності можуть бути створені тільки для випадкових величин, розподілених в m діапазоні [1, М-1], де М = 2 . У випадку використання М-послідовностей в системах шифрування даних істотне значення має ще один недолік - М-послідовність не забезпечує стійкість до визначення закону її формування за її відрізком. Це означає, що М-послідовність є передбачуваною і, як наслідок, не є криптографічно стійкою. Указані недоліки породжують безперервний процес вдосконалення методів генерації випадкових послідовностей чисел, заснованих на використанні регістрів зсуву зі зворотними зв'язками. Вдосконалення методів формування послідовності випадкових чисел зводиться до спроб усунення зазначених недоліків. Зокрема, зменшення помилки відтворення рівномірного закону m розподілу дискретної випадкової величини в діапазоні [0, М-1], де М = 2 , забезпечується виконанням процедури рандомізації, яка зводиться до вставки в послідовність, що генерується, символу "0", як, наприклад, показано в [2, 3]. Відомі також способи усунення кореляційних зв'язків у послідовності, складеної з кінцевої множини циклів, шляхом перестановки слів послідовності, як, наприклад, показано в [4]. Найбільш близьким за своєю суттю до пропонованої корисної моделі є патент Російської Федерації № 2472286 на цифровий генератор хаотичного сигналу [5]. Сутність використовуваного в ньому способу покращення статистичних параметрів породжуваної послідовності полягає в тому, що в генератор додатково вводять аналоговий формувач шуму, вихідний сигнал якого за допомогою порогового пристрою перетворюють у двійкову послідовність, яку додають за модулем два із сигналом у ланцюзі зворотного зв'язку регістра зсуву. У результаті відбувається рандомізація і декореляція генерованої послідовності, а сама послідовність стає непередбачуваною. Недоліком цього способу є те, що випадковий процес, породжений аналоговим генератором шуму, є невідтворюваним - жоден його фрагмент не можна точно відтворити при рознесенні в часі і в просторі. Це призводить до того, що стає неможливим виконання серії випробувань складних об'єктів за одних і тих же заважаючих факторах або виконання процедури дешифрування (раніше зашифрованого повідомлення) з рознесенням у просторі та часі. Суттю пропонованої корисної моделі є поліпшення статистичних властивостей послідовності випадкових чисел за рахунок виконання всіх згаданих вимог: - відтворюваність; - непередбачуваність; - рівномірний розподіл дискретної випадкової величини в діапазоні [0, М-1]; m - кінцевий, але значно більший величини Т = 2 -1, період повторення послідовності; - зменшення кореляції між символами послідовності, складеної з множини циклів. Виконати всі вимоги до послідовності випадкових чисел можна, якщо виконати конкатенацію всіх циклів, які може породити m-розрядний регістр зсуву зі зворотними зв'язками, і всіх послідовностей, отриманих після конкатенації циклів генератора, для різних генераторних поліномів. 1 UA 86705 U 5 10 15 20 25 30 35 40 45 50 55 60 Для цього апріорно (наприклад, на стадії розробки генератора) для заданого порядку генераторного полінома "w" визначають: - усі генераторні поліноми, які породжують послідовності, що підлягають конкатенації (число m-1 таких послідовностей може досягати значення r=2 . При цьому для полінома степеня m m 0 коефіцієнти біля х і х повинні бути рівні 1); m - довжини всіх циклів (1 ≤ L ≤ 2 -1) породжуваних кожним з генераторних поліномів; - по одному представнику кожного з циклів; - загальне число циклів к, породжуваних кожним генераторним поліномом. Усі ці дані заносяться в постійну пам'ять генератора. Під час використання генератора в нього завантажують генераторний поліном і вектор початкового завантаження (слово S(0)), після чого виконується генерація поточного циклу. Після завершення генерації L слів циклу проводиться заміна представника циклу, і генератор формує слова, що належать наступному циклу. Цей процес повторюється до тих пір, доки не будуть сформовані всі k циклів для поточного генераторного полінома. Після цього відбувається заміна генераторного полінома та формування для нього всіх циклів. Послідовність почне повторюватися лише після завершення формування всіх циклів для всіх генераторних поліномів, що містяться в пам'яті. Враховуючи, що довжина послідовності, яка складається з m конкатенації циклів, породжених одним поліномом, дорівнює Lпол = 2 , а число поліномів може m-1 досягати значення r=2 , період повторення всієї послідовності може досягати значення Тmах = 2m-1 m-1 2 , що істотно перевищує значення Т = 2 . Запропонований спосіб формування послідовності випадкових чисел може бути реалізований за допомогою пристрою, показаного на фіг. Пристрій містить: - три двійкових лічильники Ліч1, Ліч2, Ліч3 (блоки 1, 4, 8, відповідно); - дві схеми порівняння Пор1, Пор2 (блоки 2, 5, відповідно); - два постійних запам'ятовуючих пристрої ПЗП1, ПЗП2 (блоки 9, 10, відповідно); - m-входовий суматор за модулем два Σ mod2 (блок 3); - набір з m ключів Кл (блок 6); - m-розрядний регістр зсуву РЗ (Блок 7). На стадії виготовлення генератора в ПЗП1 заносяться всі представники циклів, що конкатенуються, (S(0)), та всі вказівники довжини кожного з цих циклів (L), а в ПЗП2 - число циклів (k), породжуваних генераторним многочленом, і всі використовувані генераторні многочлени G(x). Пристрій працює наступним чином. У момент запуску генератора лічильники Ліч1, Ліч2, Ліч3 встановлюються в нульовий стан. Для ПЗП2 виходи Ліч3 визначають адресу комірки з інформацією. За адресою 000…0 з ПЗП2 зчитується перший з генераторних многочленів G1(x) і число циклів k1, породжуваних цим генераторним многочленом. Генераторний многочлен G1(x), зчитаний з ПЗП2, встановлює в стан "замкнуто" або "розімкнуто" ключі блока ключів Кл, що підключені до відводів регістра зсуву РЗ, при цьому замкнутими є ті ключі, які відповідають двійковій одиниці в записі полінома, а розімкнуті - які відповідають бінарному нулю в записі полінома. У результаті цього до суматора за модулем 2 Σ mod 2 виявляються підключеними ті відводи регістра, які відповідають двійковій одиниці в записі полінома. Результат підсумовування надходить на вхід запису D регістра зсуву. Крім того, за зчитаним з ПЗП2 поліномом G1(x) з ПЗП1 зчитується перший представник циклу цього полінома, який завантажується в регістр зсуву в якості слова S(0), і вказівник довжини цього циклу L. У результаті цих дій у відводах регістра формується перше слово циклу, яке видається на вихід генератора (це слово S(0)). Під час надходження імпульсів на тактовий вхід С регістра зсуву відбувається формування наступних слів циклу, які виводяться на вихід генератора. Крім того, під час надходження імпульсів на тактовий вхід лічильника Ліч1 проводиться прирощення на +1 стану лічильника - підрахунок числа згенерованих слів у циклі. Це число порівнюється (схемою порівняння Пор1) з числом L - вказівником числа слів у цьому циклі. Як тільки число згенерованих слів зрівняється із заданим значенням L, на виході схеми порівняння Пор1 з'являється імпульс, який встановлює в стан "0" Ліч1 та ініціює прирощення на +1 стану Ліч2. Прирощення стану Ліч2 змінює адресу слова, що зчитується з ПЗП1 - змінюється представник циклу і його довжина. Після зміни представника циклу регістр зсуву зі зворотним зв'язком РЗ генерує символи наступного циклу, а лічильник Ліч1 підраховує кількість згенерованих слів, поки їх кількість не стане рівною L. Так цикл за циклом згенеровані слова виводяться на вихід регістра. 2 UA 86705 U 5 10 15 20 25 30 35 40 45 Коли число згенерованих циклів досягне значення k, схема порівняння 2 сформує імпульс, який ініціює прирощення на +1 стану лічильника Ліч3. Зміна стану лічильника Ліч3 змінить адресу зчитуваної з ПЗП2 комірки, що призведе до виводу наступного значення генераторного полінома і числа циклів k. У результаті відбудеться заміна генераторного полінома і представника циклу, генератор почне генерувати нову послідовність слів для нового генераторного полінома. Так триватиме до тих пір, поки не будуть перебрані всі генераторні поліноми і всі цикли, що підлягають конкатенації. m Період сформованої послідовності буде рівним Т = r·2 , де r - число поліномів, що зберігаються в ПЗП2. Максимальне число поліномів (для заданого порядку генераторного m-1 m m-1 2m-1 полінома m) дорівнює r=2 , тому максимальна довжина послідовності T mах = 2 ·2 =2 . Список джерел: 1. Р. Лидл. Конечные поля: в 2 т. / Р. Лидл, Г. Нидеррайтер; [пер. с англ. под ред. Нечаева В.И.] - М.: Мир, 1988.-822 с. 2. Митянкина Т.В. Рандомизация последовательности конгруэнтных чисел / Т.В. Митянкина, В.В. Швыдкий, А.И. Щерба // Вестник Инженерной академии Украины. - 2008. - № 2. - С. 107111. 3. Пат. 41079 Україна, МПК G06F 7/58. Спосіб рандомізації послідовності конгруентних чисел / Мітянкіна Т.В.; Швидкий В.В.; Щерба А.І.; Мітянкін М.О.; заявник та патентовласник Черкаський державний технологічний університет - №u200808187; заявл. 17.06.2008; опубл. 12.05.2009, Бюл. № 9. 4. Пат. 40649 Україна, МПК G06F 7/58. Пристрій декореляції випадкової послідовності чисел / Мітянкіна Т.В.; Швидкий В.В.; Мітянкін М.О.; заявник та патентовласник Черкаський державний технологічний університет - № u200811384; заявл. 22.09.2008; опубл. 27.04.2009, Бюл. № 8. 5. Пат. 2472286 РФ, МПК Н03В 29/00. Цифровой генератор хаотического сигнала / Семенов А.А.; Усанов Д.О.; заявник та патентовласник Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Саратовский государственный университет имени Н.Г. Чернышевского" - 2011134962/08; заявл. 19.08.2011; опубл. 10.01.2013, Бюл. № 1. ФОРМУЛА КОРИСНОЇ МОДЕЛІ Спосіб формування послідовності випадкових чисел, що використовує регістр зсуву зі зворотними зв'язками, який відрізняється тим, що апріорно (наприклад, на стадії розробки) для заданого порядку генераторного полінома визначаються і заносяться в постійну пам'ять генератора генераторні поліноми, які породжують цикли, що підлягають конкатенації, значення довжин всіх циклів для кожного з генераторних поліномів, представників кожного із циклів і загальне число циклів, що породжуються кожним генераторним поліномом; у процесі формування послідовності в регістр зсуву зі зворотними зв'язками по черзі завантажуються генераторний поліном, що визначає структуру зворотних зв'язків регістра зсуву, і представник циклу, що підлягає генерації, після чого виконується формування циклу, довжина якого визначається значенням, що зчитується з пам'яті генератора; після завершення формування циклу проводиться заміна представника циклу і виконується формування наступного циклу, зазначений процес повторюється до тих пір, поки не будуть сформовані всі цикли поточного генераторного полінома, після чого проводиться заміна генераторного полінома і почергове формування всіх циклів для наступного генераторного полінома, формування циклів проводиться для всіх генераторних поліномів, що знаходяться в пам'яті. 3 UA 86705 U Комп’ютерна верстка І. Мироненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4