Zahlentheoretische Grundlagen der Kryptografie

Definition:  Sei n ∈ ℕ. Die Menge ℤ_n* besteht aus allen Elementen von ℤ_n, die teilerfremd zu n sind.

ℤ_n*  =  { a ∈ ℤ_n  |  ggt(a, n) = 1 }

Behauptung:  Ein Element a ∈ ℤ_n besitzt genau dann ein multiplikativ inverses Element a^-1, wenn ggt(a, n) = 1 ist, d.h. wenn a und n teilerfremd sind.

Beweis:  

1. Wenn a und a^-1 invers zueinander sind, dann gilt a·a^-1  ≡  1 (mod n)   bzw.

   n  |  a·a^-1 – 1

   Ist d ein gemeinsamer Teiler von a und n, so folgt wegen d | n und d | a·a^-1 auch d | -1, und dies bedeutet, dass ggt(a, n) = 1 ist.

2. Gilt umgekehrt ggt(a, n) = 1, dann lässt sich nach dem Lemma von Bezout der größte gemeinsame Teiler von a und n als ganzzahlige Linearkombination von a und n darstellen:

   1  =  u·a + v·n

   Hieraus folgt unmittelbar

   1  ≡  u·a + v·n  ≡  u·a   (mod n)

   Somit ist u zu a hinsichtlich der Multiplikation modulo n invers. Damit u in die Menge ℤ_n fällt, wird es noch modulo n reduziert, sodass sich das inverse Element von a ergibt:

   a^-1  =  u mod n

Satz:  Die Menge ℤ_n* bildet mit der Multiplikation modulo n als Verknüpfung und der 1 als neutralem Element eine abelsche Gruppe, die multiplikative Gruppe modulo n.

Bemerkung:  Die multiplikative Gruppe modulo n wird auch als die Gruppe der invertierbaren Elemente von ℤ_n bezeichnet.

Eine weitere Bezeichnung ist prime Restklassengruppe modulo n, wobei "prim" hier im Sinne von "relativ prim" (engl.: relatively prime), also teilerfremd gemeint ist.

Die Menge ℤ_n bildet einen Ring mit Eins. In einem Ring mit Eins werden die multiplikativ invertierbaren Elemente auch – wenig intuitiv – als Einheiten bezeichnet. Entsprechend wird die Menge ℤ_n* auch als die Einheitengruppe des Rings ℤ_n bezeichnet.

Definition:  Mit φ(n) wird die Anzahl der Elemente von ℤ_n* bezeichnet

φ(n)  =  |ℤ_n*|

Beispiel:   

• ℤ₇*   =  { 1, 2, 3, 4, 5, 6 }
• ℤ₁₀*  =  { 1, 3, 7, 9 }
• ℤ₁₅*  =  { 1, 2, 4, 7, 8, 11, 13, 14 }
• φ(7) = 6,   φ(10) = 4,   φ(15) = 8

Satz:  Sei n ∈ ℕ, n > 1. Dann ist

φ(n)  =  n · _{p | n}  (1 – 1/p)

Hierbei durchläuft p alle Primzahlen, die Teiler von n sind, einschließlich n selber, falls n eine Primzahl ist.

Beweis:  Von den anfänglich n Zahlen 1, ..., n ist jede p-te durch die erste Primzahl p teilbar; werden diese gestrichen, verbleiben n·(1-1/p) Zahlen. Von diesen ist wiederum ein Anteil von 1/q durch die zweite Primzahl q teilbar; werden diese gestrichen, verbleiben n·(1-1/p)·(1-1/q) Zahlen usw.

Beispiel:  φ(10)   =   10 · (1 – 1/2) · (1 – 1/5)   =   10 · 1/2 · 4/5   =   4

Korollar:  Wenn n eine Primzahl ist, gilt

φ(n)  =  n-1

Korollar:  Wenn n das Produkt zweier verschiedener Primzahlen p, q ist, also n = p·q, so gilt

φ(n)  =  (p-1)(q-1)

Beispiel:  Die Gruppe ℤ₁₀* ist zyklisch, denn

ℤ₁₀*  =  ⟨3⟩  =  { 3¹, 3², 3³, 3⁴ }  =  { 3, 9, 7, 1 }

Die Gruppe ℤ₇* ist zyklisch, denn

ℤ₇*  =  ⟨5⟩  =  { 5¹, ..., 5⁶ }  =  { 5, 4, 6, 2, 3, 1 }

Die Gruppe ℤ₁₅* ist nicht zyklisch. Jedes einzelne Element von ℤ₁₅* erzeugt eine echte Untergruppe.

Satz:  Die Gruppe ℤ_n* ist genau dann zyklisch, wenn n gleich 2, 4, p^k oder 2p^k mit p Primzahl, p > 2 und k ∈ ℕ ist. Insbesondere ist ℤ_p* zyklisch, wenn p eine Primzahl ist.

Beispiel:  Das Erzeugnis von 2 in der Gruppe ℤ₇* ist

⟨2⟩  =  { 2¹, 2², 2³ }  =  { 2, 4, 1 },

also eine echte Untergruppe. Allgemein sind, sofern ℤ_n* selbst mehr als zwei Elemente enthält, stets

⟨1⟩  =  { 1 }   und

⟨n-1⟩  =  { n-1, 1 }

echte Untergruppen.

Beispiel:  Es sei p = 7. Dann ist p-1 = 2·q mit q = 3 Primzahl. Die Untergruppen von ℤ₇* ergeben sich als Erzeugnisse ⟨a⟩ der Elemente a ∈ G. Es gibt vier Untergruppen mit 1, 2, q = 3 und 2q = 6 Elementen:

U₀  =  ⟨1⟩  =  { 1 }

U₁  =  ⟨6⟩  =  { 1, 6 }

U₂  =  ⟨2⟩  =  ⟨4⟩  =  { 1, 2, 4 }

U₃  =  ⟨3⟩  =  ⟨5⟩  =  { 1, 2, 3, 4, 5, 6 }

Definition:  Eine Primzahl p heißt starke Primzahl, wenn sie von der Form

p  = 2·q + 1

mit q Primzahl ist. ¹)

Beispiel:  Die Primzahlen 5, 7, 11, 23, ... sind starke Primzahlen. Dagegen ist z.B. die Primzahl 13 keine starke Primzahl, weil 13 = 2·6 + 1 ist und 6 keine Primzahl ist.

Satz:  Sei p eine starke Primzahl und sei a ∈ {2, ..., p-2}. Dann ist a erzeugendes Element von ℤ_p* genau dann, wenn gilt

a^(p-1)/2 mod p  ≠  1

Aufgabe 1:  Das Lemma von Bezout sagt aus, dass sich der größte gemeinsame Teiler g von zwei ganzen Zahlen a und b als ganzzahlige Linearkombination von a und b darstellen lässt:

g  =  u·a + v·b

mit u, v ∈ ℤ.

Falls ggt(a, b) = 1, so gilt auch die Umkehrung. Zeigen Sie:

Seien a, b ∈ ℕ. Wenn es ganze Zahlen u, v ∈ ℤ gibt mit

1  =  u·a + v·b

dann gilt ggt(a, b) = 1.

Lösung:  

Es gelte

1  =  u·a + v·b

mit u, v ∈ ℤ. Sei d ein gemeinsamer Teiler von a und b. Dann gilt d | u·a und d | v·b und damit teilt d auch die Summe. Also gilt

d | 1

und damit folgt ggt(a, b) = 1.