Парадокс «дней рождений»

В классическом варианте парадокс «дней рождений» звучит так. Если считать, что дни рождения распределены равномерно, то в группе иэ 24 человек с вероятностью 0,5 у двyx человек празднования дней рождения coвпадут.

В криптоанализе этот парадокс используется следующим образом. Пусть С – не пустое множество, а А и В подмножества С. Тогда с большой степенью уверенности можно утверждать, что множества А и В пересекаются хотя бы один раз, если их размеры удовлетворяют следующему условию:

где а – размер множестваД, b – размер множества В, с – размер множества С.

 

Источник: Acoсков А. В., Иванов М. A., Мирский А. A., Рузин А. В., Сланин А. В., Тютвин А. Н. Поточные шифры. – M.: КУДИЦ-ОБРАЗ, 2003. – 336 с.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100