Ouais le problème réside dans la définition de l'algo utilisé dans le checksum.
Démonstration :
je check la parité binaire du fichier. S'il y a un nombre pair de 1, je rajoute 101 a la fin du fichier. Mon "checksum" est 101, il ne change pas la parité. Si j'ai un nombre impair de 1, je met 110 (pour changer, et on comprend l'interet du 0 entre les 1). Je ne change pas la parité non plus. Donc mon algo marche.
Je viens de démontrer l'existence d'un tel algo, héhé.
Bon apres, vous me direz que mon checksum, il prend que 2 valeurs possibles, bah c'est quand meme un checksum hein.
Donc un tel algo existe, je viens d'en exhiber un, j'ai répondu a ta question.
Bon plus sérieusement, le problème c'est la construction du checksum. Si l'on veut un checksum de qualité, il faut qu'il soit long, et plus il est long plus il a de chance d'etre de qualité (i.e. peu de collisions, et ecart important pour de faible variation).
Mais plus le checksum est long plus la complexité du problème est élevée.
Pour cela plusieurs solutions :
- utiliser un algo de type suite récursive (cf premier commentaire) qui converge. Il faut trouver une fonction potable, mais ça doit se trouver, c'est des maths.
- utiliser un algo magique qui fait que ca marcherait en une itération (faut pas rever)
- utiliser un algo statistique du genre construction progressive du checksum. Cela demanderait des propriétés assez contradictoires avec une maximisation de l'écart important pour de faibles variations.
- ou pour finir la solution que je préconiserais :
Utiliser successivement des algo de checksum utilisant une longueur de checksum de plus en plus petites (on concatène à chaque fois le checksum calculé), et on pourrai finir par exemple sur mon algo a 2 balles. A l'extreme limite, utiliser un checksum standard (md5) plus mon algo a la con. -> le checksum serait intégré au fichier, de qualité (md5) et vérifierait ta question. On connaitrait de plus la longueur du checksum, il suffit alors de couper la partie checksum du fichier :).
Des 4 solutions proposées, les 3 premières relèveraient plus de travaux mathématiques (je pense plus que c'est de ce coté que se penche ta question ;) ), alors que la derniere est plus une solution "technique".
Compenser la différence impliquée par le checksum n'est pas envisageable sur un checksum de taille conséquente (a moins que la fonction mathématique utilisée dans le checksum possède des propriétés particulières).
# Re: Question existentielle
Posté par inz . En réponse au journal Question existentielle. Évalué à 7.
Démonstration :
je check la parité binaire du fichier. S'il y a un nombre pair de 1, je rajoute 101 a la fin du fichier. Mon "checksum" est 101, il ne change pas la parité. Si j'ai un nombre impair de 1, je met 110 (pour changer, et on comprend l'interet du 0 entre les 1). Je ne change pas la parité non plus. Donc mon algo marche.
Je viens de démontrer l'existence d'un tel algo, héhé.
Bon apres, vous me direz que mon checksum, il prend que 2 valeurs possibles, bah c'est quand meme un checksum hein.
Donc un tel algo existe, je viens d'en exhiber un, j'ai répondu a ta question.
Bon plus sérieusement, le problème c'est la construction du checksum. Si l'on veut un checksum de qualité, il faut qu'il soit long, et plus il est long plus il a de chance d'etre de qualité (i.e. peu de collisions, et ecart important pour de faible variation).
Mais plus le checksum est long plus la complexité du problème est élevée.
Pour cela plusieurs solutions :
- utiliser un algo de type suite récursive (cf premier commentaire) qui converge. Il faut trouver une fonction potable, mais ça doit se trouver, c'est des maths.
- utiliser un algo magique qui fait que ca marcherait en une itération (faut pas rever)
- utiliser un algo statistique du genre construction progressive du checksum. Cela demanderait des propriétés assez contradictoires avec une maximisation de l'écart important pour de faibles variations.
- ou pour finir la solution que je préconiserais :
Utiliser successivement des algo de checksum utilisant une longueur de checksum de plus en plus petites (on concatène à chaque fois le checksum calculé), et on pourrai finir par exemple sur mon algo a 2 balles. A l'extreme limite, utiliser un checksum standard (md5) plus mon algo a la con. -> le checksum serait intégré au fichier, de qualité (md5) et vérifierait ta question. On connaitrait de plus la longueur du checksum, il suffit alors de couper la partie checksum du fichier :).
Des 4 solutions proposées, les 3 premières relèveraient plus de travaux mathématiques (je pense plus que c'est de ce coté que se penche ta question ;) ), alors que la derniere est plus une solution "technique".
Compenser la différence impliquée par le checksum n'est pas envisageable sur un checksum de taille conséquente (a moins que la fonction mathématique utilisée dans le checksum possède des propriétés particulières).