Luhn-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Loknummer mit Prüfsumme nach dem Luhn-Algorithmus bei der Deutschen Bahn

Der Luhn-Algorithmus oder die Luhn-Formel, auch bekannt als „Modulo 10“- oder „mod 10“-Algorithmus und als Double-Add-Double-Methode ist eine einfache Methode zur Berechnung einer Prüfsumme. Er wurde in den 1950er Jahren[1] von dem deutsch-amerikanischen Informatiker Hans Peter Luhn entwickelt und ist heute gemeinfrei und sehr weit verbreitet. Unter anderem dient der Luhn-Algorithmus der Verifizierung von Kreditkartennummern und kanadischen Sozialversicherungsnummern, ISINs und den siebenstelligen Kontonummern der Deutschen Bank und der Commerzbank sowie vieler Sparkassen. Er kommt auch bei den Nummern der Lokomotiven und Triebwagen nach dem Kennzeichnungsschema der UIC zum Einsatz, ebenso wie seit 1968 schon im Baureihenschema der Bundesbahn.

Der Luhn-Algorithmus erkennt jeden Fehler an einzelnen Ziffern, ebenso Vertauschungen von benachbarten Ziffern.

Informelle Erläuterung[Bearbeiten | Quelltext bearbeiten]

Der Luhn-Algorithmus erzeugt eine Prüfziffer, die in der Regel hinten an die unvollständige Identifikationsnummer angehängt wird. Auf diese Weise ergibt sich die vollständige Nummer. Diese wird als gültig angesehen, wenn sie den folgenden Prüf-Algorithmus besteht:

  1. Durchlaufe die Nummer ziffernweise von rechts nach links und bilde die Summe der Ziffern, aber: Verdoppele dabei jede zweite Ziffer, und wenn dabei ein Wert größer als 9 herauskommt, subtrahiere 9
  2. Wenn die Summe als letzte Ziffer eine 0 hat, erkenne die Nummer als gültig an und sonst nicht

Um beispielsweise die Nummer 18937 zu prüfen, werden die Ziffern von rechts nach links, also beginnend bei der 7, durchlaufen und aufsummiert. Jede zweite Ziffer wird dabei verdoppelt, also in diesem Beispiel die 3 und die 8. Da beim Verdoppeln der 8 ein Wert größer als 9 herauskommt, wird hiervon 9 subtrahiert, sodass sich 16 - 9 = 7 ergibt.

Somit wird die Summe berechnet als 7 + 6 + 9 + 7 + 1 = 30. Da die 30 auf 0 endet, ist die Nummer gültig.

Technisch gesehen wird eine Art Quersumme der Zahl berechnet, mit der besonderen Behandlung jeder zweiten Stelle. Das Ergebnis wird modulo 10 reduziert; dies bedeutet, dass es nicht auf das Ergebnis selbst ankommt, sondern nur auf den Rest, der bei ganzzahliger Division durch 10 herauskommt. Dieser Rest ist gleich der letzten Stelle des Ergebnisses.

Ist dieser Rest gleich 0, was gleichbedeutend damit ist, dass das Ergebnis durch 10 teilbar ist, so wird die Nummer als gültig angesehen, ansonsten nicht.

Der Luhn-Algorithmus erkennt es, wenn bei der Eingabe einer Nummer versehentlich eine Ziffer falsch eingegeben wird. Damit verändert sich die Summe um einen Betrag zwischen 1 und 9 und ist damit nicht mehr durch 10 teilbar. Wenn in obigem Beispiel statt der 1 eine 4 eingegeben wird, so ist das Ergebnis 33 und damit nicht durch 10 teilbar. Wenn statt der 8 eine 6 eingegeben wird, ist das Ergebnis 26 und damit nicht durch 10 teilbar.

Eine einzelne falsche Zifferneingabe würde auch bei einer normalen Quersummenbildung erkannt – nicht dagegen einer der häufig vorkommenden "Zahlendreher", also die Vertauschung zweier aufeinander folgenden Ziffern. Die normale Quersumme würde sich dadurch nicht ändern.

Der Luhn-Algorithmus erkennt einen solchen Zahlendreher dadurch, dass nunmehr eine andere Ziffer verdoppelt wird als vorher.

Nicht erkannt werden Vertauschungen von Ziffern, deren Positionen sich um einen geraden Betrag unterscheiden - wenn also beispielsweise die 3. und die 5. Ziffer oder die 2. und 6. Ziffer vertauscht werden. Ebenso wird möglicherweise nicht erkannt, wenn zwei oder mehr Ziffern falsch eingegeben werden.

Bei den folgenden Implementierungen des Algorithmus wird die Nummer als Zeichenfolge, also als String number an die Funktion checkLuhn übergeben. In der Funktion wird dieser String in natürlicher Weise von links nach rechts durchlaufen – also umgekehrt wie in der Definition des Algorithmus. Indem aber zu Anfang ermittelt wird, ob die Länge des Strings gerade oder ungerade ist, gelingt es trotzdem, die Ziffern an den richtigen Positionen zu verdoppeln.

Beispielimplementierungen[Bearbeiten | Quelltext bearbeiten]

Pseudo-Code[Bearbeiten | Quelltext bearbeiten]

 function checkLuhn(string number)
 {
     int sum := 0
     int lng := length(number)
     int parity := lng modulo 2
     for i from 0 to lng - 1
     {
         int digit := toInteger(number[i])
         if i modulo 2 = parity
         {
             digit := digit × 2
             if digit > 9
                 digit := digit - 9
         }
         sum := sum + digit
     }
     return (sum modulo 10) = 0
 }

C[Bearbeiten | Quelltext bearbeiten]

  #include <stdlib.h> // für atoi
  #include <string.h> // für strlen
  #include <stdbool.h> // für bool

  bool checkLuhn(const char *pPurported)
  {
    int nSum       = 0;
    int nDigits    = strlen(pPurported);
    int nParity    = (nDigits-1) % 2;
    char cDigit[2] = "\0"; // atoi erwartet einen null-terminierten String
    for (int i = nDigits; i > 0 ; i--)
    {
      cDigit[0]  = pPurported[i-1];
      int nDigit = atoi(cDigit);

      if (nParity == i % 2)
        nDigit = nDigit * 2;

      nSum += nDigit/10;
      nSum += nDigit%10;
    }
    return 0 == nSum % 10;
  }

C#[Bearbeiten | Quelltext bearbeiten]

Der Code überprüft, ob ein String nach dem Algorithmus gültig ist:

    public static bool checkLuhn(string number)
    {
        int sum = 0;
        int len = number.Length;
        for (int i = 0; i < len; i++)
        {
            int d = number[i]-'0';    // Wert der i-ten Ziffer aus ASCII-Code ermitteln
            if ((len - i) % 2 == 0)
               d = d < 5 ? d * 2 : d * 2 - 9;
            sum += d;
        }
        return sum % 10 == 0;
    }

Go[Bearbeiten | Quelltext bearbeiten]

func checkLuhn(purportedCC string) bool {
	var sum = 0
	var nDigits = len(purportedCC)
	var parity = nDigits % 2

	for i := 0; i < nDigits; i++ {
		var digit = int(purportedCC[i] - 48)
		if i%2 == parity {
			digit *= 2
			if digit > 9 {
			    digit -= 9
		    }
		}
		sum += digit
	}
	return sum%10 == 0
}

PHP[Bearbeiten | Quelltext bearbeiten]

function checkLuhn($number)
{
    $sum = 0;
    $numDigits = strlen($number)-1;
    $parity = $numDigits % 2;
    for ($i = $numDigits; $i >= 0; $i--)
    {
        $digit = substr($number, $i, 1);
        if (!$parity == ($i % 2))
            $digit <<= 1;
        $digit = ($digit > 9) ? ($digit - 9) : $digit;
        $sum += $digit;
    }
    return (0 == ($sum % 10));
}

Java[Bearbeiten | Quelltext bearbeiten]

public static boolean check(int[] digits)
{
    int sum = 0;
    int length = digits.length;
    for (int i = 0; i < length; i++)
    {
        // get digits in reverse order
        int digit = digits[length - i - 1];
        // every 2nd number multiply with 2
        if (i % 2 == 1)
            digit *= 2;
        sum += digit > 9 ? digit - 9 : digit;
    }
    return sum % 10 == 0;
}

Python[Bearbeiten | Quelltext bearbeiten]

def checkLuhn(number):
    sum = 0
    parity = len(number) % 2
    for i, digit in enumerate([int(x) for x in number]):
        if i % 2 == parity:
            digit *= 2
            if digit > 9:
                digit -= 9
        sum += digit
    return sum % 10 == 0

Oder andere Version:

def checkLuhn(number):
    return sum(map(int, number)[1-len(number)%2::2] + map(lambda x: x*2-9 if x*2>9 else x*2, map(int, number)[len(number)%2::2])) % 10 == 0

Visual Basic[Bearbeiten | Quelltext bearbeiten]

    Function checkLuhn(digits() As Integer)

        Dim sum As Int16 = 0
        Dim length As Int16 = digits.Length

        For i As Int16 = 1 To length
            Dim digit As Integer
            digit = digits(length - i)
            If i Mod 2 = 1 Then
                digit *= 2
            End If
            sum += IIf(digit > 9, digit - 9, digit)
        Next

        Return sum Mod 10 = 0


    End Function

Visual Basic 6

Function CheckLuhn(ByVal value As String) As Boolean
    Dim idx As Integer
    Dim iLength As Integer
    Dim iSum As Integer
    Dim iDigit As Integer
    Dim iAdd As Integer
    Dim bDouble As Boolean
    Dim sDigits As String
    Dim sDigit As String

    iSum = 0
    bDouble = False
    sDigits = Trim$(value)
    iLength = Len(sDigits)

    For idx = iLength To 1 Step -1

        sDigit = Mid$(sDigits, idx, 1)
        iDigit = CInt(sDigit)

        If bDouble Then iDigit = iDigit * 2

        bDouble = Not bDouble

        iAdd = IIf(iDigit > 9, iDigit - 9, iDigit)
        iSum = iSum + iAdd
    Next

    CheckLuhn = CBool(iSum Mod 10 = 0)
End Function

Haskell[Bearbeiten | Quelltext bearbeiten]

checkluhnIntegral:: Integral a => a -> Bool
checkluhnIntegral i = (lunvalIntegral i) == 0

genluhnIntegral:: Integral a => a -> a
genluhnIntegral i = (10*i) + mod (10 - lunvalIntegral (10*i)) 10

lunvalIntegral:: Integral a => a -> a
lunvalIntegral i = mod (singleNext i) 10
                   where
                     singleNext 0 = 0
                     singleNext i = (mod i 10) + doubleNext (div i 10)
                     doubleNext 0 = 0
                     doubleNext i = (luhndouble (mod i 10)) + singleNext (div i 10)

luhndouble a = dsum (2*a)
dsum a | a < 10    = a
       | otherwise = (dsum (div a 10)) + (mod a 10)

Oder andere Version:

import Data.Char
checkLuhn :: String -> Bool
checkLuhn number = sum (map2nd (\x -> if x*2>9 then x*2-9 else x*2) num) `mod` 10 == 0
    where
    map2nd f = zipWith ($) (cycle [id, f])
    num' = map Data.Char.digitToInt number
    num=if odd (length num') then num' else [0]++num'

ILE-RPG (IBM native)[Bearbeiten | Quelltext bearbeiten]

D ccInvalidChar   C                   CONST('abcdefghi…')
…
 	§nLength = %len( %trim( §cString));

        for §nI = §nLength downto 1;
          §nJ = §nJ + 1;
          §cString1 = %subst( %trim( §cString): §nI : 1);
          MONITOR;
            §nInt = %DEC( %XLATE(ccInvalidChar: '0': §cString1): 1: 0);
          ON-ERROR 105;
            §nInt = 0;
          ENDMON;

          if %rem( §nJ: 2) = 0;
             §nInt = §nInt * 2;
          endif;

          if §nInt > 9;
            §cDigit1 = %subst( %char( §nInt): 1: 1);
            MONITOR;
              §nDigit1 = %dec( §cDigit1: 1: 0);
            ON-ERROR 105;
              §nDigit1 = 0;
            ENDMON;
            §cDigit2 = %subst( %char( §nInt): 2: 1);
            MONITOR;
              §nDigit2 = %dec( §cDigit2: 1: 0);
            ON-ERROR 105;
              §nDigit2 = 0;
            ENDMON;
            §nInt = §nDigit1 + §nDigit2;
          endif;
          §nResult = §nResult + §nInt;
        endfor;

        §nChkDigit = %rem( §nResult: 10);

Beispiel[Bearbeiten | Quelltext bearbeiten]

Gegeben sei die Beispielidentifikationsnummer 446-667-651.

Ziffer Verdoppelt Reduziert Summe der Ziffern
1 1 1
5 10 10-9 1
6 6 6
7 14 14-9 5
6 6 6
6 12 12-9 3
6 6 6
4 8 8 8
4 4 4
Gesamtsumme: 40

Die Summe 40 wird ganzzahlig durch 10 dividiert; der Rest ist 0 – also ist die Nummer gültig.

Anwendung bei EC-Karten[Bearbeiten | Quelltext bearbeiten]

Bei EC-Karten unterscheidet sich die Berechnung der Nummer geringfügig. Es wird nämlich jede zweite Zahl, ausgehend von der ganz rechten (statt der zweiten von rechts) verdoppelt.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. U.S. Patent No. 2,950,048, Anmeldung eingereicht am 6. Januar 1954, Patent erteilt am 23. August 1960.

Weblinks[Bearbeiten | Quelltext bearbeiten]