Algoritmo de Luhn - Luhn algorithm

O Luhn algoritmo ou fórmula Luhn , também conhecido como o " módulo de 10" ou "mod 10" algoritmo , em homenagem a seu criador, IBM cientista Hans Peter Luhn , é uma simples soma de verificação fórmula utilizada para validar uma variedade de números de identificação, tais como crédito números de cartão , números IMEI , número identificador fornecedor nacional nos Estados Unidos, do Canadá números de seguro social , israelenses números de identificação, Sul Africano números de identificação, sueco números de identificação nacional , sueco números identidade Corporativa (OrgNr), grego números de segurança social (ΑΜΚΑ), Números de cartão SIM e códigos de pesquisa que aparecem nos recibos do McDonald's , Taco Bell e Tractor Supply Co .. É descrito na Patente US No. 2.950.048, concedida em 23 de agosto de 1960.

O algoritmo é de domínio público e é amplamente utilizado hoje. É especificado na ISO / IEC 7812 -1. Não se destina a ser uma função hash criptograficamente segura ; ele foi projetado para proteger contra erros acidentais, não contra ataques maliciosos. A maioria dos cartões de crédito e muitos números de identificação do governo usam o algoritmo como um método simples de distinguir números válidos de números incorretos ou incorretos.

Descrição

O dígito de verificação é calculado da seguinte forma:

1. Pegue o número original e, começando do dígito mais à direita movendo para a esquerda, duplique o valor de cada segundo dígito (incluindo o dígito mais à direita).
2. Substitua o valor resultante em cada posição pela soma dos dígitos do valor desta posição.
3. Soma-se os valores resultantes de todas as posições ( s ).
4. O dígito de verificação calculado é igual a .${\ displaystyle 10-s \ operatorname {mod} 10}$

Exemplo para calcular o dígito de verificação

Suponha um exemplo de um número de conta "7992739871" (apenas a "carga", dígito de verificação ainda não incluído):

A soma dos dígitos resultantes é 67.

O dígito de verificação é igual a . ${\ displaystyle 10-67 \ operatorname {mod} 10 = 3}$

Isso faz com que o número completo da conta seja 79927398713.

Exemplo de validação de dígito de verificação

Basta cortar o dígito de verificação (último dígito) do número para validar. 79927398713 -> 7992739871 Calcule o dígito de verificação (veja acima) (3) e compare seu resultado com o dígito de verificação cortado (3 = 3). Se eles corresponderem ao número, passou no teste.

Forças e fraquezas

O algoritmo de Luhn detectará qualquer erro de um dígito, bem como quase todas as transposições de dígitos adjacentes. No entanto, ele não detectará a transposição da sequência de dois dígitos 09 a 90 (ou vice-versa). Ele detectará a maioria dos possíveis erros gêmeos (não detectará 22 ↔ 55 , 33 ↔ 66 ou 44 ↔ 77 ).

Outros algoritmos de dígito verificador mais complexos (como o algoritmo Verhoeff e o algoritmo Damm ) podem detectar mais erros de transcrição. O algoritmo Luhn mod N é uma extensão que oferece suporte a strings não numéricas.

Como o algoritmo opera nos dígitos de uma maneira da direita para a esquerda e os dígitos zero afetam o resultado apenas se causam mudança de posição, o preenchimento com zeros no início de uma sequência de números não afeta o cálculo. Portanto, os sistemas que preenchem com um número específico de dígitos (convertendo 1234 em 0001234, por exemplo) podem realizar a validação Luhn antes ou depois do preenchimento e obter o mesmo resultado.

O algoritmo apareceu em uma patente dos Estados Unidos para um dispositivo mecânico de mão para calcular a soma de verificação. Portanto, era necessário ser bastante simples. O dispositivo absorveu a soma do mod 10 por meios mecânicos. Os dígitos de substituição , ou seja, os resultados do procedimento duplicar e reduzir, não foram produzidos mecanicamente. Em vez disso, os dígitos foram marcados em sua ordem permutada no corpo da máquina.

Implementação de pseudocódigo

function checkLuhn(string purportedCC) {
    int nDigits := length(purportedCC)
    int sum := integer(purportedCC[nDigits-1])
    int parity := (nDigits-1) modulus 2
    for i from 0 to nDigits - 2 {
        int digit := integer(purportedCC[i])
        if i modulus 2 = parity
            digit := digit × 2
        if digit > 9
            digit := digit - 9 
        sum := sum + digit
    }
    return (sum modulus 10) = 0
}

Referências

links externos

• Implementação em 88 idiomas no projeto Rosetta Code