Comput unicum 1113325234 (Tue, 12 Apr 2005 19:00:34 +0200), Vincent DUVERT a �crit : > > pingouin osmolateur a �crit : > > > Attention : en suivant la bonne id�e de Stephane, > > Je propose pour vendredi (jour du Troll) de trouver de > > 2 emails "valides" ayant les memes 20 premiers > > carat�res du condens� md5 identiques. > > St�phane m'offre la biere et moi j'offre la biere aux > > deux adresses email. > > > > A vos marques !!! > > Je sens que les machines vont tourner � bloque pour > > trouver les deux adresses. > > Bon, alors : > Nombre de possibilit�s d'une combinaison = (Nombre de possibilit�s par > signe)^(Nombre de signes) > > Exemple : Un compteur de 0000 � 9999 > 10^4 = 10000 -> correct. > > MD5 : 32 caract�res (on ram�ne � 20, vu que pour le concours les 12 > derniers sont ignor�s), avec chacun 36 possibilit�s (a-z 0-9) > 20^32=429496729600000000000000000000000000000000
Tu veux dire 36^20, je suppose. Soit 13 367 494 538 843 734 067 838 845 976 576. (Ce qui est beaucoup moins que 32 chiffres � 20 possibilit�s par chiffre.) > L�g�rement plus que le nombre d'internautes dans le monde... Donc c'est > pas s�r qu'il y ait 2 adresses dans le monde qui aient la m�me somme > md5. Il n'est pas n�cessaire d'avoir plus de 365 personnes dans un groupe pour avoir des chances suffisamment grandes d'en avoir deux avec le m�me anniversaire (jour et mois, pas ann�e). D�s qu'on d�passe 23 personnes, la probabilit� d�passe 50 % ! La probabilit� pour que deux adresses donnent le m�me md5 tronqu� est la probabilit� compl�mentaire du cas o� les md5 diff�rent. Donc 1 - (N-1)/N. Pour 3 adresses : 1 - (N-1)(N-2)/N�. Donc, si je ne me trompe pas, avec n adresses : 1 - N! / [N^n . (N-n)!] Si on pose n = 1e9 (ce qui est peu), la proba est de : ... euh, je vous le redirai quand le calcul sera termin�... ou peut-�tre m�me _si_ le calcul termine... -- Sylvain Sauvage
