ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   05 Feb 2003  13:55:50
 To : Dankov
 Subject : Как оценить случайность набора битов?
 -------------------------------------------------------------------------------- 
 

 Wed Feb 05 2003 12:04, Dankov wrote to All:
 
  D> Итак, есть генератор случайных чисел, выдающий последовательность битов.
  D> При каждом запуске последовательность разная.
 
  D> Как мне оценить, что эта последовательность достаточно "случайная" и
  D> вообще похожа на случайную, для целей, например, генерации ключей? Как
  D> оценить степень похожести на белый шум? Как узнать наличие и размер
  D> корреляции, девиации и периода?
 
 0. Читать 2-й том Кнута, в значительной степени этому посвященный.
 1. Если генератор доступен математическому исследованию, то много можно узнать
 о нем не вычисляя ничего. В противном случае придется считать.
 2. Для оценки периода есть остроумный прием, состоящий в том, что на каждом
 шаге вычисляют ГСЧ трижды. Единожды и дважды.
 x[n+1]=R(x[n])
 y[n+1]=R(R(y[n]))
 и ищут совпадения. Расстояние между оными = период.
 3. Корреляцию, среднее и дисперсию считаем напрямую, по обычным формулам.
 4. Спектр вычисляем через корреляцию или через Фурье. (Собственно, "белый шум"
 это плоскота спектра).
 5. Случайность понятие многообразное, так что тестов много ("покер",
 "собирателя купонов"...), а равномерность проверяют Хи-квадратом или
 Колмогоровым-Смирновым (собственно, прежде названные тесты тоже их
 используют).
 6. А вот насчет допустимости для генерации ключей - тут еще есть
 нематематические аспекты... Hапример, существуют ли методы восстановления
 параметров ГСЧ по нескольким его значениям...
 7. Есть мнение, что генераторы, ориентированные на выдачу битов, плохо
 генерируют числа, если числа эти составляются из последовательных битов.
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор