The birthday paradox refers to the famous surprising fact that if you find yourself in a gathering of 23 people then there is a better than even chance that two of the people in the room share a birthday. It seems a paradox because there are 366 possible dates for each birthday so the chance of two people being born on any given day is only (1/366)^2 or about 0.00000746. The reason you only need 23 people to beat the odds is that you don’t care which date they share and that there are a lot of pairs of people!
The reason I am telling you about this is that the birthday paradox plays an important role in cryptography. For example, one of the most important public key ciphers in current use is the RSA cipher and its security depends on the fact that prime factorisation is a very time consuming process. The birthday paradox helps to speed up the prime factorisation process, but even that is not enough to break 2048bit RSA on a modern computer. Of course quantum computers are a lot more powerful and recently a Chinese team announced significant progress in using them to break modern ciphers. Their method is still not fast enough to overcome the security of the RSA ciphers used online, but it is a warning that new ciphers will be needed soon!
Anyway, this is a Sunday post, so you are probably expecting a puzzle. I don’t have a good birthday paradox puzzle for you, but I did see the following birthday puzzle at Mr Barton’s maths site. Enjoy!
Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gives them a list of 10 possible dates.
May 15 May 16 May 19
June 17 June 18
July 14. July 16
August 14. August 15. August 17
Cheryl then tells Bernard and Albert separately the month and the day of her birthday respectively.
Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know too.
Bernard: At first I don’t know when Cheryl’s birthday is, but I know now.
Albert: Then I also know when Cheryl’s birthday is.
When is Cheryl’s birthday?