Prüfziffern: Luhn, Barcodes, ISBN & die Fehler, die sie übersehen

Tippe eine Kartennummer, eine IMEI, einen Barcode oder eine ISBN ein und wähle das passende Prüfverfahren. Die Seite zeigt, was jede Ziffer beiträgt und ob die Nummer gültig ist. Dann probiert sie jeden Fehler aus, der nur einen Tippfehler entfernt ist, und listet diejenigen auf, die der Prüfziffer entgehen würden.

Rechenbeispiel — Prüfziffern: Luhn, Barcodes, ISBN & die Fehler, die sie übersehen

Summe der Beiträge	60
Was die Prüfung liest	0
Erwartete Prüfziffer	7
Ist die Nummer gültig?	Ja

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Prüfziffern: Luhn, Barcodes, ISBN & die Fehler, die sie übersehen

Eine Prüfziffer ist eine zusätzlich gewählte Ziffer, damit die gesamte Nummer eine Regel erfüllt. In diesem Fall müssen die Ziffern, abhängig von ihrer Position multipliziert oder umgewandelt, in der Summe ein Vielfaches des Modulos ergeben, hier 10 oder 11. Ein Fehler, der diese Regel verletzt, wird erkannt. Ein Fehler, der sie einhält, bleibt unbemerkt. Daher kann eine Prüfziffer stets nur beweisen, dass eine Nummer falsch ist, aber niemals, dass sie richtig ist.

Was die einzelnen Symbole bedeuten

dᵢ: die Ziffer i Stellen von rechts; die Prüfziffer ist d₀
wᵢ: das Gewicht der Position i: abwechselnd 1 und 3 für einen Barcode, i + 1 für ISBN-10
D(d): Luhns Verdopplung: 2d, abzüglich 9, falls das Ergebnis größer als 9 ist, also 0 2 4 6 8 1 3 5 7 9
S: die Summe der Beiträge aller Ziffern
m: der Modulo, 10 für Luhn und den Barcode, 11 für ISBN-10; die Nummer ist gültig, wenn S ein Vielfaches von m ist

Setzt voraus: Immer nur ein Fehler gleichzeitig. Zwei Fehler in einer Nummer können sich gegenseitig aufheben, und die Zahlen auf dieser Seite sagen darüber nichts aus. Die Übersicht geht davon aus, dass jedes Ziffernpaar gleich wahrscheinlich ist. Beim echten Tippen ist das allerdings nicht der Fall. Das einzige blinde Ziffernpaar bei Luhn ist 09 und 90, und wie oft diese beiden direkt nebeneinander stehen, hängt stark von den Nummern ab.
Versagt, wenn: Eine Prüfziffer ist keine Sicherheitsmaßnahme. Wer das Verfahren kennt, kann problemlos eine gültige Nummer erzeugen. Deshalb ist eine Kartennummer, die die Luhn-Prüfung besteht, lediglich eine korrekt abgetippte Nummer. ISBN-13 verwendet das Barcode-Verfahren, weil eine ISBN-13 selbst eine Barcode-Nummer ist, die unter den von GS1 bereitgestellten Präfixen 978 und 979 läuft.

Luhn erkennt jeden Dreher von Nachbarn bis auf einen: 09 und 90 🖖

Klick auf 1234567890 + Prüfung. Vertausche die 9 und die 0, und das Ergebnis 12345678093 besteht den Test. Luhn verdoppelt jede zweite Ziffer und addiert die Ziffern des Ergebnisses, falls dieses zweistellig ist. Aus 9 wird 18 und dann 9, während die 0 eine 0 bleibt. Vertauscht man zwei Nachbarn, verschiebt sich die Summe um die Differenz dessen, was die Verdopplung zu jeder Ziffer hinzufügt. Die Verdopplung addiert 0 zu einer 0, 1 zu einer 1, 4 zu einer 4, −4 zu einer 5, −1 zu einer 8 und 0 zu einer 9. Die 0 und die 9 sind die einzigen beiden Ziffern, die das Verfahren gleich behandelt. Deshalb hat das linke Raster genau zwei rote Zellen, 09 und 90, und das Verfahren erkennt 97,8% der benachbarten Vertauschungen. Klick auf IMEI: Hier steht keine 9 neben einer 0, und keine der 13 benachbarten Vertauschungen geht durch.

Keine Prüfziffer aus Summen mod 10 erkennt jede Vertauschung 🖖

Klick auf UPC-Barcode. Zwei seiner neun benachbarten Vertauschungen gehen durch: die 3 mit der 8 sowie die 0 mit der 5. Ein Barcode multipliziert abwechselnde Ziffern mit 3 und 1. Vertauscht man a und b, ändert sich die Summe also um 2(a − b). Das ergibt ein Vielfaches von 10, sobald die Ziffern einen Abstand von fünf haben. Das betrifft 10 der 90 Paare. Andere Gewichtungen schneiden nicht besser ab. Um jede einzelne falsche Ziffer zu erkennen, muss ein Gewicht kongruent zu 1, 3, 7 oder 9 mod 10 sein. Je zwei davon unterscheiden sich um eine gerade Zahl, und eine gerade Zahl mal 5 ist ein Vielfaches von 10. Somit liegt die Obergrenze für jede Gewichtung bei 88,9%. Luhns Verdopplung ist keine einfache Gewichtung und erreicht 97,8%. Einen Wert von 100% kann sie nicht erzielen. Gallian zitiert H. P. Gumms Beweis von 1985: Kein Verfahren, das seine Ziffern aufaddiert, kann jede einzelne falsche Ziffer und jede benachbarte Vertauschung erkennen, wenn der Modulo gerade ist, völlig unabhängig davon, wie die Positionen die Ziffern zuvor umwandeln. J. Verhoeff erreichte 1969 beides durch Multiplikation in der Diedergruppe des Fünfecks, bei der die Reihenfolge der Faktoren eine Rolle spielt.

Vertausche zwei Ziffern über eine hinweg, und Luhn merkt es nie 🖖

Klick auf IMEI. Alle 12 Vertauschungen über eine Ziffer hinweg bestehen die Prüfung. Die beiden Ziffern stehen an Positionen gleicher Parität. Luhn verdoppelt also entweder beide oder keine von beiden, und der Barcode gibt beiden dasselbe Gewicht. Ein Vertauschen der Ziffern kann die Summe nicht verändern, und die Übersicht setzt beide Verfahren auf 0,0%. Die ISBN-10 gibt jeder Position ein eigenes Gewicht, absteigend von 10 bis 1. Eine Vertauschung ändert die Summe somit um die Differenz zweier Gewichte mal die Differenz zweier Ziffern. Da 11 eine Primzahl ist, ergibt dieses Produkt niemals ein Vielfaches von 11. Klick auf ISBN-13 und dann ISBN-10: Es ist eine einzige Nummer, und beim ersten Verfahren kommen 9 von 9 solcher Vertauschungen durch, beim zweiten 0 von 6. Es handelt sich um einen seltenen Fehler, der laut Verhoeffs Zählung 0,8% der echten Fehler ausmacht, gegenüber 10,2% bei benachbarten Vertauschungen. Und mod 11 hat seine eigene Schwachstelle: Das Verfahren verbraucht ein Zeichen, X, für die Prüfziffer 10, und an den mit 6 und 5 gewichteten Positionen, die sich zu 11 addieren, lässt es jeden Fehler bei Doppelziffern passieren.

Aufgabe vollständig gelöst

Eine unleserliche Ziffer einer ISBN-10 wiederherstellen 4 Schritte
Eine ISBN-10 lautet 0-11-000?22-9, und die siebte Ziffer ist verwischt. Finde sie heraus und erkläre, warum es genau eine Antwort gibt. Klick auf ISBN-10, um das Ergebnis zu überprüfen.

Öffne diese Aufgabe im Tool
1. Die Gewichte fallen von links von 10 auf 1 ab, also hat die verwischte siebte Ziffer das Gewicht 4. Addiere die restlichen neun Ziffern multipliziert mit ihren Gewichten.
  
  $S = 10 \cdot 0 + 9 \cdot 1 + 8 \cdot 1 + 7 \cdot 0 + 6 \cdot 0 + 5 \cdot 0 + 3 \cdot 2 + 2 \cdot 2 + 1 \cdot 9 = 36$
2. Die gesamte Summe muss ein Vielfaches von 11 sein. Die 4 mal die fehlende Ziffer muss also den Unterschied ausgleichen.
  
  $36 + 4 x \equiv 0 (mod 11) \Rightarrow 4 x \equiv - 36 \equiv 8 (mod 11)$
3. Mod 11 darfst du dividieren, da 11 eine Primzahl ist: 4 × 3 = 12 ist genau 1 mehr als 11. Daher macht die Multiplikation mit 3 die Multiplikation mit 4 rückgängig.
  
  $4 \cdot 3 = 12 \equiv 1 (mod 11) \Rightarrow x \equiv 8 \cdot 3 = 24 \equiv 2 (mod 11)$
4. Setze die 2 wieder ein, und die Summe auf der Seite ist 44, genau viermal die Elf.
  
  $36 + 4 \cdot 2 = 44 = 4 \cdot 11$
Antwort

Die Ziffer ist eine 2, und die ISBN lautet 0-11-000222-9. Es ist die einzige Ziffer, die passt. Die Multiplikation mit 4 führt die elf Werte 0 bis 10 auf elf verschiedene Reste mod 11 ab, daher landet genau einer davon bei der 8. Dies ist dieselbe Eigenschaft, die es dem Verfahren ermöglicht, jede falsche Ziffer an dieser Position zu erkennen, nur von der anderen Seite betrachtet: Ein Gewicht, das jeden einzelnen Fehler sichtbar macht, sorgt auch dafür, dass sich jeder einzelne verwischte Wert rekonstruieren lässt. Ein Verfahren mod 10 mit einem Gewicht von 2 an dieser Stelle würde zwei mögliche Kandidaten oder gar keinen liefern. Es würde zudem jede falsche Ziffer an dieser Position übersehen, die fünf von der richtigen entfernt liegt.

$x = 2 : 0 - 11 - 000222 - 9$

Quellen (3)

The Luhn check digit as the IMEI standard defines it, step by step, with the worked example the page's IMEI preset reproduces (26053179311383, sum 53, check digit 7): 3GPP TS 23.003, "Numbering, addressing and identification", Annex B (normative): IMEI Check Digit computation. Published as ETSI TS 123 003 V18.7.0 (2024-09).
The ISBN-13 check digit, the 1-3 weighting that barcodes use, with the manual's own example 978-0-11-000222-4: International ISBN Agency, ISBN Users' Manual, International Edition, sixth edition. London, 2012. Appendix 1, "Check digit calculation".
ISBN-10's mod 11, the barcode's blind pairs 05, 16, 27, 38, 49 and Luhn's 09 and 90, the frequencies of real mistakes from Verhoeff's study, Gumm's theorem that no even-modulus scheme catches every swap, and Verhoeff's dihedral scheme with its tables: J. A. Gallian, "Error detection methods." ACM Computing Surveys 28(3), 1996, pp. 504-517. DOI 10.1145/243439.243457

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.