Modulare "Wurzeln"

Strukturen Modulo 17 unter Multiplikation

Nimmt man für das Modul eine Primzahl, wird die Struktur praktikabel. Beispiele zur Modulo-Arithmetik: Modulo $17$ ist $13+8 = 21\equiv 4\mod 17$ oder $4-9 = -5\equiv12\mod17$ . Spannend ist auch die Multiplikation: $5\cdot4 = 20\equiv3\mod17$ und $9\cdot 2 = 18\equiv1\mod17$ . Die letzte Kongruenz besagt, dass $9$ das multiplikative Inverse von $2$ ist (Modulo $17$ ):

9\equiv \frac{1}{2} \mod 17.

(Potenzen Modulo 17 kommentiert)

Potenzen

Wir berechnen illustrativ alle Potenzen von $3$ Modulo $17$ .

Exercise 1: Potenzen von 3 Modulo 17

Vervollständige folgende Tabelle:

n	0	1	2	3	4	5	6	7
$3^n$	1	3	9	10

n	8	9	10	11	12	13	14	15
$3^n$

Solution

n	0	1	2	3	4	5	6	7
$3^n \pmod{17}$	1	3	9	10	13	5	15	11

n	8	9	10	11	12	13	14	15
$3^n \pmod{17}$	16	14	8	7	4	12	2	6

Es fällt auf, dass jede Zahl ungleich $0$ eine Potenz von $3$ ist; also jeder mögliche, nichttriviale Rest taucht genau einmal auf. Ausserdem stellt man fest:

3^{16}\equiv3\cdot6 = 18\equiv1\mod17.

Ausser $0$ sind alle Zahlen eine Potenz von $3$ und $3^{16}\equiv1\mod17$ impliziert: Jede Zahl $a\not\equiv0\mod17$ hat als $16$ -te Potenz den Wert $1$ ; denn $a$ ist eine Potenz von $3$ , also $a = 3^n$ und daher

a^{16} = (3^n)^{16} = (3^{16})^n\equiv1^n = 1\mod17

Das bedeutet, es gilt auch

a^{17} = a, a^{33} = a, a^{49} = a, \dots

und daraus erhält man

a = a^{33} = a^{3\cdot11} = (a^3)^{11}.

Note 1

Man zieht die dritte Wurzel, indem man mit $11$ potenziert.

Exercise 2: Modulo Wurzel

Ziehe durch Potenzieren die siebte Wurzel aus $a^7\mod17$ .

Solution

Es gilt für ein beliebiges Element $a\in\mathbb{Z}_{17}^\ast$ , dass $a^{16}\equiv1\mod{17}$ . Um die siebte Wurzel aus $a^7$ zu ziehen, suchen wir einen Exponenten $x$ , so dass $(a^7)^x \equiv a \mod 17$ . Das bedeutet $7x \equiv 1 \mod 16$ .

Wir erkennen, dass $x = 7$ eine Lösung ist, denn $7 \cdot 7 = 49$ . Da $49 = 3 \cdot 16 + 1$ , gilt $49 \equiv 1 \mod 16$ .

Also können wir rechnen: $(a^7)^7 = a^{49} = a^{3 \cdot 16 + 1} = (a^{16})^3 \cdot a^1 \equiv 1^3 \cdot a \equiv a \mod 17$ .

Man zieht die siebte Wurzel also, indem man mit $7$ potenziert.

Eine Idee zur Kryptogarphie

Kryptographie - eine erste Idee

Letztgenannte Beziehungen enthalten eine der Grundideen der Kryptologie basierend auf Zahlentheorie. Benutzt man die $16$ Zahlen von $1$ bis $16$ als verkürztes Alphabet, kann man eine gewählte Zahl als Verschlüsselungsexponent verwenden - beispielsweise $e = 3$ . Die Entschlüsselung erfolgt dann mittels Potenzierung mit dem entsprechenden Entschlüsselungsexponenten $d = 11$ - da $e \cdot d = 3 \cdot 11 = 33 \equiv 1 \pmod{16}$ .

Example 1

Wir wählen den Buchstaben c, der dem Wert $3$ entspricht (da a = 1, b = 2, c = 3). Mit dem Verschlüsselungsexponenten $e = 3$ verschlüsseln wir ihn: $3^3\equiv10\mod17$ . Der Chiffretext ist also $10$ , was dem Buchstaben K entspricht. Zur Entschlüsselung potenzieren wir den Chiffretext mit dem Entschlüsselungsexponenten $d = 11$ : $10^{11}\equiv3\mod17$ ; wir erhalten wieder den Klartext c.

Ein angenehmer Aspekt dieses Verfahrens ist, dass zur Ver- und Entschlüsselung dasselbe Rechenverfahren benutzt wird (Potenzierung) - und dass die Reihenfolge von Ver- und Entschlüsselung vertauscht werden kann. Dies eröffnet in der Kryptologie interessante Möglichkeiten. Wie praktisch das Verfahren ist, hängt nun davon ab, ob und wie leicht zum "Verschlüsselungsexponenten" $3$ der "Entschlüsselungsexponent" $11$ berechnet werden kann.