Rtf template

«Упругие» функции 
Еще один подход к усилению случайности путем фильтрации через 
некоторый детерминированный процесс – это использование упругих функций, 
которые были введены Сунаром, Мартином и Стинсоном [15, 21] в качестве шага 
постобработки для ГСП на свободных осцилляторах.
 
Вопросы для самоконтроля 
1.
Что такое истинно случайная последовательность? 
2.
Что собой представляет генератор истинно случайных последовательностей? 
3.
Перечислите наиболее известные источники случайности, встречающиеся в 
природе. 
4.
Какие генераторы случайных последовательностей, основывающиеся на 
хаотических процессах, применяются чаще всего? 
5.
Охарактеризуйте 
квантовые 
генераторы 
истинно 
случайных 
последовательностей. 
6.
В чем заключается сущность постобработки выходных данных генераторов? 

---

26 
Раздел 3. Генераторы псевдослучайных последовательностей
3.1 Применение генераторов псевдослучайных последовательностей 
Как уже отмечалось, псевдослучайные последовательности (ПСП) являются 
результатом работы некоторого детерминированного алгоритма, но при этом 
используются для тех же целей, что и случайные последовательности. По этой 
причине ПСП должны быть близки по своим статистическим свойствам к истинно 
случайным последовательностям. Как правило, алгоритмы генерации таких 
последовательностей используют специальное случайное начальное значение 
(
seed
). 
В силу особенностей генераторов истинно случайных последовательностей, 
которые серьезно затрудняют их использование в условиях ограниченности 
вычислительных ресурсов и необходимости работы в режиме, близком к режиму 
реального времени, существует необходимость разработки и применения 
генераторов псевдослучайных последовательностей, которые производят 
последовательности, максимально близкие по своим свойствам к истинно 
случайным. 
Общая структура генераторов псевдослучайных последовательностей 
включает следующие основные компоненты: 
1.
Источник энтропии. 
2.
Блок хранения внутреннего состояния генератора. 
3.
Блок генерации очередного значения. 
4.
Блок перехода генератора на следующий шаг. 
В настоящее время существует большое количество самых разных 
генераторов псевдослучайных последовательностей [1-4, 7, 9]. К наиболее 
популярным относятся: 

линейные и нелинейные (квадратические, кубические) конгруэнтные 
генераторы; 

генераторы, основанные на регистрах сдвига с линейной или обобщенной 
обратной связью; 

аддитивные генераторы с запаздываниями на основе последовательностей 
чисел Фибоначчи; 

высокопроизводительный генератор «вихрь Мерсенна», использующий 
свойства простых чисел; 

генераторы на базе клеточных автоматов; 

генераторы, основанные на нечеткой логике и т.д. 

---

27 
Особый класс образуют генераторы псевдослучайных последовательностей, 
выход которых может быть использован в задачах криптографии. Такие 
генераторы основаны на детерминированных алгоритмах, которые из входной 
истинно случайной последовательности битов формируют поток битов большей 
длины, практически независимых друг от друга и подчиняющихся заданному 
распределению.