PICSI

Un moyen majeur de détection d’une suite aléatoire est d’observer la façon dont elle peut être compressée sans perte d’informations. En effet, les algorithmes de compression sans pertes utilisent des répétitions de séquences, appelées mots, pour économiser de la place : au lieu de stocker chaque octet, l’algorithme crée une table (un dictionnaire) de mots auxquels sont associés leurs occurrences dans le fichier. S’il n’y a aucune répétition, non seulement le gain de place est nul, mais il y a en réalité perte de place à cause de l’en-tête du fichier où sont stockées des informations nécessaires à la décompression. Ainsi lors de la compression d’une séquence aléatoire, aucune place significative ne doit être gagnée.

Le principe de ce test est de mesurer l’écart entre deux mots identiques dans la suite. Pour cela le test prend deux paramètres : la longueur des mots L et le nombre de mots utilisés pour créer le dictionnaire Q. Le programme parcourt la suite et commence par créer un dictionnaire avec les Q premiers mots. Celui-ci contient la position de la dernière occurrence du mot (on peut donc considérer que le dictionnaire est un tableau à 2 colonnes : dans la première se trouve le mot et dans la seconde se trouve sa position de la dernière occurrence). Le parcours du reste de la suite permet de mettre à jour les positions des dernières occurrences et de calculer une valeur qui servira pour déterminer si la suite est aléatoire ou pas grâce à une comparaison avec des valeurs théoriques (on dispose de tables dans des livres comme le « Handbook of Applied Cryptography »). Cette valeur est la somme des logarithmes en base deux des écarts entre deux occurrences consécutives du même mot (écart calculé grâce à la position de la dernière occurrence, stockée dans le dictionnaire).

            On admettra que si ce test est passé avec succès alors tous les tests statistiques classiques (test en fréquence, test de répétition etc) le seront également. Cependant ce test nécessite des suites relativement longues pour que le résultat soit significatif. Par ailleurs le programme prend un temps exponentiel en L ce qui empêche de tester de trop grandes valeurs de L.