¿Cuántos hashes debo calcular para obtener x colisiones?

0

Sé que necesitas hacer un hash de aproximadamente 2 ^ (N / 2) para encontrar una colisión teniendo en cuenta el problema de cumpleaños.

Pero no estoy realmente seguro de más de una colisión, quiero decir, colisiones con diferentes valores (H (A) = H (B); H (C) = H (D)).

No sé si es correcto si digo que para el número X de colisiones, debería incluir valores de sqrt (x * 2 ^ N) para encontrar el número X de colisiones diferentes.

¿Puede decirme si esta es una suposición correcta o no? y por que?

    
pregunta Alex 13.03.2016 - 19:42
fuente

1 respuesta

2

Como aproximación , su estimación está cerca: si X es el número de colisiones, necesita el hash SQRT (X * 2 N + 1 ) valores.

Para obtener una explicación matemática, puede consultar esta respuesta en Matemáticas ; y específicamente, la aproximación de ShreevatsaR (su N es tu 2 N , con N su número de bits).

( lo siento, no entendí tu solicitud en una versión anterior de esta respuesta. Mi error )

    
respondido por el LSerni 13.03.2016 - 20:15
fuente

Lea otras preguntas en las etiquetas