Генератор Фібоначчі

Генератор Фібоначчі (англ. lagged Fibonacci generator) — генератор псевдовипадкових чисел, також названий адитивний генератор.

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

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

Історія

Послідовність, в якій $X_{n+1}$ залежить більше, ніж від одного з попередніх значень, і яка визначається наступною формулою:

$X_{n+1}=(X_{n}+X_{n-1})\mod (2^{m}),$

носить назву послідовність Фібоначчі.

На початку 50-х років вивчався даний алгоритм, проте, дослідження показали, що цей генератор, як джерело випадкових чисел, був неефективний. Вчені запропонували допрацьовану формулу послідовності Фібоначчі у вигляді:

$X_{n+1}=(X_{n}+X_{n-k})\mod (2^{m}).$

Однак, позитивний результат вийшов лише при $k\geq 16$.

У 1958 році було виведено послідовність:

$X_{n}=(X_{n-24}+X_{n-55})\mod (2^{m}),$

де, $n\geq 55$, $m$ — парне число, $X_{0},X_{1},...,X_{54}$ - довільні цілі не всі парні числа. Числа 24 і 55 обрані так, щоб визначалася послідовність, молодші значущі числові розряди $(X_{n}\mod (2))$ якої мають довжину періоду $2^{55}-1$.

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

Формула

Адитивні генератори генерують замість випадкових бітів випадкові слова.

Для роботи адитивному генератору потрібно якийсь початковий стан, який є ключем - набір n-бітових слів: 16-бітових, 32-бітових, 64-бітових слів і т. Д. - $X_{1},X_{2},...,X_{k}$.

Знаючи початковий стан, можна обчислити $i-$е слово генератора за формулою :

$X_{i}=(X_{i-a}+X_{i-b}+...+X_{i-k})\mod (2^{m}),$

причому період генератора повинен бути більше або дорівнювати $2^{m}-1$.

Приклади алгоритмів, на основі адитивних генераторів

$(x\oplus 1)^{S},\quad \quad S={\overline {1,7}}$

S	1	2	3	4	5	6	7
$f(x)$	3	5	17	21	63	125	377
Випадкові послідовності	$\{1(2)\}$	$\{1(4)\}$	$\{2(4)\}$	$\{2(8)\}$	$\{4(8)\}$	$\{8(8)\}$	$\{16(8)\}$
Г е н е р а т о р и Ф і б о н н а ч і	$(M-1)$ 01	$(M-3)$ 0011	$(M-3)\Pi$ 0001, 0111	$(M-7)\Pi$ 00001111, 01011010	$(M-7)\Pi$ 00000101, 00011011, 00100111, 01011111	$(M-7)\Pi$ 00000011, 00001001, 00010111, 00011101, 00101011, 00110101, 00111111, 01101111	$(M-7)\Pi$ 00000001, 00000111, 00001011, 00001101, 00010011, 00010101, 00011001, 00011111, 00100101, 00101111, 00110111, 00111011, 00111101, 01010111, 01011011, 01111111

При $S={\overline {5,7}}$ для випадкової послідовності $\{4(8)\}-\{16(8)\}$ усі $(M-7)\Pi \Pi$ різні, причому половина їх інверсні. Жирним шрифтом виділені послідовності де Брейна.

1) Один з широко поширених генераторів Фібоначчі ґрунтується на наступній ітеративній формулі:

$X_{k}={\begin{cases}X_{k-a}-X_{k-b},&{\text{if }}X_{k-a}\geq X_{k-b};\\X_{k-a}-X_{k-b}+1,&{\text{if }}X_{k-a}<X_{k-b};\end{cases}}$

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

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

$T=(2^{\max\{a,b\}}-1)\cdot 2^{\ell },$

де $\ell$ - число бітів дійсного числа.

Вибір параметрів

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

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

В даний час підібрано досить багато пар чисел a і b, наведемо деякі з них:

$(24,55),(38,89),(37,100),(30,127),(83,258),(107,378),(273,607),(1029,2281),(576,3217),(4178,9689),...$

2) Брюс Шнайєр у своїй роботі «Прикладна криптографія» наводить приклади 3-х алгоритмів на основі адитивних генераторів :

Алгоритм Fish

Fish - це адитивний генератор, заснований на методах, які використовуються в проріджувальному генераторі. Він видає потік 32-бітових слів, які можуть бути використані (за допомогою XOR) з потоком відкритого тексту для отримання шифротекста або з потоком шифротекста для отримання відкритого тексту. Назва алгоритму являє собою скорочення від Fibonacci shrinking generator - проріджувальний генератор Фіббоначі.

По-перше, використовуйте два наступних адитивних генератора. Ключем є початкові стани цих генераторів.

$A_{i}=(A_{i-55}+A_{i-24})\mod (2^{32})$

$B_{i}=(B_{i-52}+B_{i-19})\mod (2^{32})$

Ці послідовності проріджуються попарно в залежності від молодшого значущого біта $B_{i}$: якщо його значення дорівнює 1, то пара використовується, якщо 0 — ігнорується. $C_{j}$ — це послідовність використаних слів $A_{i}$, a $D_{j}$ — це послідовність використаних слів $B_{i}$. Для генерації двох 32-бітових слів-результатів $K_{2j}$ і $K_{2j+1}$ ці слова використовується парами — $C_{2j},C_{2j+1},D_{2j},D_{2j+1}$.

$E_{2j}=C_{2j}\oplus (D_{2j}\land D_{2j+1})$

$F_{2j}=D_{2j+1}\oplus (E_{2j}\land C_{2j+1})$

$K_{2j}=E_{2j}\oplus F_{2j}$

$K_{2j+1}=C_{2j+1}\oplus F_{2j}$

Цей алгоритм швидкий на процесорі i486/33 реалізація Fish на мові С шифрує дані зі швидкістю 15-Мбіт/с. На жаль він є небезпечним, порядок розкриття становить близько 2 ⁴⁰.

Алгоритм Pike

Pike - це збіднена і урізана версія Fish, запропонована Росом Андерсоном, тим, хто зламав Fish. Він використовує три адитивних генератора. Наприклад:

$A_{i}=(A_{i-55}+A_{i-24})\mod (2^{32})$

$B_{i}=(B_{i-57}+B_{i-7})\mod (2^{32})$

$C_{i}=(C_{i-58}+C_{i-19})\mod (2^{32})$

Для генерації слова потоку ключів погляньте на біти перенесення при додаванні. Якщо всі три однакові (всі нулі або всі одиниці), то тактуються всі три генератора. Якщо немає, то тактуються тільки два співпадаючих генератора. Збережіть біти перенесення для наступного разу. Остаточним виходом є XOR виходів трьох генераторів.

Pike швидше Fish, так як в середньому для отримання результату потрібно 2.75 дії, а не 3. Він також занадто новий, щоб йому довіряти, але виглядає непогано.

Алгоритм Mush

Mush є взаємно проріджувальний генератор. Його роботу пояснити легко. Візьмемо два адитивних генератора: А і В. Якщо біт перенесення А встановлено, тактується В. Якщо біт перенесення В встановлено, тактується А. Тактуємо А і при переповненні встановлюємо біт перенесення. Тактуємо В і при переповненні встановлюємо біт перенесення. Остаточним виходом є XOR виходів А і В. Найпростіше використовувати ті ж генератори, що і в Fish:

$A_{i}=(A_{i-55}+A_{i-24})\mod (2^{32})$

$B_{i}=(B_{i-52}+B_{i-19})\mod (2^{32})$

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

Посилання

• http://www.phy.ornl.gov/csep/rn/node20.html [Архівовано 30 січня 2014 у Wayback Machine.]
• Aluru, S. (1997). Lagged Fibonacci Random Number Generators for Distributed Memory Parallel Computers. [Архівовано 26 березня 2014 у Wayback Machine.] JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 45, 1-12.