Всем добрый день. Агнер Фог на своей страничке приводит среди прочих ГПСЧ алгоритм Mother-of-all PRNG's, разработанный неким Джорджем Марсагли. Этот алгоритм я использовал при решении некоторой задачи, специфика которой подразумевает инициализацию именно всего состояния этого ГПСЧ некоторым заранее выбранным случайным значением (т.е. все 160 бит). Собственно, проблема в том, что длина цикла этого ГПСЧ согласно Фогу равна примерно 2158, что является примерно четвертью от числа всех возможных состояний (2160). Т.е. оставшиеся три четверти состояний могут давать зацикливание со значительно меньшей длиной. Соответственно, если инициализировать ГПСЧ вышеозначенным некошерным образом, то можно нарваться на цикл длиной в три состояния, что будет ни разу не криптостойко. Вопрос в следующем. Насколько просто (и как) узнать длину цикла (или хотя бы факт принадлежности к циклу с длиной 2158) для некоторого произвольно выбранного стартового состояния данного ГПСЧ?
Зря я, наверное, Марсагли "неким" назвал. А по поводу остального по всей видимости можно действительно инициализировать все 160 бит произвольно кроме двух наборов: Код (Text): DWORD state[] = {0,0,0,0,0}; DWORD state[] = {4294967295,4294967295,4294967295,4294967295,2111119493}; На обоих наборах ГПСЧ деградирует до периода 1. Любые другие наборы должны приводить к одному из двух возможных циклов длиной 2158, возможно с некоторой ведущей последовательностью, которая повторяться не будет. С другой стороны у Марсагли есть статья "Seeds for Random Number Generators", написанная для дилетантов вроде меня с минимумом математики, где он приводит более-менее общий вид complimentary-multiply-with-carry PRNG, где можно задавать желаемое количество произвольно задаваемых бит. У минимального варианта с 256-ю произвольно задаваемыми битами (полное состояние — 288 бит) период превышает 2285.
