Elementare Zahlentheorie

Question

Aufgabe:

Thema Zahlentheorie "Sicherheit durch Prüfziffern". (PZN Prüfziffer)

Hier einmal zwei Fragen, wofür ich Hilfe benötige:

1. Finden Sie ein Beispiel für eine Eingabe von zwei falschen Ziffern, die durch das Prüfziffernverfahren nicht aufgedeckt wird. Zeigen Sie, dass dieser Fehler nicht erkannt wird.

2. Zeigen Sie, dass die Vertauschung zweier benachbarter Ziffern immer aufgedeckt wird.

Answer 1

Laut PZN besteht die Prüfziffer der Zahl

        \(z := \sum_{i=0}^7z_i \cdot 10^i\)

mit \(z_i ∈ \{0,\dots, 9\}\, \forall i\in \{0,\dots, 7\}\) aus der Einerstelle der Zahl

        \(p(z) := \left(\sum_{i=0}^7z_i\cdot (9-i)\right) \mod 11\).

Dabei ist die Zehnerstelle 0, weil nach den PZN-Richtlinien Zahlen \(z\) mit \(p(z)=10\) nicht als PZN vergeben werden.

Insbesondere ist \(p(11111111) = p(31011111) = 6\).

Answer 2

Ich unterstelle, Du meinst mit PZN die Pharmazentralnummer. Hier habe ich gefunden, dass die Prüfziffer \(p_z\), also die letzte Stelle der 8-stelligen PZN, wie folgt berechnet wird:$$p_z \equiv \sum_{i=1}^{7} i \cdot z_i \mod 11$$Die ersten sieben Ziffern \(z_i\) werden von links nach rechts mit \(1\) bis \(7\) multipliziert und vom Ergebnis wird nur der Rest bei der Division durch \(11\) betrachtet. Ist der Rest \(=10\), so wird diese PZN nicht vergeben.

Finden Sie ein Beispiel für eine Eingabe von zwei falschen Ziffern, die durch das Prüfziffernverfahren nicht aufgedeckt wird. Zeigen Sie, dass dieser Fehler nicht erkannt wird.

Nehme die ersten beiden Ziffern \(z_1\) und \(z_2\). Und setze sie auf (fast) beliebige Werte, z.B. \(z_1=2\) und \(z_2=2\). Ihr Anteil \(p_{1,2}\) an der Prüfziffer ist$$\begin{aligned}z_1 \cdot 1 + z_2 \cdot 2 &\equiv p_{1,2} &&\mod 11 \\ 2 \cdot 1 + 2 \cdot 2 &\equiv 6 &&\mod 11 \end{aligned}$$Jetzt gilt es, zwei andere Ziffern \(z_1'\) und \(z_2'\) zu finden, die das gleiche \(p_{1,2}=6\) erzeugen:$$\begin{aligned}z_1' \cdot 1 + z_2' \cdot 2 &\equiv 6 &&\mod 11 \\ 4 \cdot 1 + 1 \cdot 2 &\equiv 6 && \mod 11\end{aligned}$$D.h. mit \(z_1'=4\) und \(z_2'=1\) bleibt das \(p_{1,2}=6\) erhalten. Nehme z.B. die PZN $$2222222 \colorbox{#ffff00}{1} \to \sum_{i=1}^7 i\cdot 2  = 28 \cdot 2 \equiv 6 \cdot 2 \equiv \colorbox{#ffff00}{1} \mod 11$$

Jetzt ersetze die ersten beiden Ziffern wie oben berechnet

$$ 4122222 \colorbox{#ffff00}{1} \to 4\cdot 1 + 1 \cdot 2 + \sum_{i=3}^7 i \cdot 2 = 6 + 25 \cdot 2 \equiv 6 + 3 \cdot 2 \equiv \colorbox{#ffff00}{1} \mod 11$$

Die Prüfziffer bleibt erhalten.

Zeigen Sie, dass die Vertauschung zweier benachbarter Ziffern immer aufgedeckt wird.

Sei \(z_i\) die erste der beiden Ziffern, so ist der Anteil \(p_{i,i+1}\) an der Prüfziffer$$p_{i,i+1} \equiv z_i \cdot i + z_{i+1} \cdot (i+1)\mod 11$$Mit Vertauschen der Ziffern ergibt sich:$$\begin{aligned}p_{i,i+1}' &\equiv z_{i+1} \cdot i + z_{i} \cdot (i+1)\mod 11 \\ & \equiv z_{i+1} \cdot (i+1) + z_{i} \cdot i + z_i - z_{i+1}\mod 11 \\ &\equiv p_{i,i+1} + (z_i - z_{i+1}) \mod 11 \end{aligned}$$Sind die Ziffer verschieden (sonst macht es ja keinen Sinn!), dann ist die Differenz \(|z_i - z_{i+1}|\gt 0\) und sicher \(|z_i - z_{i+1}|\lt 11\). Somit ist immer gewährleistet, dass \(p_{i,i+1} \ne p_{i,i+1}'\).

Gruß Werner