serious-cool

Die Modulo Arithmetrik ist Grundlage aller Kryptographischer Systeme. Ein Computer kann intern nur Ganzzahlen verarbeiten. Wir machen uns diese Eigenschaft zunutze und rechen mit Ganzzahlen in Begrenzten Mengen.

Beispiel:

Wie nehmen eine Menge aus 9 Zahlen: { 0, 1, 2, 3, 4, 5 6, 7, 8 } und versuchen einige einfache Rechnungen: 2 + 4 = 6; 2 * 4 = 8. Die Ergebnisse liegen alle in unserer Menge. Wie sieht es aber bei  3*4 aus? 3*4 = 12 und 12 liegt außerhalb unserer Menge. Die Lösung: Wenn wir am ende der Menge ankommen zählen wir von Vorne weiter. 3 * 4 = 12 = 3 mod 9. 3* 4 ist äquivalent Rest 3 Modulus 9. Bei Modulus Operationen liegen alle Ergebnisse innerhalb der gewählten Menge.

Definition: Es seien a, r, m Elemente der ganzzahligen Menge mit m > 0. Dann schreiben wir a = r mod m falls m teilt ( a-r ) gilt.

Probe: 12 ?= 3 mod 9: 3-12 = -9_qed

Implikationen aus der Definition:

1. Berechnung des Restes: gegeben: a gesucht: a mod m = ? a = q *m +r mit der Vereinbarung m > 0
2. Der Rest ist nicht eindeutig: 12 = 3 mod 9 = 21 mod 9 = -6 mod 9. Die Klasse { ..., -6, 3, 12, 21, 30, ... } erfüllt die Äquivalenz. 

Wir schauen uns diese Äquivalenzklassen am Beispiel von mod 5 genauer an:

• { ..., -10, -5, 0, 5, 10, ... } A
• { ..., -9, -4, 1, 6, 11, ... } B
• { ..., -8, -3, 2, 7, 12, ... } C
• { ..., -7, -2, 3, 8, 13,... } D
• { ..., -6, -1, 4, 9, 14, ...} E

Es ergeben sich 5 Klassen die kompletten Ganzzahligen Raum für mod 5 abdecken.

Dieses Verhalten lässt sich auch auf die Multiplikation anwenden. Generell wird bei Addition und Multiplikation immer auf die gleiche Weise vorgegangen:

15 * (-4) +14 = -46 = 4 mod 5 also A*B + E

Die 0 bleibt neutrales Element 0 * 1 + 4 = 4 mod 5

Aus der Definition ergeben sich für die Exponentsation folgenden Vorgehen:

1. 3⁸ = 6561 = 937 * 7 +2 = 2 mod 7
2. 3⁸ = 3⁴⁺⁴= 3⁴ * 3⁴ = 81 * 81 = 4 * 4 mod 7 = 16 mod 7 = 2 mod 7

Ganzzahlenringe

Definition: Der Ganzzahlenring Z_m besteht aus:

1. Der Menge Z_m = {0, 1, ..., m-1 }
2. Die Operationen ,, + " , ,, * " funktionieren, a + b = c mod m; a * b = d mod m mit a, b, c, d Element von Z_m

Eigenschaften eines Rings

1. Wir können immer zwei Zahlen addieren, subtrahieren oder multiplizieren, das Ergebnis liegt immer im Ring.
2. Für einige Elemente im Ring existiert ein inverses Element, dieses ist definiert:  a * a^-1 = 1 mod m.
3. Die Inverse von a mod m existiert falls ggT(a ,m) = 1 ist. Die Inverse ist die Umkehrung der Multiplikation.
4. Es existiert ein neutrales Element bezüglich der Multiplikation  e = 1

Wie viele Elemente in Z_m sind invertierbar?

Definition: Eulerische Phi-Funktion: Phi ( m ) ist die Anzahl der Zahlen a von Z_m welche relativ prim zu m und somit invertierbar sind. Phi ( a ) = Anzahl von { a = 1, 2, 3, ..., m-1} mit ggT(a, m) = 1

Beispiel:

Phi ( 4 ) = 2 ( # { 1, 3 } )

Phi (11) = 10 ( # {1,2, ...,10} )

Für die Primzahlen P gilt immer  Phi (P ) = P -1. Dies bedeutet dass alle Zahlen außer 0 in Z_P invertierbar sind.

Formel zur Berechnung von Phi

Gegeben sei m Element von Z_m mit folgender Primfaktor Zerlegung: m = p₁^e1 * p₂^e2 * ... * p_i^ei  wobei p_i verschiedene Primzahlen sind.

Es gilt: Phi (m) = Produkt_{i = 1 bis n} ( p_i^ei - p_i^ei-1)

Diese Berechnung ist nur bei bekannter Primfaktor Zerlegung möglich. Bei großen Primzahlen wird dies zur Einwegfunktion.

Wie berechnet man a^-1 in Z_m?

kleiner Satz des Fermat:

geg: Primzahl p, a Element Z_p

Es gilt a^p-1 = 1 mod p.