Clé de contrôle : Luhn, codes-barres, ISBN et les erreurs qu'ils ignorent

Saisissez un numéro de carte, un IMEI, un code-barres ou un ISBN, puis choisissez l'algorithme qui le vérifie. La page affiche la contribution de chaque chiffre et indique si le nombre est valide. Elle teste ensuite toutes les erreurs à une frappe près et liste celles que le chiffre de contrôle ne remarquerait pas.

Exemple résolu — Clé de contrôle : Luhn, codes-barres, ISBN et les erreurs qu'ils ignorent

Somme des contributions	60
Résultat du contrôle	0
Chiffre de contrôle attendu	7
Le nombre est-il valide ?	Oui

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Clé de contrôle : Luhn, codes-barres, ISBN et les erreurs qu'ils ignorent

Un chiffre de contrôle est un chiffre supplémentaire choisi pour que le nombre entier respecte une règle. Ici, cette règle veut que les chiffres, chacun multiplié ou transformé selon sa position, s'additionnent pour former un multiple du modulo, 10 ou 11. Une erreur qui enfreint la règle est détectée. Une erreur qui la respecte ne l'est pas. Un chiffre de contrôle peut donc prouver qu'un nombre est faux, mais ne peut jamais prouver qu'il est juste.

Ce que signifie chaque symbole

dᵢ: le chiffre à i positions en partant de la droite ; le chiffre de contrôle est d₀
wᵢ: le poids de la position i : 1 et 3 en alternance pour un code-barres, i + 1 pour l'ISBN-10
D(d): le doublement de Luhn : 2d, moins 9 lorsque le résultat dépasse 9, donnant 0 2 4 6 8 1 3 5 7 9
S: la somme des contributions de chaque chiffre
m: le modulo, 10 pour Luhn et le code-barres, 11 pour l'ISBN-10 ; le nombre est valide lorsque S est un multiple de m

Suppose: Une erreur à la fois. Deux erreurs dans un même nombre peuvent s'annuler, et les totaux de cette page n'en tiennent pas compte. L'échelle considère chaque paire de chiffres comme équiprobable, ce qui n'est pas le cas lors d'une saisie réelle. La seule paire de voisins que Luhn ignore est 09 et 90, et la fréquence à laquelle ces deux chiffres se retrouvent côte à côte dépend de la nature des nombres.
Ne tient plus quand: Un chiffre de contrôle n'est pas une mesure de sécurité. Quiconque connaît l'algorithme peut créer un nombre valide. C'est pourquoi un numéro de carte validé par Luhn signifie uniquement qu'il a été saisi correctement. L'ISBN-13 utilise l'algorithme du code-barres car un ISBN-13 est lui-même un numéro de code-barres, sous les préfixes 978 et 979 mis à disposition par GS1.

Luhn détecte toute inversion de voisins sauf une : 09 et 90 🖖

Cliquez sur 1234567890 + contrôle. Inversez le 9 et le 0 et le résultat, 12345678093, passe le contrôle. L'algorithme de Luhn double un chiffre sur deux et, lorsque le double comporte deux chiffres, il les additionne : 9 devient 18 puis 9, et 0 reste 0. Inverser deux voisins décale la somme de la différence entre ce que le doublement ajoute à chacun. Le doublement ajoute 0 à un 0, 1 à un 1, 4 à un 4, −4 à un 5, −1 à un 8 et 0 à un 9. Le 0 et le 9 sont les deux seuls chiffres traités de manière identique. C'est pourquoi la grille de gauche compte exactement deux cases rouges, 09 et 90, et l'algorithme détecte 97,8 % des inversions de voisins. Cliquez sur IMEI : il n'y a pas de 9 à côté d'un 0, et aucune de ses 13 inversions de voisins ne passe.

Aucun chiffre de contrôle basé sur l'addition modulo 10 ne détecte toutes les inversions 🖖

Cliquez sur Code-barres UPC. 2 de ses 9 inversions de voisins passent : le 3 avec le 8, et le 0 avec le 5. Un code-barres multiplie les chiffres de manière alternée par 3 et 1. Inverser a et b modifie donc la somme de 2(a − b), un multiple de 10 dès que leur écart est de cinq. Cela représente 10 des 90 paires. D'autres pondérations ne font pas mieux. Pour détecter chaque chiffre faux unique, un poids doit être congru à 1, 3, 7 ou 9 modulo 10. La différence entre deux de ces valeurs est toujours un nombre pair, et un nombre pair multiplié par 5 donne un multiple de 10. Le plafond pour toute pondération est donc de 88,9 %. Le doublement de Luhn n'est pas un poids et il atteint 97,8 %. Il ne peut pas atteindre 100 %. Gallian cite la preuve établie par H. P. Gumm en 1985 : aucun algorithme additionnant ses chiffres, peu importe comment chaque position les transforme au préalable, ne peut détecter toutes les erreurs de chiffre unique et toutes les inversions de voisins lorsque le modulo est pair. J. Verhoeff a obtenu les deux en 1969 en effectuant des multiplications dans le groupe diédral du pentagone, où l'ordre des facteurs a son importance.

Inversez deux chiffres séparés par un autre et Luhn ne le remarquera jamais 🖖

Cliquez sur IMEI. La totalité de ses 12 inversions par-dessus un chiffre passe. Les deux chiffres se trouvent à des positions de même parité. Luhn double donc les deux ou aucun, et le code-barres leur attribue le même poids. Leur inversion ne peut pas modifier la somme, et l'échelle place les deux algorithmes à 0,0 %. L'ISBN-10 donne à chaque position son propre poids, décroissant de 10 à 1. Une inversion modifie la somme par la différence des deux poids multipliée par la différence des deux chiffres. Comme 11 est un nombre premier, ce produit n'est jamais un multiple de 11. Cliquez sur ISBN-13 puis sur ISBN-10 : un seul nombre, et 9 de ces 9 inversions passent pour le premier contre 0 sur 6 pour le second. C'est une erreur rare, représentant 0,8 % des erreurs réelles selon le décompte de Verhoeff, contre 10,2 % pour les inversions de voisins. Et le modulo 11 a sa propre faille. Il utilise un symbole, X, pour le chiffre de contrôle 10. Aux positions de poids 6 et 5, dont la somme est 11, il laisse passer toutes les erreurs de chiffre double.

Problème entièrement résolu

Retrouver un chiffre effacé sur un ISBN-10 4 étapes
Un ISBN-10 indique 0-11-000?22-9, avec le septième chiffre effacé. Trouvez-le et expliquez pourquoi il existe exactement une réponse. Cliquez sur ISBN-10 pour vérifier le résultat.

Ouvrez ce problème dans l'outil
1. Les poids vont de 10 à 1 en partant de la gauche. Le septième chiffre effacé a donc un poids de 4. Additionnez les neuf autres chiffres multipliés par leur poids.
  
  $S = 10 \cdot 0 + 9 \cdot 1 + 8 \cdot 1 + 7 \cdot 0 + 6 \cdot 0 + 5 \cdot 0 + 3 \cdot 2 + 2 \cdot 2 + 1 \cdot 9 = 36$
2. La somme totale doit être un multiple de 11. Ainsi, 4 fois le chiffre manquant doit compenser la différence.
  
  $36 + 4 x \equiv 0 (mod 11) \Rightarrow 4 x \equiv - 36 \equiv 8 (mod 11)$
3. Modulo 11, vous pouvez diviser car 11 est premier : 4 × 3 = 12, soit 1 de plus que 11. Multiplier par 3 annule donc la multiplication par 4.
  
  $4 \cdot 3 = 12 \equiv 1 (mod 11) \Rightarrow x \equiv 8 \cdot 3 = 24 \equiv 2 (mod 11)$
4. Remettez le 2 en place et la somme de la page vaut 44, soit exactement quatre fois 11.
  
  $36 + 4 \cdot 2 = 44 = 4 \cdot 11$
Réponse

Le chiffre est 2, et l'ISBN est 0-11-000222-9. C'est le seul chiffre qui convient car multiplier par 4 envoie les onze valeurs de 0 à 10 vers onze restes différents modulo 11. L'une d'entre elles tombe donc exactement sur 8. C'est la même propriété qui permet à l'algorithme de détecter chaque chiffre faux à cette position, vue sous un autre angle. Un poids qui rend chaque erreur visible permet également de retrouver chaque chiffre effacé. Un algorithme modulo 10 avec un poids de 2 à cet endroit donnerait deux candidats ou aucun, et il laisserait passer chaque chiffre faux distant de cinq du bon chiffre.

$x = 2 : 0 - 11 - 000222 - 9$

Références (3)

The Luhn check digit as the IMEI standard defines it, step by step, with the worked example the page's IMEI preset reproduces (26053179311383, sum 53, check digit 7): 3GPP TS 23.003, "Numbering, addressing and identification", Annex B (normative): IMEI Check Digit computation. Published as ETSI TS 123 003 V18.7.0 (2024-09).
The ISBN-13 check digit, the 1-3 weighting that barcodes use, with the manual's own example 978-0-11-000222-4: International ISBN Agency, ISBN Users' Manual, International Edition, sixth edition. London, 2012. Appendix 1, "Check digit calculation".
ISBN-10's mod 11, the barcode's blind pairs 05, 16, 27, 38, 49 and Luhn's 09 and 90, the frequencies of real mistakes from Verhoeff's study, Gumm's theorem that no even-modulus scheme catches every swap, and Verhoeff's dihedral scheme with its tables: J. A. Gallian, "Error detection methods." ACM Computing Surveys 28(3), 1996, pp. 504-517. DOI 10.1145/243439.243457

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.