Euro et Math

1   Euros neufs et vieilles preuves

Le début de l'année 2002 nous a amené nos beaux billets européens tout neufs. Comment résister à la question que tout le monde se posait : les numéros de ces billets contiennent-ils un code détecteur d'erreurs ?  Je suis donc allé à la première heure le 1^ier Janvier en chercher une petite liasse dans le distributeur le plus proche, espérant les trouver, puisque tout neufs, dans l'ordre logique de la numérotation. En effet, voici donc une partie des numéros que j'ai relevés :

U14164027898
U14164027889
U14164027871
U14164027862
U14164027853
U14164027844
U14164027835
U14164027826
U14164027817
U14164027808
U14164027781
U14164027772

On voit tout de suite que  la somme des chiffres modulo 9 est constante. Mais que faire de la lettre ? Hélas tous mes billets commençaient par U. J'entrepris donc de  réveiller mes voisins, mes amis qui n'avaient que trop dormi afin d'en trouver un qui aurait un billet préfixé d'une autre lettre. Hélas, personne n'avait le moindre petit billet à me mettre sous  la dent. Le croiriez vous, ils me répondaient tous que disposer d'un billet commençant par un V n'était pas leur souci principal et que d'ailleurs, n'ayant pas complètement cuvé leur alcool du réveillon ils ne s'étaient pas encore procuré les précieuses coupures. En plus ils disaient qu'il était l'heure du petit déjeuner, et que moi-même je ferais aussi bien d'aller me faire cuire un oeuf.
Heureusement, le site web de la Banque de France donne des photographies de divers billets, on y voit des numéros qui commencent par d'autres lettre que U.

A partir de là une généralisation audacieuse mais raisonnée donne à penser que la règle est la suivante :

On attribue à la lettre le nombre qui donne sa place dans l'alphabet (U est remplacé par 21). On fait alors la somme modulo 9
de ce nombre et de tous les chiffres qui le suivent et on obtient 8.

Je dois dire que j'étais un peu déçu qu'on nous ait ressorti cette vieille preuve par 9. J'ai donc recherché s'il n'y avait pas un autre mécanisme plus complexe.  Je n'en sais rien mais les deux numéros valides :

U14164027898
U14164027808
prouvent au moins qu'il existe des cas où une erreur sur un seul chiffre n'est pas détectée.

Que cela soit clair : un code détecteur n'a pas un rôle de sécurité destiné à prevenir les contrefaçons. On voit mal un faussaire  être assez débile pour fabriquer des billets dont les numéros seraient incohérents. De tels codes sont utilisés par exemple pour détecter des erreurs de saisie.

On peut tout de même se demander si on pouvait faire mieux sans grossir les nombres utilisés.

2  Pouvait-on faire mieux ?

Remarquons qu'on peut considérer que chaque numéro est formé d'une lettre, de 10 chiffres et d'un onzième chiffre pouvant être considéré comme la clé. Cette clé étant calculée de telle sorte que la somme totale (y compris la valeur de la lettre) soit 8 modulo 9. Il y a bien entendu une ambiguité lorsque la clé vaut 9 car alors la clé pourrait être aussi bien 0. Mais je n'ai pas trouvé de billet se terminant par 0.

Ainsi qu'on l'a vu, une telle clé ne permet pas de détecter à coup sûr une unique erreur. On peut citer divers codes pourvus eux aussi d'un seul chiffre de clé et qui eux permettent de détecter à coup sûr une unique erreur.

Exemple 1 :

Puique nous sommes dans des histoires bancaires, commençons par la règle de Luhn utilisée sur les numéros de cartes bancaires.

Un numéro de carte bancaire est de la forme

où les sont des chiffres décimaux qu'on identifiera aux nombres 0,1,...,9. Sur ces nombres on définit l'application :

avec . Ainsi si et .

On impose à un numéro de carte bancaire de vérifier (règle de Luhn) :

Le chiffre peut être considéré comme la clé, calculée en fonction des autres chiffres afin que la règle de Luhn soit vérifiée. Si un des chiffres et un seul est erroné il est facile de voir  (en utilisant le fait que m est une bijection) que la cohérence est compromise et l'erreur est détectée. C'est donc déjà mieux.
De plus si deux chiffres successifs sont permutés, on s'en aperçoit, sauf si ces deux chiffres sont 0 et 9 (il suffit pour démontrer  cela de regarder la fonction et de voir que avec x et y distincts ne peut avoir lieu que si l'un des nombres est 0 et l'autre 9).

Exemple 2 :

Le deuxième exemple est le code UPC (Universal Product Code) utilisé pour coder par exemple les produits des supermarchés.
Le code UPC utilise des nombres de 12 chiffres (11 chiffres pour désigner un produit, et une clé), de telle sorte que

soit divisible par 10.

Si un chiffre du nombre est modifié, la somme associée à A est modifiée en de telle sorte que   ou que avec .
Dans chacun de ces cas n'est pas divisible par 10 et donc n'est pas divisible par 10 ce qui permet de détecter l'erreur.

Si le chiffre est permuté avec , la somme est transformée en de telle sorte que

Donc

En dehors des cas où , n'est pas divisible par 10 donc l'erreur est détectée.

Hélas il y a là encore des cas particuliers pour lesquels une permutation de deux chiffres consécutifs n'est pas détectée.

Exemple 3 :

Donnons un autre exemple instructif, le code ISBN utilisé pour les livres.
L'International Standard Book Number utilise des mots de longueurs 10 constitués avec les chiffres  0, 1, ...,9 et le symbole X (qui représente le nombre 10) ; le symbole X ne sera utilisé, si nécessaire, que pour la clé.

    Exemples : 2 84180 013 X,  2 84225 000 1,  0 471 62187 0,  0 12 163251 2.

Le premier chiffre représente le pays, un bloc de chiffres est attribué à un éditeur, un autre bloc est le numéro donné par l'éditeur, le dernier symbole est la clé, calculée de telle sorte que si désigne un numéro I.S.B.N., soit divisible par 11.

Remarquons que . Ceci simplifie un peu le calcul de la clé.

Soit A un numéro valide. Appelons le nombre obtenu à partir des chiffres de A. On sait que est divisible par 11.
Si un chiffre de A est modifié, on obtient alors A' dont le nombre associé vérifie où , . Le nombre ia est premier avec 11, donc n'est pas divisible par 11, ce qui permet de détecter l'erreur.

Si deux chiffres distincts sont permutés, par exemples ceux d'indices i et j, le nombre devient et

où . On a et . Donc n'est pas divisible par 11 et n'est pas divisible par 11.

Cette fois-ci, contrairement aux deux premiers exemples, on a pu détecter outre une erreur sur un chiffre, toutes les permutations de deux chiffres consécutifs. Mais nous avons travaillé modulo 11 ce qui introduit une clé "parasite" X. Bien entendu on pourrait décider de supprimer tous les numéros ayant cette clé parasite. Ce n'est pas commode et fait perdre des représentations valides.

3  Toujours plus fort : la perle rare

Alors la question maintenant est de savoir si on peut faire encore mieux que dans les trois exemples précédents. Autrement dit, peut-on avoir un code avec une clé formé d'un chiffre décimal et qui permette de détecter à coup sûr une unique erreur, ou une permutation de deux chiffres consécutifs.

Notons un numéro dépendant des deux variables et où i est une position fixée (autrement dit on regarde ce qu'il se passe lorsqu'on fixe les composantes d'un numéro, sauf deux d'entre elles consécutives. La clé calculée lorsque et est notée f(u,v) (ici ). Si on veut pouvoir détecter à coup sûr un erreur sur un chiffre il est nécessaire que pour v fixée à une valeur , la fonction de u seule, soit une bijection de {0,...,9} sur lui même et aussi qu'en fixant u à la valeur la fonction soit bijective. De plus lorsque u≠v on doit avoir f(u,v)≠f(v,u). Tout ceci peut s'interpréter de la façon suivante. Construisons une matrice de taille pour laquelle les coefficients sont les f(u,v). Chaque ligne et chaque colonne doit contenir exactement un permutation des 10 chiffres décimaux. Cette matrice est un carré latin. De plus ce carré latin doit être tel que deux éléments qui sont symétriques par rapport à la diagonale principale (sans être sur cette diagonale !) sont toujours distincts. Il n'y a d'espoir d'existence d'un code vérifiant les propriétés  indiquées que si un tel carré latin existe.

Soit le groupe diédral d'ordre 10 que nous représenterons comme le groupe des isométries laissant invariant un pentagone régulier.
Notons O le centre du pentagone et les sommets écrits dans l'ordre (sens trigonométrique).
Nous numérotons les transformations de la façon suivante : 0 est l'identité, 1 est la rotation R de centre O et d'angle ,  2, 3, 4 sont respectivement les rotations . Enfin 5 ,6, 7, 8, 9 sont respectivement les symétries où désigne la symétrie par rapport à l'axe . On prend comme loi de groupe sur {0,...,9} la loi "*" donnée par la composition des transformations. Ainsi tandis que .

On introduit aussi la permutation de {0,...,9} dans lui même définie par

La matrice A  dont les coefficients vérifient est un carré latin ayant la propriété indiquée. Pour voir cela il suffit d'écrire cette matrice.

Remarque : Il est possible de montrer que si on avait pris une opération commutative alors quel que soit le choix de la permutation la matrice ayant pour coefficients ne convient pas.

Maintenant, expliquons comment calculer la clé. On calcule en fonction de de telle sorte que :

On obtient alors le code convoité.

4  Conclusion

Voilà ce qu'à peu près ils auraient pu construire ...

---

Converted by Mathematica