Kryptologie/Probedivision (Primzahltest 1)

Einleitung

Beim RSA-Kryptosystem werden sehr große und zufällig gewählte Primzahlen verwendet. Da diese aus Sicherheitsgründen nach keiner Formel konstruiert werden dürfen, wählt man stattdessen eine zufällige Zahl $n\in \mathbb{N}$ der gewünschten Größe und überprüft anschließend, ob diese prim ist. Mit der Probedivision können wir eindeutig zeigen, ob es sich bei einer Zahl $n\in \mathbb{N}$ um eine Primzahl handelt.

Die Probedivision beruht auf folgendem Satz:

Satz Primteiler $p\le \sqrt{n}$

Sei $n\in \mathbb{N}$ eine zusammengesetzte Zahl, dann existiert ein Primteiler $p$ von $n$, für den gilt: $p\le \sqrt{n}$.

Beweis Satz Primteiler $p\le \sqrt{n}$

Voraussetzung

Sei $n\in \mathbb{N}$ ist zusammengesetzt

Zu zeigen

Dann existiert ein Primteiler $p$ von $n$ mit $p\le \sqrt{n}$

Beweis

Primzahl und Satz Primteiler
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.

Da $n\in \mathbb{N}$ eine zusammengesetzte Zahl sein soll, handelt es sich nach der Definition von Primzahlen nicht um eine Primzahl.

Es gibt also zwei Zahlen $a,b\in N$ mit $a>1$ und $b>1$, für die gilt: $n=a\cdot b$.

Es gilt außerdem: $a\le \sqrt{n}$ oder $b\le \sqrt{n}$.

Wären beide Zahlen größer als $\sqrt{n}$, dann wäre $a\cdot b>\sqrt{n}\cdot \sqrt{n}=n$.

Da $a$ und $b$ nach Satz Primteiler prime Teiler besitzen, teilen diese Primteiler auch $n$.

Somit besitzt $n$ einen Primteiler $p$ für den gilt: $p\le \sqrt{n}$.

Probedivision

Algorithmus der Probedivision

Sei $n\in \mathbb{N}$ ungerade (für $n<2$ gerade ist $2$ Primteiler). Ziel ist es zu ermitteln, ob $n$ prim oder zusammengesetzt ist.

1. Berechne $\sqrt{n}$
   • Ist bekannt, dass $\sqrt{n}$ prim, dann ist $n$ zusammengesetzt und die Probedivision abgeschlossen
   • Andernfalls muss der Algorithmus fortgeführt werden
2. Wähle eine Primzahl $p\le \sqrt{n}$
   • Wurde die Probedivision noch nicht auf $n$ angewandt, wähle $p=2$
   • Ist dies mindestens der zweite Durchlauf von Schritt 2 auf $n$, dann wähle die nächstgrößere Primzahl zu diesem Durchlauf
3. Ermittle, ob die Primzahl $p$ ein Teiler von $n$ ist
   • Gilt $p\mid n$, dann ist $n$ zusammengesetzt und die Probedivision abgeschlossen
   • Gilt $p\mid ̸n$, dann und es gibt ein $p\le \sqrt{n}$, welches noch nicht getestet wurde, dann wiederhole ab Schritt 2
   • Wurden alle $p\le \sqrt{n}$ durchlaufen und für all diese gilt $p\mid ̸n$, so ist $n$ prim und die Probedivision abgeschlossen

Beispiel

Tabelle 1: Primzahltabelle für die Primzahlen bis $n=21$

2
3
5
7
11
13
17
19

Mit der Probedivision testen wir, ob

$n=443$

prim ist.

Wir müssen also $n$ durch alle möglichen Primzahlen $p<21,05\approx \sqrt{443}$ teilen.

Wir lesen die Primzahlen $p<21,05$ aus einer Primzahltabelle ab (siehe Tabelle 1).

$2,3,5,7,11,13,17$ und $19$ sind alle in Frage kommende Primzahlen.

Nun muss man $443$ durch jede dieser Primzahlen nach dem Algorithmus der Probedivision einzeln dividieren.

Es gilt:

$2\nmid 443$, da $\frac{443}{2}=221,5$ und $221,5\in ̸\mathbb{Z}$.

Für die übrigen Primzahlen erfolgt die Begründung analog und es gilt:

$3\nmid 443$, $5\nmid 443$, $7\nmid 443$, $7\nmid 443$, $11\nmid 443$, $13\nmid 443$, $17\nmid 443$ und $19\nmid 443$.

Da keine der Primzahlen $p<21,05$ ein Primteiler von $n=443$ ist, muss $n$ prim sein.

Probedivision als Primzahltest

In der Praxis ist die Verwendung der Probedivision problematisch, da beispielsweise das RSA-Verschlüsselungsverfahren Primzahlen verwendet, die größer als $10^{154}$ sind. Darüber hinaus kennt man ab einer gewissen Größe der Zahl $n$ die Primzahlen $p\le \sqrt{n}$ nicht mehr und ihre Berechnung ist zu zeitintensiv, sodass man neben den Primzahlen auch einige der übrigen ungeraden Zahlen kleiner $\sqrt{n}$ (nämlich ab einer gewissen Größe) ausprobieren muss. Für eine Primzahl der Größe $10^{154}$ muss man somit mehr als $5,8\cdot 10^{71}$ Zyklen der Probedivision durchführen. In der Praxis werden daher, beispielsweise beim RSA-Verschlüsselungsalgorithmus, effizientere Verfahren verwendet.

Lernaufgabe

Aufgabe

Bestimmen Sie mittels Probedivision, ob es sich bei $n=2911$ um eine Primzahl oder eine zusammengesetzte Zahl handelt. Sie können Tabelle 2 nutzen, um die zu testenden Primzahlen zu erhalten.

Tabelle 2: Primzahlen bis $p=53$

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53

Lösung

Wir beginnen mit Schritt 1: Da $\sqrt{2911}\approx 53,95$ nicht prim, müssen wir mit Schritt 2 und 3 fortfahren. Wir testen also alle Primzahlen $p\le 53,95$, bis wir eine Primzahl finden, die $2911$ teilt: $2\mid ̸2911$, $3\mid ̸2911$, $5\mid ̸2911$, $7\mid ̸2911$, $11\mid ̸2911$, $13\mid ̸2911$, $17\mid ̸2911$, $19\mid ̸2911$, $23\mid ̸2911$, $29\mid ̸2911$, $31\mid ̸2911$, $37\mid ̸2911$, $41\mid 2911$. Da $41\mid 2911$, ist $n=2911$ zusammengesetzt.

Lernempfehlung

Kursübersicht

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