24 de outubro de 2008

O Algoritmo de Luhn

O Algoritmo de Luhn foi criado por Hans Peter Luhn (1896-1964), cientista da computação que trabalhou na IBM. O objetivo deste algoritmo é criar um dígito de verificação para uma sequência de números.



O maior uso do algoritmo de Luhn é com cartões de crédito, onde as operadoras geram os n - 1 dígitos iniciais (da esquerda para a direita de quem os lê) e o enésimo digíto é calculado de acordo com os anteriores.

O método para realização do cálculo não é muito difícil:
  1. Tome uma sequência de números inteiros positivos (inclusive o dígito verificador) e a inverta.
  2. Adicione o primeiro número (dígito de verificação) ao somatório geral, que deve iniciar com zero.
  3. Multiplique o segundo número por 2 e execute a operação "noves fora", adicionando o resultado ao somatório.
  4. Repita os passos 2 e 3 até o final da sequência, ou seja, ora adicionando diretamente o número ao somatório, ora multiplicando-o por 2, realizando "noves fora" e adicionando ao somatório.
  5. Ao final, verifique se o somatório é divisível por 10. Se for, o número é válido. Senão, é inválido.

Tudo isso é muito sexy, mas até então conseguimos apenas validar um número. Como podemos gerar um dígito verificador?

Bom, para os que gostam de desafio, aí está um. Se conseguir, poste aqui a sua solução ou um link para a mesma.

Se você não está com tempo ou vontade para fazer isso, eis a minha solução (baseada em várias outras que andei lendo):
  1. Tome uma sequência de inteiros positivos e a inverta.
  2. Multiplique a primeira posição por 2 e faça os "nove fora", adicionando o resultado ao somatório, que deve iniciar com 0.
  3. Adicione a segunda posição ao somatório.
  4. Repita os passos 2 e 3, para, ora multiplicar, fazer os "nove fora" e adicionar o resultado ao somatório, ora adicionar o resultado diretamente.
  5. Se o resultado do somatório for múltiplo de 10, o dígito verificador será 0. Senão, deve-se saber quantos dígitos faltam para completar 10, então o dígito verificador será 10 - (resto da divisão do somatório por 10).

Mas por que aquelas contas no passo 5? Acontece que, como descrito no último passo do algoritmo de Luhn, um número válido deve ter o resultado do somatório igual a um múltiplo de 10. Então, se o resultado do somatório encontrado for múltiplo de 10, este não deve ser alterado. Logo, adicionamos 0. Caso contrário, precisamos fazer com que este resultado seja múltiplo de 10, então adicionamos quanto falta para chegar a 10, como forma de "completar" o número obtido. :D

Eu ia postar o código que fiz em Python, mas vou deixar de lição de casa para os leitores. Porém, para ajudar, eis uma série de números com seus respectivos dígitos verificadores, obtidos a partir da aplicação do algoritmo de Luhn. Assim cada um pode testar sua implementação:

Nota: O comprimento da sequência não importa para o algoritmo.


11111-2
12345-5
1123581321-6
98765432-4
14061970-1

Agora um bônus: este link leva a uma página do PayPal com vários números de cartão de crédito (os mesmos da tabela abaixo), para testes de validação.

Nota: Não se esqueça de ignorar o último dígito dos números, pois ele é o dígito verificador a ser calculado.



Tipo do Cartão de Crédito Número do Cartão
American Express 378282246310005
American Express 371449635398431
American Express Corporate 378734493671000
Australian BankCard 5610591081018250
Diners Club 30569309025904
Diners Club 38520000023237
Discover 6011111111111117
Discover 6011000990139424
JCB 3530111333300000
JCB 3566002020360505
MasterCard 5555555555554444
MasterCard 5105105105105100
Visa 4111111111111111
Visa 4012888888881881
Visa 4222222222222

Para completar os desafios desta postagem, há um erro proposital nela (não compromete o entendimento!). Será que alguém consegue descobrir? Comente! ;)


Leia Também

11 comentários:

  1. Fala brow.

    Pelo que pude observar o dígito verificador não entra no cálculo. Fiz um post relacionando ao seu - http://informacaocomdiversao.blogspot.com/2008/10/resposta-ao-algoritmo-de-luhn.html - dê uma verificada lá. E clube de revista na veia.
    abraço.

    ResponderExcluir
  2. Fala brother!

    Sim! O Dígito Verificador não entra no cálculo... do segundo algoritmo passado, pois neste caso, a idéia é calculá-lo. No caso do primeiro algoritmo, entra sim, já que este só vai dizer se o número é válido ou inválido.

    A dúvida ainda persiste: qual o erro nesta postagem?!
    ;)

    ResponderExcluir
  3. Fala brow!!!!

    Erro bastante implícito hein!!!!
    Olha realmente você está certo quanto ao meu comentário eu levei em consideração somente a geração do dígito e não a verificação.

    A meu ver a única coisa que pode compromenter algo são nas duas explicações a questão dos "nove fora" so vai ser executada quando for maior ou igual a dez.

    Mais sinceramente não faço idéia. Qual seria o erro?

    []

    ResponderExcluir
  4. Hahaha!

    Se eu contar, perde a graça. A questão dos nove fora é redundante, caso o número seja menor que 10, mas não creio que possa ser considerado um erro. Talvez uma má prática de programação, mas imaginei que, colocar um teste para verificar se o número é maior que 9, para só então executar os "nove fora", seria tão custoso em termos de desempenho, quanto a utilização dos "nove fora" para todos os números, sem contar que seria pior para a legibilidade do código (na minha opinião)

    O mistério ainda está no ar.
    Ninguém?!

    ResponderExcluir
  5. Eu tenho uma dúvida, mas não é sobre seu exercicio, mas de um similar.
    Eu preciso fazer um algoritomo que verifique a validade de um endereço ip.
    tem alguma idéia?

    w.pimenta@yahoo.com.br

    ResponderExcluir
  6. @walber Neste post do blog (http://pipeless.blogspot.com/2008/09/destrinchador-de-ips-em-java.html) tem uma solução para isso em Java. Contudo, se você utilizar expressões regulares, conseguirá fazer facilmente essa validação. Se não souber o que são essas expressões, procure no Google ou compre o Livro do Aurélio Jargas (se bobear, no Google você acha isso pronto).

    Abraço!

    ResponderExcluir
  7. Não é necessario inverter! Esse é o erro.

    ResponderExcluir
  8. Boa tentativa, mas ainda não é isso. Como eu escrevi, não compromete o entendimento. Não seria legal da minha parte publicar o algoritmo errado. ;)
    Vamos pra 2 anos de publicação deste texto, algumas dezenas de milhares de pageviews e ainda não acertaram... hehe

    ResponderExcluir
  9. O dígito verificador do cartão na imagem, no começo do post, está errado. Fiz as contas aqui e, se eu não fiz cagada nos cálculos, esse dígito deveria ser 8. Acertei?

    ResponderExcluir
  10. Isso aí, Leonardo!
    Quase 4 anos depois, alguém respondeu certo.
    :)

    ResponderExcluir