Divisibilité - division euclidienne - Congruences

L'algorithme de Luhn - aussi connu comme l'algorithme « modulo 10 » - est une simple formule de somme de contrôle utilisée pour valider une variété de numéros de comptes, comme les numéros de cartes bancaires, les numéros d'assurance sociale canadiens, les numéros IMEI des téléphones mobiles ainsi que pour le calcul de validité d'un numéro SIRET.

Elle fut développée dans les années 1960 par un ingénieur allemand chez IBM, Hans Peter Luhn, comme méthode de validation d'identification de nombres. Sa notoriété provient principalement de son adoption par les compagnies de cartes de crédit peu après sa création.

L'algorithme fait partie du domaine public et est largement répandu aujourd'hui. Il n'a pas été conçu pour être sécurisé cryptologiquement : il protège contre les erreurs aléatoires, pas contre les attaques malveillantes. 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.

Source : Wikipedia^[1]

L'algorithme procède en trois étapes:

1. L'algorithme multiplie par deux un chiffre sur deux, en commençant par l'avant dernier et en se déplaçant de droite à gauche. Si le double d'un chiffre est plus grand que neuf, on additionne les chiffres composant le double.

2. On effectue la somme de tous les chiffres obtenus.

3. Si le reste de la division est égal à zéro, alors le nombre original est valide.

Exemple : somme de Luhn sur le nombre 972487086

50 est divisible par 10. le reste de la division de 50 par 10 est 0. On dit aussi que 50 modulo 10 vaut 0.

Lorsque la somme de Luhn est divisible par 10, le nombre est considéré comme valide. C'est de cette manière que l'on détecte les erreurs de saisie sur les numéros de carte bancaire ou les numéros IMEI des téléphones portables.