Accueil    Développement    LEX & YACC    Outils    Liens Web  
Divers
Accélération de Firefox
Authentification type BASE
DigiCode - Comment essayer toutes les combinaisons en une seule passe.
News - Que sont elles ?
DigiCode Comment essayer toutes les combinaisons en une seule passe. Impression de l'article

Le secret du DigiCode percé grâce aux circuits Eulériens

Le digicode, est un appareil qui n’a en général, que fort peu de mémoire : il ne se souvient que des p dernières touches enfoncées sur son clavier, p représentant la longueur du code qui permet d’ouvrir.

Mais chercher à forcer une porte en essayant systématiquement toutes les combinaisons sur un digicode à n touches nécessite bien sûr une stratégie. Celle qui consistera à essayer de taper une séquence la plus courte possible et contenant au moins une fois chacune des np combinaisons différentes. Dans l’exemple simpliste où le digicode n’aurait que n = 3 touches différentes (0, 1 et 2) et où le code serait de longueur p = 2, la séquence 0011021220 répond à ce critère, puisqu’on peut aisément vérifier qu’elle contient une occurence de chacune des 32 = 9 combinaisons possibles. De plus, elle est de longueur minimale, chaque combinaison n’y étant présente qu’une seule fois. Une telle séquence porte un nom, celui de séquence de de Bruijn, en l’honneur du matématicien hollandais qui les a étudiées dans les années quarante. Ces séquences constituent la solution optimale au problème du digicode, la question restant alors de savoir si l’on peut en trouver quels soient les nombres n et p considérés.

A cette question, Euler donne une nouvelle fois la réponse, grâce à une transposition astucieuse de ce problème sous forme d’un graphe. Dès lors, si l’on cherche un code de longueur p, on trace un graphe contenant np-1 sommets, correspondant à toutes les combinaisons de touches de longueur p - 1.


Pour engendrer des séquences de de Bruijn sur un ordinateur, la méthodes la plus simple est l’utilisation d’une relation de récurence linéaire modulo n. Ceci n’est possible de manière simple que si la longueur n de l’alphabet sur lequel on travaille (le nombre de touches du digicode) est un nombre premier. La méthode pour trouver les coefficients de ces relations de récurence fait appel à des notions complexes d’algèbre (la théorie des polynômes primitifs dans le corps fini Z/nZ).

En voici quelques-unes pour différents valeurs de n et p.

n = 2 p = 8 un+8 = un+7 + un+6 + un+1 + un modulo 2
n = 2 p = 10 un+10 = un+8 + un modulo 2
n = 3 p = 4 un+4 = 2un+3 + un modulo 3
n = 3 p = 8 un+8 = 2un+5 + un modulo 3
n = 5 p = 4 un+4 = 4un+3 + 4un + 1 + 2un modulo 5
n = 13 p = 4 un+4 = 12un+3 + 12un+1 + 10un modulo 13

630 visiteswebmaster le 20.06.2002
Copyright 2000-2009 BUCHARD@com