Аннотация:Одной из характеристик качества псевдослучайного генератора, представляющего собой автомат, является
его мера, которая может принимать всего два значения, 0 и 1. В приложениях предпочтительнее, разумеется,
автоматы полной меры чем нулевой меры, но критериев того, что автомат имеет полную меру, не известно.
Однако известно, что конечные автоматы имеют нулевую меру, и известны критерии ограниченной детер-
минированности функции. Применение таких критериев дает возможность отсекать заведомо плохие с кри-
птографической точки зрения детерминированные функции. К сожалению, даже если известно, что данная
детерминированная функция не может быть задана автоматом с конечным числом состояний, т.е. что она не
является ограниченно детерминированной, это еще не означает, что автомат имеет полную меру, он может
иметь и меру 0, причем этот факт может быть совсем не очевидным и достаточно сложным для выявления. В
данной работе изучаются именно такие «коварные» автоматы, применяющиеся в качестве криптографических
примитивов.