| |
В условиях экспоненциального роста киберугроз, задача разработки и анализа генераторов псевдослучайных чисел приобретает исключительную актуальность. На сегодняшний день сохраняется актуальность вопроса, связанного с конечностью периода генерируемых последовательностей, обусловленный детерминированной природой алгоритмов, реализуемых на вычислительных машинах. Цель исследования – демонстрация принципиальной невозможности построения генератора с бесконечным периодом на основе конечного автомата, являющегося математической моделью вычислительной машины. Основу исследования составили формальные методы теории конечных автоматов, включая применение теоремы Клини для установления эквивалентности между алгоритмами генераторов псевдослучайных чисел и конечными автоматами, и теоремы о невозможности распознавания непериодических последовательностей, обосновывающей конечность периода. Проведенный анализ в рамках теории автоматов демонстрирует, что алгоритмы генерации псевдослучайных чисел реализуемы в виде конечных автоматов, а значит, подвержены ограничению числа внутренних состояний и, следовательно, конечности периода генерируемой последовательности. Научная новизна заключается в явном применении теоретических результатов теории конечных автоматов для обоснования ограниченности периода генераторов псевдослучайных чисел. Полученные результаты вносят вклад в понимание фундаментальных ограничений, накладываемых вычислительной средой на свойства генерируемых последовательностей.
Ключевые слова:алгоритм, конечные автоматы, регулярные выражения, непериодические бесконечные последовательности, теорема Клини, генераторы псевдослучайных чисел.
|
ПРАВОВАЯ
ИНФОРМАЦИЯ:
