Si on a un p premier plus grand que n'importe quel xk, on aura l'écriture en base p sur k bits d'un entier. Si tous les xk sont plus petits que p, on a directement l'unicité de l'empreinte (si l'empreinte est égale, on aura nécessairement trouvé le motif) Dans le cas plus général où certains xk peuvent être plus grands que p, on a tout de même peu de collisions
J'ai jamais rien vu d'aussi clair, la vidéo est parfaite
Merci du compliment
très clair merci beaucoup
Merci beaucoup pour cette explication qui clairifie le formalisme mathématique un peu pompeux des bouquin ! :)
Merci
Une petite question : pourquoi p doit-il être premier pour l'empreinte de Rabin ?
Sinon, c'était une excellente vidéo !
Si on a un p premier plus grand que n'importe quel xk, on aura l'écriture en base p sur k bits d'un entier.
Si tous les xk sont plus petits que p, on a directement l'unicité de l'empreinte (si l'empreinte est égale, on aura nécessairement trouvé le motif)
Dans le cas plus général où certains xk peuvent être plus grands que p, on a tout de même peu de collisions
Il n'est pas nécessaire que p soit premier, mais algébriquement il est probable que cela minimise les collisions.