Calculateur de l'algorithme de Luhn

Introduction

L'algorithme de Luhn, également connu sous le nom d'algorithme "modulus 10" ou "mod 10", est une formule de contrôle simple utilisée pour valider une variété de numéros d'identification, tels que les numéros de carte de crédit, les numéros d'assurance sociale canadiens, les numéros IMEI et les numéros d'identifiant de fournisseur national aux États-Unis. Ce calculateur vous permet de valider des numéros en utilisant l'algorithme de Luhn et de générer des numéros valides qui passent le contrôle de Luhn.

Comment fonctionne l'algorithme de Luhn

L'algorithme de Luhn fonctionne comme suit :

En commençant par le chiffre le plus à droite (à l'exclusion du chiffre de contrôle) et en se déplaçant vers la gauche, doublez la valeur de chaque deuxième chiffre.
Si le résultat de cette opération de doublement est supérieur à 9, soustrayez 9 du résultat.
Additionnez tous les chiffres de la séquence résultante.
Si le total modulo 10 est égal à 0 (si le total se termine par zéro), alors le numéro est valide selon la formule de Luhn ; sinon, il n'est pas valide.

Voici une représentation visuelle de l'algorithme de Luhn :

Formule

L'algorithme de Luhn peut être exprimé mathématiquement comme suit :

Soit $d_i$ le $i$ -ème chiffre, en comptant à partir du chiffre le plus à droite (à l'exclusion du chiffre de contrôle) et en se déplaçant vers la gauche. Alors le chiffre de contrôle $d_0$ est choisi de sorte que :

$(2d_{2n} \bmod 9 + d_{2n-1} + 2d_{2n-2} \bmod 9 + d_{2n-3} + \cdots + 2d_2 \bmod 9 + d_1 + d_0) \bmod 10 = 0$

Où $\bmod$ est l'opération modulo.

Cas d'utilisation

L'algorithme de Luhn a diverses applications dans différents domaines :

Validation des cartes de crédit : La plupart des numéros de carte de crédit sont validés à l'aide de l'algorithme de Luhn.
Numéros d'assurance sociale canadiens : L'algorithme de Luhn est utilisé pour vérifier la validité de ces numéros d'identification.
Numéros IMEI : Les numéros IMEI des téléphones mobiles incorporent un chiffre de contrôle validé par l'algorithme de Luhn.
Numéros d'identifiant de fournisseur national (NPI) : Utilisés dans le système de santé des États-Unis, ces numéros sont validés à l'aide de l'algorithme de Luhn.
ISBN : Certains numéros ISBN-10 utilisent une variante de l'algorithme de Luhn pour la validation.

Alternatives

Bien que l'algorithme de Luhn soit largement utilisé, il existe d'autres algorithmes de contrôle pour différents objectifs :

Algorithme de Damm : Un autre algorithme de chiffre de contrôle qui détecte toutes les erreurs à un chiffre et toutes les erreurs de transposition adjacentes.
Algorithme de Verhoeff : Un algorithme de contrôle plus complexe qui attrape toutes les erreurs à un chiffre et la plupart des erreurs de transposition.
Chiffre de contrôle ISBN-13 : Utilise un algorithme différent de celui de l'ISBN-10, qui est basé sur l'algorithme de Luhn.

Histoire

L'algorithme de Luhn a été créé par Hans Peter Luhn, un informaticien d'IBM, en 1954. Luhn était un pionnier dans le domaine de l'information et est crédité de plusieurs innovations, y compris le système d'indexation KWIC (Key Word In Context).

L'algorithme a été conçu à l'origine pour protéger contre les erreurs accidentelles, et non les attaques malveillantes. Il est important de noter que bien que l'algorithme de Luhn puisse détecter de nombreuses erreurs courantes, il n'est pas une forme sécurisée de cryptage et ne doit pas être utilisé pour des objectifs de sécurité des données.

Malgré son âge, l'algorithme de Luhn reste largement utilisé en raison de sa simplicité et de son efficacité à détecter les erreurs de transcription courantes.

Exemples d'implémentation

Voici quelques exemples de code pour implémenter l'algorithme de Luhn dans divers langages de programmation :

import random

def luhn_validate(number):
    digits = [int(d) for d in str(number)]
    checksum = 0
    for i in range(len(digits) - 1, -1, -1):
        d = digits[i]
        if (len(digits) - i) % 2 == 0:
            d = d * 2
            if d > 9:
                d -= 9
        checksum += d
    return checksum % 10 == 0

def generate_valid_number(length):
    digits = [random.randint(0, 9) for _ in range(length - 1)]
    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
    check_digit = (10 - (checksum % 10)) % 10
    return int(''.join(map(str, digits + [check_digit])))

## Exemple d'utilisation :
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Génère un numéro valide de 16 chiffres

function luhnValidate(number) {
    const digits = number.toString().split('').map(Number);
    let checksum = 0;
    for (let i = digits.length - 1; i >= 0; i--) {
        let d = digits[i];
        if ((digits.length - i) % 2 === 0) {
            d *= 2;
            if (d > 9) d -= 9;
        }
        checksum += d;
    }
    return checksum % 10 === 0;
}

function generateValidNumber(length) {
    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
    const checksum = digits.reduce((sum, digit, index) => {
        if ((length - 1 - index) % 2 === 0) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }
        return sum + digit;
    }, 0);
    const checkDigit = (10 - (checksum % 10)) % 10;
    return parseInt(digits.join('') + checkDigit);
}

// Exemple d'utilisation :
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Génère un numéro valide de 16 chiffres

import java.util.Random;

public class LuhnValidator {
    public static boolean luhnValidate(long number) {
        String digits = String.valueOf(number);
        int checksum = 0;
        boolean isEven = true;
        for (int i = digits.length() - 1; i >= 0; i--) {
            int digit = Character.getNumericValue(digits.charAt(i));
            if (isEven) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
            isEven = !isEven;
        }
        return checksum % 10 == 0;
    }

    public static long generateValidNumber(int length) {
        Random random = new Random();
        long[] digits = new long[length - 1];
        for (int i = 0; i < length - 1; i++) {
            digits[i] = random.nextInt(10);
        }
        long checksum = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            long digit = digits[i];
            if ((length - 1 - i) % 2 == 0) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
        }
        long checkDigit = (10 - (checksum % 10)) % 10;
        long result = 0;
        for (long digit : digits) {
            result = result * 10 + digit;
        }
        return result * 10 + checkDigit;
    }

    public static void main(String[] args) {
        System.out.println(luhnValidate(4532015112830366L));  // true
        System.out.println(luhnValidate(4532015112830367L));  // false
        System.out.println(generateValidNumber(16));  // Génère un numéro valide de 16 chiffres
    }
}

Cas limites et considérations spéciales

Lors de l'implémentation de l'algorithme de Luhn, tenez compte des cas limites et des considérations spéciales suivantes :

Validation des entrées : Assurez-vous que l'entrée est une chaîne de chiffres valide. Les caractères non numériques doivent être traités de manière appropriée (soit supprimés, soit considérés comme une entrée invalide).
Zéros en tête : L'algorithme doit fonctionner correctement avec des numéros ayant des zéros en tête.
Grands nombres : Soyez prêt à gérer des numéros très longs qui pourraient dépasser la capacité des types d'entiers standard dans certains langages de programmation.
Entrée vide : Définissez comment votre implémentation doit traiter les chaînes vides ou les entrées nulles.
Ensembles de caractères non standard : Dans certaines applications, vous pourriez rencontrer des numéros représentés avec des caractères en dehors de la plage standard 0-9. Définissez comment ceux-ci doivent être traités.
Considérations de performance : Pour les applications qui doivent valider un grand nombre d'entrées rapidement, envisagez d'optimiser l'implémentation de l'algorithme.

Exemples numériques

Numéro de carte de crédit valide :
- Numéro : 4532015112830366
- Vérification Luhn : Valide
Numéro de carte de crédit invalide :
- Numéro : 4532015112830367
- Vérification Luhn : Invalide
Numéro d'assurance sociale canadien valide :
- Numéro : 046 454 286
- Vérification Luhn : Valide
Numéro IMEI invalide :
- Numéro : 490154203237518
- Vérification Luhn : Invalide

Cas de test

Pour vérifier l'implémentation de l'algorithme de Luhn, vous pouvez utiliser les cas de test suivants :

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Test des numéros générés
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Tous les tests ont réussi !")

test_luhn_algorithm()

Références

Luhn, H. P. (1960). "Ordinateur pour vérifier les numéros". Brevet américain 2,950,048.
Gallian, Joseph. "Les mathématiques des numéros d'identification." The College Mathematics Journal, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
"ISO/IEC 7812-1:2017". Organisation internationale de normalisation. Consulté le 2 août 2024.
Knuth, Donald. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms". Addison-Wesley, 1997.