imported>Kuebi: Änderungen von 91.53.153.168 (Diskussion) auf die letzte Version von Reinhard Kraasch zurückgesetzt

2025-03-19T07:27:08Z

Änderungen von 91.53.153.168 (Diskussion) auf die letzte Version von Reinhard Kraasch zurückgesetzt

Neue Seite

[[Datei:Bahn Logo.jpg|mini|Loknummer mit Prüfziffer (2) nach dem Luhn-Algorithmus bei der [[Deutsche Bahn|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 von dem deutsch-amerikanischen Informatiker [[Hans Peter Luhn]] entwickelt, zum Patent angemeldet<ref>{{Patent| Land=US| V-Nr=2950048| Code=A| Titel=Computer for verifying numbers| A-Datum=1954-06-01| V-Datum=1960-08-23| Anmelder=International Business Machines Corporation| Erfinder=Hans P. Luhn}}</ref> und ist heute [[Gemeinfreiheit|gemeinfrei]] und sehr weit verbreitet. Unter anderem dient der Luhn-Algorithmus der Verifizierung von [[Kreditkarte]]nnummern und kanadischen [[Sozialversicherungsnummer]]n, [[Internationale Wertpapierkennnummer|ISINs]] und den siebenstelligen [[Kontonummer]]n der [[Deutsche Bank|Deutschen Bank]] und der [[Commerzbank]] sowie vieler [[Sparkasse]]n. Er kommt auch bei den Nummern der Lokomotiven und Triebwagen nach dem [[UIC-Kennzeichnung der Triebfahrzeuge|Kennzeichnungsschema der UIC]] zum Einsatz, ebenso wie seit 1968 schon im [[Baureihenschema der DB|Baureihenschema der Bundesbahn]].

Der Luhn-Algorithmus erkennt jeden Fehler an einzelnen Ziffern, ebenso in den meisten Fällen Vertauschungen von benachbarten Ziffern.

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

# Durchlaufe die Nummer (mit der Prüfziffer) 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
# 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 (Prüfziffer ist hier 7), 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''' + (2 × '''3''') + '''9''' + (2 × '''8''' − 9) + '''1''' = 7 + 6 + 9 + 7 + 1 = 30. Da die 30 auf 0 endet, ist die Nummer gültig.

Technisch gesehen wird eine [[Quersumme#Gewichtete Quersumme|gewichtete 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 als vorher verdoppelt wird und sich die Quersumme ändert. Beispielsweise ist die Zahl 190 gültig (Luhn-Prüfsumme 10), 910 jedoch nicht (Luhn-Prüfsumme 11), d. h. der Zahlendreher 19 zu 91 wird erkannt. Ausgenommen sind lediglich Zahlendreher der Ziffern 0 und 9, da ihre Quersummen mit und ohne Verdopplung jeweils gleich sind. So sind beispielsweise 190 und 109 beide gültig (Luhn-Prüfsumme 10), d. h. der Zahlendreher 90 zu 09 wird nicht erkannt.

''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.

== Beispielimplementierungen ==
Bei den folgenden Implementierungen des Algorithmus wird die Nummer als Zeichenfolge, also als String <code>number</code> an die Funktion <code>checkLuhn</code> übergeben. In einigen dieser Beispiele wird dieser String von links nach rechts durchlaufen – also umgekehrt als 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.



=== Pseudo-Code ===
'''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
}

=== Java ===




<syntaxhighlight lang="java">
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;
}
</syntaxhighlight>

=== JavaScript ===
<syntaxhighlight lang="javascript">
function check(code)
{
if (Number.isNaN(code)) return '';
var len = code.length;
var parity = len % 2;
var sum = 0;
for (var i = len-1; i >= 0; i--)
{
var d = parseInt(code.charAt(i));
if (i % 2 == parity) { d *= 2 }
if (d > 9) { d -= 9 }
sum += d;
}
return (sum % 10).toString();
}
</syntaxhighlight>

=== Python ===

<syntaxhighlight lang="python">
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
</syntaxhighlight>

Oder:

<syntaxhighlight lang="python">
def checkLuhn(number):
digits = list(map(int, number))
return 0 == sum(digits + [ d + (d > 4) for d in digits[-2::-2] ]) % 10
</syntaxhighlight>

=== VB / VBA ===

<syntaxhighlight lang="vbscript">
Public Function checkLuhn(number As String) As Long

Dim StringLength As Long, parity As Long, sum As Long, i As Long, digit As Long

StringLength = Len(number)
parity = StringLength Mod 2
sum = 0

For i = StringLength To 1 Step -1
digit = CLng(Mid(number, i, 1))

If (i Mod 2) <> parity Then
digit = digit * 2
If digit > 9 Then
digit = digit - 9
End If
End If

sum = sum + digit
Next i
checkLuhn = sum Mod 10
End Function
</syntaxhighlight>

=== TSQL ===
<syntaxhighlight lang="sql">
CREATE FUNCTION FN_CheckLuhn(
@Input NVARCHAR(MAX)
)
RETURNS BIT
BEGIN
DECLARE @CurrentDigit INT;
DECLARE @Cnt INT = 0;
DECLARE @Checksum BIGINT = 0;

-- check if input is numeric, else return null
IF ISNUMERIC(@Input) = 0
RETURN NULL

WHILE @Cnt < LEN(@Input)
BEGIN
-- get next rightmost digit
SET @CurrentDigit = CAST(SUBSTRING(@Input, LEN(@Input) - @Cnt, 1) AS INT);

-- "add double" every second digit
SET @CurrentDigit = @CurrentDigit + @CurrentDigit * (@Cnt % 2);

IF @CurrentDigit > 9
SET @CurrentDigit = @CurrentDigit - 9;

SET @Checksum = @Checksum + @CurrentDigit;

SET @Cnt = @Cnt + 1;
END

RETURN IIF(@Checksum % 10 = 0, 1, 0);
END
GO
</syntaxhighlight>

== Beispiel ==
Gegeben sei die Beispielidentifikationsnummer 446-667-651.

{| class="wikitable"
! Ziffer !! Verdoppelt !! Reduziert !! Summe der Ziffern
|- align="center"
| 1 || || 1 || 1
|- align="center" style="background:#FFFFAA;"
| 5 || 10 ||10 − 9 || 1
|- align="center"
| 6 || || 6 || 6
|- align="center" style="background:#FFFFAA;"
| 7 || 14 || 14 − 9 || 5
|- align="center"
| 6 || || 6 || 6
|- align="center" style="background:#FFFFAA;"
| 6 || 12 || 12 − 9 || 3
|- align="center"
| 6 || || 6 || 6
|- align="center" style="background:#FFFFAA;"
| 4 || 8 || 8 || 8
|- align="center"
| 4 || || 4 || 4
|- align="center"
| colspan="3" | Gesamtsumme: || 40
|}

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

== Anwendung bei der Girocard (ehemals EC-Karte) ==
Bei der Girocard unterscheidet sich die Berechnung der Nummer geringfügig. Es wird nämlich jede zweite Ziffer, ausgehend von der ganz rechten (statt der zweiten von rechts) verdoppelt.

== Weblinks ==
* [https://bavister.org/tools/genLuhn.php Luhn (mod 10)-Prüfziffer-Rechner]
* [https://www.ee.unb.ca/cgi-bin/tervo/luhn.pl Luhn (mod 10)-Fehlerprüfung]
* ähnlich siehe: Check Digit Verification of [https://www.cas.org/support/documentation/chemical-substances/checkdig CAS Registry Numbers]

== Einzelnachweise ==
<references />

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Identifikationstechnik]]

Luhn-Algorithmus - Versionsgeschichte

imported>Kuebi: Änderungen von 91.53.153.168 (Diskussion) auf die letzte Version von Reinhard Kraasch zurückgesetzt