Kryptologie/Primzahl(-eigenschaften)

Einleitung

Das asymmetrische RSA-Kryptosystem verwendet zur Schlüsselerzeugung Primzahlen. Wir beschäftigen uns daher in dieser Lerneinheiten mit der Definition und grundlegenden Eigenschaften von Primzahlen. Besonders den Fundamentalsatz der Zahlentheorie werden für den Beweis des Satz von Eulers benötigen, welcher der wichtigste Satz für die Korrektheit des RSA-Kryptosystems ist.

Primzahl

Definition Primzahl

Sei $p\in \mathbb{N}$ mit $p>1$, dann heißt $p$ Primzahl oder prime Zahl, wenn gilt:

$p$ besitzt nur zwei Teiler in $\mathbb{N}$, nämlich $1$ und $p$.

Bemerkung: Natürliche Zahlen, die größer als $1$ und keine Primzahlen sind, heißen zusammengesetzte Zahlen.

Eigenschaften

Satz Primteiler

Sei $n\in \mathbb{N}$ mit $n>1$, dann hat $n$ einen Primteiler, d.h. einen Teiler, der gleichzeitig eine Primzahl ist.

Beweis Satz Primteiler

Voraussetzung

$n\in \mathbb{N}$ mit $n>1$

Zu zeigen

$n$ hat einen Teiler, der gleichzeitig eine Primzahl ist

Beweis

Da $n>1$, besitzt $n$ mindestens einen Teiler, der größer als $1$ ist und zwar $n$.

Nun betrachten wir den kleinsten Teiler $a$ von $n$ und es gilt: $a>1$.

Diese Zahl muss eine Primzahl sein, da sie sonst wiederum durch eine weitere Zahl $b$ teilbar wäre und $b$ somit ein kleinerer Teiler von $n$ als $a$ wäre.

Dies steht im Widerspruch zu der Annahme, dass $a$ der kleinste Teiler von $n$ ist■

Satz 2 Eigenschaften von Primzahlen

Seien $p\in \mathbb{N}$ prim und $a,b\in \mathbb{Z}$ mit $p\mid ab$, dann gilt $p\mid a$ oder $p\mid b$.

Beweis Satz 2

Lemma von Euklid
Lemma von Euklid
Seien $n\in \mathbb{N}$ und $a,b\in \mathbb{Z}$ mit $n\mid ab$ und ist nun $n$ teilerfremd zu einem der Faktoren, so teilt es den anderen.

Zunächst müssen wir zwei Fälle unterscheiden: $p\mid a$ und $p\nmid a$.

Gilt $p\mid a$, dann sind wir fertig.

Wir betrachten nun den Fall $p\nmid a$.

Voraussetzung

$p\in \mathbb{N}$ prim und $a,b\in \mathbb{Z}$ mit $p\nmid a$

Zu zeigen

$p\mid b$

Beweis

Nach der Definition von Primzahlen sind $1$ und $p$ die einzigen Teiler von $p$ und es folgt $ggT(p,a)=1$ nach der Voraussetzung $p\nmid a$.

Nun nutzen wir das Lemma von Euklid und erhalten $p\mid b$■

Primfaktorzerlegung

Fundamentalsatz der Zahlentheorie

Sei $n\in \mathbb{N}$ mit $n>1$, dann ist $n$ als Produkt von Primzahlen darstellbar. Es gilt

$n=p_1\cdot p_2\cdot \dots \cdot p_i$ mit $i\in \mathbb{N}$.

Die Darstellung ist, abgesehen von der Reihenfolge der Faktoren, eindeutig und wird Primfaktorzerlegung genannt.

Beispiel Primfaktorzerlegung

Wir bestimmen die Primfaktorzerlegung von $2835$.

Es gilt offensichtlich

$5\mid 2835=567$,

$7\mid 567=81$,

$3\mid 81=27$,

$3\mid 27=9$,

$3\mid 9=3$,

und

$3\mid 3=1$.

Die Primfaktorzerlegung von $2835$ lautet: $3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 7=2835$.

Beweis

Wir müssen Existenz und Eindeutigkeit der Primfaktorzerlegung beweisen.

Voraussetzung

$n\in \mathbb{N}$ mit $n>1$

Existenz

Zu zeigen

Für jedes $n$ ist als Produkt von Primzahlen darstellbar

Beweis

Primzahl
Primzahl
Sei $p\in \mathbb{N}$ mit $p>1$, dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb{N}$, nämlich $1$ und $p$. Andernfalls heißt $p$ zusammengesetzte Zahl.

Jede Primzahl ist selbst ihre Primfaktorzerlegung. Wir müssen also noch zeigen, dass für die zusammengesetzte Zahlen eine Primfaktorzerlegung existiert.

Angenommen es gibt solche Zahlen in $\mathbb{N}$, für die keine Primfaktorzerlegung existiert. Dann gibt es unter diesen eine kleinste Zahl, welche wir $m$ nennen.

Da $m>1$ keine Primzahl ist, hat $m$ nach der Definition der Primzahl die Teiler $a,b\in \mathbb{N}$ mit $ab=m$, wobei $1<a,b<m$. Da $m$ die kleinste Zahl ist, für die keine Primfaktorzerlegung existiert, existiert für $a$ (bzw. $b$) eine Primfaktorzerlegung. Das Produkt der Primfaktorzerlegungen von $a$ und $b$ ist somit die Primfaktorzerlegung von $m$. Dies steht im Widerspruch zu unserer Annahme, dass für $m$ keine Primfaktorzerlegung existiert.

Eindeutigkeit

Zu zeigen

Die Primfaktorzerlegung von $n$ ist für jedes $n$, abgesehen von der Reihenfolge der Faktoren, eindeutig

Beweis

Analog zur Existenz, müssen wir die Eindeutigkeit für alle zusammengesetzten Zahlen zeigen, da diese sich aus der Definition von Primzahlen ergibt.

Primzahl und Lemma von Euklid
Primzahl
Sei $p\in \mathbb{N}$ mit $p>1$, dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb{N}$, nämlich $1$ und $p$. Andernfalls heißt $p$ zusammengesetzte Zahl.
Lemma von Euklid
Seien $n\in \mathbb{N}$ und $a,b\in \mathbb{Z}$ mit $n\mid ab$ und ist nun $n$ teilerfremd zu einem der Faktoren, so teilt es den anderen.

Wir nehmen also an, dass es zusammengesetzte Zahlen gibt, die mindestens zwei Primfaktorzerlegungen besitzen, die (abgesehen von der Reihenfolge) nicht identisch sind.

Unter diesen gibt es erneut eine kleinste Zahl, welche wir $n$ nennen.

Es gibt also zwei unterschiedliche Primfaktorzerlegungen von $n$:

$n=p_1\cdot ...\cdot p_i$ und $n=q_1\cdot ...\cdot q_j$ mit $i,j\in \mathbb{N}$.

Da nun aber ein beliebiger Faktor $p_1$die Zahl $n$ teilt, teilt dieser wegen $n=q_1\cdot ...\cdot q_j$ und dem Lemma von Euklid einen Faktor $q_t$ mit $t\in \{1,2,\dots ,j\}$.

Da $q_t$ jedoch eine Primzahl ist, muss gelten: $p_1=q_t$.

Wir betrachten nun die natürliche Zahl $\frac{n}{p_1}=p_2\cdot ...\cdot p_i=\frac{n}{q_t}=q_1\cdot ...\cdot qt-1\cdot q_{t+1}\cdot ...\cdot q_j$, welche kleiner ist als $n$.

Diese hat eine eindeutige Primfaktorzerlegung.

Da jedoch $p_1=q_t$ gilt, muss $n=p_1\cdot ...\cdot p_i=q_1\cdot ...\cdot q_j$ ebenfalls eindeutig sein.

Dies ist ein Widerspruch zu unserer Annahme, dass $n$ (abgesehen von der Reihenfolge) verschiedene Primfaktorzerlegungen besitzt■

Lernaufgabe

Aufgabe 1

Bestimmen Sie die Primfaktorzerlegung der Zahlen $4600$ und $63525$.

Lösung
$4600=2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 23$ $63525=3\cdot 5\cdot 5\cdot 7\cdot 11\cdot 11$

Aufgabe 2

Vervollständigen Sie den Beweis des Satzes von Euklid.

Satz von Euklid

Zu verwendende Definitionen, Sätze und Lemmata
Primzahl
Sei $p\in \mathbb{N}$ mit $p>1$, dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb{N}$, nämlich $1$ und $p$. Andernfalls heißt $p$ zusammengesetzte Zahl.
Satz Primteiler
Sei $n\in \mathbb{N}$ mit $n>1$, dann hat $n$ einen Primteiler, d.h. einen Teiler, der gleichzeitig eine Primzahl ist.
Größte gemeinsame Teiler
Seien $a,b\in \mathbb{Z}$, wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d:=ggT(a,b)$ mit $d\in \mathbb{N}$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$, falls gilt: $(1)$: $d\mid a$ und $d\mid b$ und $(2)$: Für alle $c\in \mathbb{Z}$ mit $c\mid a$ und $c\mid b\Rightarrow c\le d$.
Lemma der Teilbarkeit: $(3)$
Seien $a,b,c,d,m\in \mathbb{Z}$, dann gilt: $a\mid b$ und $a\mid c\Rightarrow a\mid (bs+ct)$ für beliebige $s,t\in \mathbb{Z}$.
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$.

Es gibt unendlich viele Primzahlen.

Beweis Satz von Euklid

Zu zeigen

Es gibt unendlich viele Primzahlen

Beweis

Wir betrachten folgende Zahlenfolge:

$n_1=2$

$n_2=n_1+1$

$n_3=n_1{n}_2+1$

$\dots$,

$n_s=n_1{n}_2\dots n_{s-1}+1$ mit $s\in \mathbb{N}$

$\dots$

Jede Zahl $n_s$ ist größer $1$.

Nun können wir _____________________ anwenden, also ist jede Zahl $n_s$ durch eine Primzahl $p$ teilbar.

Wir zeigen nun, dass ______________________, also keine zwei Zahlen einen gemeinsamen Primfaktor besitzen.

Wenn dem so wäre, dann wäre nämlich $d=ggT(n_s,n_t)=$__ mit $s<t\in \mathbb{N}$.

Angenommen $d=ggT(n_s,n_t)=$__, dann gilt $d\mid n_s$ und somit $d\mid n_1{n}_2\dots n_{t-1}$.

Da $d\mid n_t$ nach ___________________, können wir aus ________________ folgern: $d\mid n_t-n_1{n}_2\dots n_{t-1}$.

Nach Definition von $n_t$ erhalten wir $d\mid$__.

Also gilt $d=ggT(n_s,n_t)=$__.

Somit sind die Zahlen der Zahlenfolge paarweise __________ und haben keine gemeinsamen Primteiler.

Da aber nach ____________ jede Zahl der Zahlenfolge ________________, muss es unendlich viele Primzahlen geben. ■

Lösung

Wir betrachten folgende Zahlenfolge: $n_1=2$ $n_2=n_1+1$ $n_3=n_1{n}_2+1$ $\dots$, $n_s=n_1{n}_2\dots n_{s-1}+1$ mit $s\in \mathbb{N}$ $\dots$ Jede Zahl $n_s$ ist größer $1$. Nun können wir den Satz zu Primteilern anwenden, also ist jede Zahl $n_s$ durch eine Primzahl $p$ teilbar. Wir zeigen nun, dass die Zahlen der Zahlenfolge paarweise teilerfremd sind, also keine zwei Zahlen einen gemeinsamen Primfaktor besitzen. Wenn dem so wäre, dann wäre nämlich $d=ggT(n_s,n_t)=1$ mit $s<t\in \mathbb{N}$. Angenommen $d=ggT(n_s,n_t)=1$. Dann gilt $d\mid n_s$ und somit $d\mid n_1{n}_2\dots n_{t-1}$. Da $d\mid n_t$ nach Definition des größten gemeinsamen Teilers, können wir aus $(3)$ des Lemmas zur Teilbarkeit folgern: $d\mid n_t-n_1{n}_2\dots n_{t-1}$. Nach Definition von $n_t$ erhalten wir $d\mid 1$. Also gilt $d=ggT(n_s,n_t)=1$. Somit sind die Zahlen der Zahlenfolge paarweise teilerfremd und haben keine gemeinsamen Primteiler. Da aber nach dem Satz zu Primteilern jede Zahl der Zahlenfolge mindestens einen Primteiler besitzt, muss es unendlich viele Primzahlen geben. ■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens	7.1.1: Primzahl(-eigenschaften)	7.1.2: Probedivision (Primzahltest 1)