Лекция 10

Эквивалентные ЭКА: преобразование отражения. Неподвижные точки. Подсчёт количества неэквивалентных ЭКА напрямую. Понятие действия группы на множестве, подсчёт количества неэквивалентных ЭКА на основе леммы Бёрнсайда.

Классификация ЭКА по Стивену Вольфраму.

Вариант конечных автоматов: автоматы-генераторы, области применения. Период и полный период. Качество случайности по BSI (Немецкое бюро информационной безопасности), примеры простейших статистических тестов.

Линейный конгруэнтный генератор. Полный период. Спектральное тестирование, RANDU. Теорема Халла—Добелла.

Регистры сдвига с линейной обратной связью. Пример. Задание регистра сдвига с линейной обратной связью с помощью многочлена. Примитивные многочлены.