Les fonctions de hachage différentielles, application à la génération de graphes d'états
Résumé
Differential hashing functions have a differential computation process which enables hashing function processing time to be optimized. Formal definition of the differential property for hashing functions is proposed, and we show that not all hashing functions have this property, then we propose a characterization of the differential hashing function set. Next, we show the performance acceleration produced by the differential algorithms applied to five hashing functions found in common applications. The observed accelerations can be significant because they are proportional to key length. Last, we study the performances of differential hashing functions for the reachability graph exploration of distributed systems specified by a Petri net.
Les fonctions de hachage différentielles possèdent un procédé de calcul différentiel qui permet d'optimiser le temps d'exécution des fonctions de hachage vis-à-vis du procédé usuel tout en obtenant exactement la même valeur de hachage. Nous définissons la propriété d'être différentielle pour une fonction de hachage, puis nous montrons que toutes les fonctions de hachage ne possèdent pas cette propriété, enfin nous proposons une caractérisation de l'ensemble des fonctions qui la possède. Nous nous attachons ensuite à montrer le gain en performance induit par l'utilisation d'algorithmes différentiels de quatre fonctions de hachage trouvées dans la littérature. Les gains observés étant proportionnels à la taille de la clef, ils peuvent être extrêmement importants. Nous utilisons alors une fonction de hachage différentielle pour la génération de graphes d'états issus de modèles décrits moyen de réseaux de Petri.
Origine : Fichiers produits par l'(les) auteur(s)