Formule de Luhn
Un article de Wikipédia, l'encyclopédie libre.
L'algorithme de Luhn ou la formule de Luhn, aussi connu comme l'algorithme « module 10 » ou « mod 10 », fut développé dans les années 1960 comme une méthode de validation d'identification de nombres. C'est une simple formule de vérification de somme (Checksum) utilisée pour valider une variété de numéros de comptes, comme les numéros de cartes de crédit et les numéros d'assurance sociale canadiens. Beaucoup de sa notoriété provient de son adoption par les compagnies de cartes de crédit rapidement après sa création sur la fin des années 1960 par un scientifique d'IBM Hans Peter Luhn (1896–1964).
L'algorithme fait partie du domaine public et est d'un usage large aujourd'hui. Il n'a pas été conçu pour être une fonction de hachage sécurisée cryptologiquement ; il protège contre les erreurs aléatoires, pas contre les attaques malicieuses. La plupart des cartes de crédit et beaucoup de numéros d'identification gouvernementaux utilisent l'algorithme comme une simple méthode de distinction de nombres valides dans des collections de chiffres aléatoires.
Sommaire |
[modifier] Explications informelles
La formule génère un chiffre de vérification, qui est généralement annexé à un numéro de compte partiel pour générer un numéro de compte complet. Ce numéro de compte (complet, i.e. le numéro partiel et le chiffre de vérification) est soumis à l'algorithme suivant pour vérifier sa correction :
- on démarre avec le deuxième chiffre (à droite) et on se déplace vers la gauche, en doublant la valeur de tous les chiffres de rang pair. Si le double d'un chiffre dépasse 10, on le remplace par la somme de ses chiffres. Par exemple, 1 111 devient 2 121, tandis que 8 763 devient 7 733 (car 2×6=12, et 1+2=3 ; 2×8=16, et 1+6=7).
- on additionne ensemble tous les chiffres du nombre ainsi obtenu. Par exemple, 1 111 devient 2 121, alors 2+1+2+1 ce qui nous donne 6 ; tandis que 8 763 devient 7 733, alors 7+7+3+3 ce qui nous donne 20.
- si le total finit par un 0 (dit autrement, si le total modulo 10 est 0), alors le nombre est valide, étant en accord avec la formule de Luhn, sinon il n'est pas valide. Ainsi 1 111 n'est pas valide (comme montré ci-dessus, il aboutit à 6), tandis que 8 763 est valide (comme montré ci-dessus, il aboutit à 20).
Dans les deux exemples ci-dessus, si le chiffre de vérification était additionné au début de ces nombres, alors 4 devrait être additionné à 1 111 pour faire 41 111, tandis que 0 serait ajouté à 8 763 pour faire 08 763. Généralement, les chiffres de vérification sont ajoutés à la fin, bien que ceci requiert une simple modification de l'algorithme pour déterminer un chiffre de vérification final par rapport au reste du numéro de compte donné.
[modifier] Algorithme
L'algorithme procède en trois étapes. Premièrement, un chiffre sur deux, en commançant par le deuxième jusqu'à la fin, est doublé. Si ce résultat est plus grand que neuf, ses chiffres sont additionnés (ce qui est équivalent, pour n'importe quel nombre dans l'intervalle de 10 à 18, de lui soustraire 9). Ainsi, 2 devient 4 et 7 devient 5 (=1+4). Deuxièmement, la somme de tous les chiffres est effectuée. Finalement, le résultat est divisé par 10. Si le reste est égal à zéro, le nombre original est valide.
function checkLuhn(string purportedCC) {
int sum := 0
int nDigits := length(puportedCC)
int parity := nDigits AND 1
for i from 0 to nDigits {
int digit := integer(purportedCC[i])
if (i AND 1) XOR parity ≠ 0
digit := digit × 2
if digit > 9
digit := digit - 9
sum := sum + digit
}
return (sum % 10) = 0
}
[modifier] Exemple
Considérons l'identification du nombre 456-565-654. La première étape est de doubler un chiffre sur deux en partant du deuxième jusqu'à la fin, et de faire la somme de tous les chiffres, doublés ou non. Le tableau suivant montre cette étape (les lignes colorées indiquent les chiffres doublés) :
| Chiffre | Doublé | Somme des chiffres |
|---|---|---|
| 4 | 4 | 4 |
| 5 | 10 | 1 |
| 6 | 6 | 6 |
| 5 | 10 | 1 |
| 6 | 6 | 6 |
| 5 | 10 | 1 |
| 6 | 6 | 6 |
| 5 | 10 | 1 |
| 4 | 4 | 4 |
| Sum: | 30 | |
La somme égale à 30 est divisée par 10 ; le reste est 0, donc le nombre est valide.
