Luhn-algoritmen

Från Rilpedia

Texten från svenska Wikipedia

Luhn-algoritmen, även kallad modulus-10-algoritmen eller mod-10-algoritmen, är en vanligt förekommande algoritm för att beräkna en enkel kontrollsumma som används bland annat för att beräkna kontrollsiffran i personnummer. Den används förutom i svenska personnummer även på kreditkorts-, postgiro-, bankgiro- och bankkontonummer. Den ingår också i kontrollsiffrorna för OCR-nummer (referensnummer för intebetalningskort), men där är den ibland kompletterad med en kontrollsiffra som anger entalssiffran i antalet siffror i OCR-numret. Syftet med algoritmen är att upptäcka enkla fel av typen en felskriven siffra eller ett byte av 2 intilliggande siffror. Eftersom algoritmen börjar med den minst signifikanta siffran så är det möjligt att addera ett godtyckligt antal nollor i strängens start utan att det påverkar kontrollsiffran (ex 000123 och 123 ger upphov till samma kontrollsiffra). När algoritmen uppfanns fanns det krav på en enkel algoritm för att kunna kontrollera och generera kontrollsiffror och Luhn-algoritmen uppfyller detta krav. I övrigt har idag inte algoritmen någon betydande styrka.

Algoritmen utvecklades av Hans Peter Luhn på IBM och beskrivs i US patent 2950048, med ansökningsdatum den 6 januari, 1954, och beviljandedatum den 23 augusti, 1960.

Beskrivning

Vid kontroll av siffran fungerar algoritmen på så sätt att med start från den sista siffran (den minst signifikanta siffran), det vill säga kontrollsiffran, så multipliceras siffrorna ömsom med 1 och ömsom med 2. Skulle något tal vid en sådan multiplikation bli större än 9 ersätts talet med dess siffersumma (eller, likvärdigt, med talet subtraherat med 9). Därefter summeras talen. Om den erhållna summan är jämnt delbar med 10 så är kontrollsiffran korrekt.

För att beräkna kontrollsiffran är förfarandet likvärdigt, med skillnaden att man multiplicerar ömsom med 2 och ömsom med 1 (det vill säga att man börjar att multiplicera den sista siffran med 2, och inte med 1 som i fallet vid kontroll). Den erhållna summan dras därefter ifrån närmast större 10-tal, varvid kontrollsiffran erhålles.

Exempel på personnummer 811218-9876:

   8  1 1 2 1 8  9 8  7 6
*  2  1 2 1 2 1  2 1  2 1
-------------------------
   ^  ^ ^ ^ ^ ^  ^ ^  ^ 
  16  1 2 2 2 8 18 8 14 6

Produkterna ska sedan splittras upp och adderas:

1+6+1+2+2+2+8+1+8+8+1+4+6 = 50

Denna summa är delbar med 10 och sålunda är kontrollsiffran korrekt.

Om istället kontrollsiffran eftersöks så erhålls följande summa:

1+6+1+2+2+2+8+1+8+8+1+4 = 44

Kontrollsiffran erhålls genom att detta tal subtraheras från närmast högre tiotal.

Implementationer

C

Här är en c-implementation av algoritmen som kontrollerar om kontrollsiffran är korrekt. Funktionen luhn returnerar 0 om kontrollsiffran är korrekt, och annars ett värde x. Om kontrollsiffran är felaktig, kan 10-x adderas till denna varvid en korrekt kontrollsiffra (mod 10) erhålles.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int luhn(const char *p)
{
   int m = 1;
   int sum = 0;
   int term = 0;
 
   if (strlen(p) % 2 == 0)
      m = 2;
 
   while(*p) {                  
      term = ( *p - '0' ) * m ;  
      if ( term > 9 ) term -= 9; 
      sum += term;               
      p++;                       
      m = 3 - m;
   }
 
   return sum % 10;
}
 
int main(int argc, char **argv)
{
   if (argc != 2)
      exit(1);
   printf("%d\n", luhn(argv[1]));
 
   return 0;
}

Java

Samma algoritm i java:

  class Mod10
  {
 
    public static int luhn(String indata)
    {
      int a = 1;
      int sum = 0;
      int term;
      for (int i = indata.length() - 1; i >= 0; i--) {
        term = Character.digit(indata.charAt(i),10) * a;
        if ( term > 9) term -= 9;
        sum += term;
        a = 3 - a;
      }
      return sum % 10;
    }
 
    public static void main(String[] args)
    {
      if (args.length != 1)
        System.exit(0);
      System.out.println(luhn(args[0]));
    }
  }

C#

class luhnProgram
{
    static void Main(string[] args)
    {
        if (args.Length > 0) System.Console.WriteLine(luhn(args[0]));
    }
 
    static bool luhn(string pNum)
    {
        int sum = 0;
        for (int i = 0; i < pNum.Length; i++){
            int temp = (pNum[i] - '0') * ((i % 2) == 0 ? 2 : 1);
            if (temp > 9) temp -= 9;
            sum += temp;
        }
        return (sum % 10) == 0;
    }
}

Pascal

En implementation i Pascal som en unit (använd FreePascal eller gpc - The Gnu Pascal compiler - om du vill kompilera nedanstående)

  unit luhnunit;
 
  interface
  function luhn( a : string ) : integer;
 
  implementation
 
  function luhn(a : string ):integer;
  var
    x, m, term : word;
    sum	      : integer;
  begin
    sum := 0;
    m := 1;
    for x := length(a) downto 1 do
    begin
      term := ( ord(a[x]) - ord('0') ) * m;
      if term > 9 then term := term - 9;
      sum := sum + term;
      m := 3 - m;
    end;
    luhn := (sum mod 10);
  end; { valid }
 
  begin
  end.

Javascript

Här är en variant i javascript och html. Klipp ut den, spara den och ladda den i din webläsare. Den anger även korrekt kontrollsiffra om en felaktig angivits.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<title>Luhn</title>
<script type="text/javascript">/*<![CDATA[*/
 
function checkLuhn(c)
{
	if (c.match(/[^\d]/)) return "Endast siffror är tillåtet";
	if (c.length < 2) return "Måste vara minst två siffror"; 
	var sum=0, m = 1, d;
 
	var last = c.charAt(c.length - 1) * 1;
 
	for (var i = c.length - 1; i >= 0; i--) {
		d = ( c.charCodeAt(i) & 15 ) * m;
		sum += d > 9 ? d - 9 : d;
		m = 3 - m;
	}
	if (!(sum % 10)) return "'" + c + "'" + " har en <b>KORREKT<\/b> kontrollsiffra.";
	return "'" + c + "'" + " har en <b>FELAKTIG<\/b> kontrollsiffra. Korrekt siffra är: " + ((last + 10 - sum % 10) % 10);
}
 
/*]]>*/
</script>
</head>
<body>
 
<div>
	<form method="get" action=""
		onsubmit="document.getElementById('resultat').innerHTML = checkLuhn(this.luhn.value);return false;">
		<fieldset>
			<legend>Ange det nummmer som skall kontrolleras</legend>
			<input id="luhn" type="text" />
			<input type="submit" value="Kontrollera">
		</fieldset>
		<fieldset>
			<legend>Resultat</legend>
			<div id="resultat"></div>
		</fieldset>
	</form>
</div>
 
</body>
</html>

VBA

Function Luhn(Nummer As Double, Optional Multi As Integer = 1) As Integer
    'Luhn funktionen kontrollerar eller genererar en kontrollsiffra enl. Luhn-algoritmen http://sv.wikipedia.org/wiki/Luhn-algoritmen
    'Giltiga argument är: Nummer, ett positivt heltal av Single typ (0-3E38)
    'Multiplikator 1 eller 2, bestämmer om en kontrollsiffra skall kontrolleras (1) eller genereras (2)
    'Resutlatet är ett heltal mellan 0 och 9 där 0 vid kontroll (Multi=1) indikerar en giltig kontrollsiffra
    'Vid generering (Multi=2) representerar resutatet helt enkelt kontrollsiffran
    Dim x As Integer, Text, Prod As String
    Text = Trim(Str(Nummer)) 'Gör en sträng (utan inledande blanksteg) av Numbret
    For x = Len(Text) To 1 Step -1 'Loopar från höger till vänster i strängen
        Prod = Prod & Val(Mid(Text, x, 1)) * Multi 'Lägger till produkten av varje tal och multiplikator i en sträng
        If Multi = 2 Then Multi = 1 Else Multi = 2 'Byter värde på multiplikatorn
    Next x
    For x = 1 To Len(Prod) 'Loopar igenom listan av produkter
        Luhn = Luhn + Val(Mid(Prod, x, 1)) '...och summerar dessa tal för tal
    Next x
    Luhn = 10 - Val(Right(Str(Luhn), 1))
    If Luhn = 10 Then Luhn = 0
End Function