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^[1]. Mit der Probedivision können wir eindeutig zeigen, ob es sich bei einer Zahl $n\in \mathbb {N}$ um eine Primzahl handelt^[2].

Die Probedivision beruht auf folgendem Satz:

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

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

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

Voraussetzung

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

Zu zeigen

Dann existiert ein Primteiler $p$ von $n$ mit $p\leq {\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^[3].
Satz Primteiler
Sei $n\in \mathbb {N}$ mit $n>1$ , dann hat $n$ einen Primteiler, d.h. einen Teiler, der gleichzeitig eine Primzahl ist^[4].

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\leq {\sqrt {n}}$ oder $b\leq {\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\leq {\sqrt {n}}$ ^[2].

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.

Berechne ${\sqrt {n}}$
- Ist bekannt, dass ${\sqrt {n}}$ prim, dann ist $n$ zusammengesetzt und die Probedivision abgeschlossen
- Andernfalls muss der Algorithmus fortgeführt werden
Wähle eine Primzahl $p\leq {\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
Ermittle, ob die Primzahl $p$ ein Teiler von $n$ ist
- Gilt $p\mid n$ , dann ist $n$ zusammengesetzt und die Probedivision abgeschlossen
- Gilt $p\not \mid n$ , dann und es gibt ein $p\leq {\sqrt {n}}$ , welches noch nicht getestet wurde, dann wiederhole ab Schritt 2
- Wurden alle $p\leq {\sqrt {n}}$ durchlaufen und für all diese gilt $p\not \mid n$ , so ist $n$ prim und die Probedivision abgeschlossen^[2]

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^[5].

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\not \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^[6]. Darüber hinaus kennt man ab einer gewissen Größe der Zahl $n$ die Primzahlen $p\leq {\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^[7]. 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^[6].

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\leq 53,95$ , bis wir eine Primzahl finden, die $2911$ teilt:

$2\not \mid 2911$ , $3\not \mid 2911$ , $5\not \mid 2911$ , $7\not \mid 2911$ , $11\not \mid 2911$ , $13\not \mid 2911$ , $17\not \mid 2911$ , $19\not \mid 2911$ , $23\not \mid 2911$ , $29\not \mid 2911$ , $31\not \mid 2911$ , $37\not \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)

Literatur

↑ Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 118.
↑ ^2,0 ^2,1 ^2,2 ^2,3 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 155.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 47.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 10.
↑ Primzahlen: Tabelle der Primzahlen (2 - 100.000). (15. Oktober 2007). Wikibooks, Die freie Bibliothek. Abgerufen am 20. Dezember 2019, 14:22 von https://de.wikibooks.org/w/index.php?title=Primzahlen:_Tabelle_der_Primzahlen_(2_-_100.000)&oldid=327631.
↑ ^6,0 ^6,1 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 156f.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 384.

[1] Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 118.

[:2-2] 2,0 ^2,1 ^2,2 ^2,3 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 155.

[:1222-3] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 47.

[:26-4] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 10.

[:3-5] Primzahlen: Tabelle der Primzahlen (2 - 100.000). (15. Oktober 2007). Wikibooks, Die freie Bibliothek. Abgerufen am 20. Dezember 2019, 14:22 von https://de.wikibooks.org/w/index.php?title=Primzahlen:_Tabelle_der_Primzahlen_(2_-_100.000)&oldid=327631.

[:022-6] 6,0 ^6,1 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 156f.

[7] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 384.

[1]

[2]

[3]

[4]

[5]

[6]

[7]