Math
Anniversaires et collisions
Des gens arrivent sur un anneau de jours jusqu'à ce que deux en partagent un : dans une année de 365 jours c'est la 23e personne, pas la 183e ; sur Mars la 32e ; dans 65 536 alvéoles de hachage la 302e ; des tirages contre la courbe exacte, les jours balayés en glissant d'une année à 2³², la règle de la racine carrée lue en direct, et une tâche sur la salle martienne.
Ce qui se passe
Un anneau de jours. Les gens arrivent un à un et allument le jour où ils tombent ; la première fois que quelqu'un tombe sur un jour allumé, l'anneau s'embrase et le tirage est fini. Dans une année de 365 jours cela arrive vers la 23e personne, pas la 183e, parce que la question n'est pas de savoir si quelqu'un partage ton anniversaire mais si deux quelconques en partagent un, et il y a 253 paires parmi 23 personnes. La courbe exacte est 1 − (1 − 1/m)(1 − 2/m)…(1 − (n − 1)/m) : 50,7 % à 23, 99 % à 57. Tirage après tirage, le graphe remplit la fraction empirique sur la courbe. Glisse sur l'anneau et le nombre de jours balaie en échelle logarithmique : une année martienne de 687 jours demande 32 personnes, une table de hachage de 65 536 alvéoles entre en collision à la 302e clé, un hachage de 32 bits vers la 77 000e ; la salle qui entre en collision avec une chance sur deux suit √(2m ln 2), la racine carrée des jours, pas les jours. C'est pourquoi un hachage a besoin de bien plus d'alvéoles que de clés, et pourquoi l'attaque des anniversaires est le moyen le moins cher de casser une signature courte.
Équations du module
Équations collision parmi n personnes : P = 1 − (1 − 0/m)(1 − 1/m)…(1 − (n − 1)/m) ; 365 jours : 22 personnes 47.6 %, 23 personnes 50.7 %, 57 personnes 99 % ; la première collision attendue est la 24.617e personne le groupe pile ou face (plus petit n avec P ≥ ½) : 365 → 23, Mars 687 → 32 (52.0 %; 31 donne 49.7 %), 65 536 alvéoles → 302, 2^32 → 77 164 la règle de la racine carrée : n ≈ √(2m ln 2) = 22.5, 30.9, 301.4, 77 162.7 - le groupe croît comme la racine carrée du nombre de jours, non comme le nombre de jours essais : un tirage par personne, jour = floor(r·m), avec le xorshift commun ; graine 1 en 365 jours : la quarantième personne tombe le jour 200, déjà pris par la trente-quatrième ; graines 1…1000 : 518 ont une collision parmi 23 personnes, première collision moyenne 24.05 hachages : la même arithmétique pour des clés dans des alvéoles - un hachage 32-bits devrait produire une collision après environ 77 000 clés
