Primzahlen: Unterschied zwischen den Versionen

Version vom 31. März 2021, 09:27 Uhr

Definition

Sei [math] p \in \mathbb{N} [/math]. Hat p genau zwei Teiler so wird p Primzahl genannt. Wir bezeichnen [math]\mathbb P[/math] als die Menge aller Primzahlen.

Arten von Primzahlen

Primzahltupel

Jedes Paar ( p 1 , p 2 ) aus zwei Primzahlen p 1 und p 2 mit der Differenz 2 wird Primzahlzwilling genannt. Sie haben also die Form (p1,p1+2). Ein paar aus drei Primzahlen, die den Abstand von 2 haben wird hingegen als Primzahldrilling bezeichnet und hat die Form (p,p+2,p+4). Nur das Paar (3,5,7) ist ein Primzahldrilling, da unter drei aufeinanderfolgenden ungerade Zahlen stets eine durch 3 teilbar ist. Diese Definition lässt sich auf Primzahltupel erweitern, die weitere Bezeichnungen einschließt wie Primzahlvierlinge oder Primzahlcousins. Insbesondere auch die Paare mit Abstand 6 die als sexy Primzahlen bezeichent werden.

Mersennesche Primzahlen

Ist pcP und hat die Form 2^n -1 für ncN so wird p als Mersennesche Primzahl bezeichnet

Sophie-Germain Primzahlen

Gilt für eine Primzahl p, dass auch 2p+1 eine Primzahl ist, so wird p Sophie-Germain Primzahl genannt und 2p+1 sichere Primzahl

Fermat Primzahlen

Primzahlen die folgende Form haben werden Fermat PRimzahlen genannt.

Ramanujan Primzahl

Größte berechnete Primzahl

Tabelle:

Satz von Euklid

Im Jahr 300 v.u.Z hat Euklid von Alexandria bewiesen, dass es unendlich viele Primzahlen gibt.

Primzahlsatz

Hier wird die Primzählfunktion zund der Primzahlsatz vorgestellt

Die Primzahlfunktion

[math]\pi(x)[/math] ist die Primzahlfunktion. Diese ist für beliebige [math]x \in R [/math] definiert und gibt die Anzahl der Primzahlen, die nicht größer als [math]x[/math] sind wieder.

[math]\pi (x) := \left | \{p \in \mathbb{P} \mid p \le x\} \right |[/math]

Nicht vergessen, hier auch Riemannsche Vermutung zu verlinken...

Der Primzahlsatz

	erklär: beschreib
	erklär: beschreib
	erklär: beschreib

Anwendungen

Primzahlen in der Natur

Es existieren Zikadenarten, die sich in einem festen Abstand von Jahren massenhaft über der Erde vermehren und danach wieder unter die Erde zurückkehren. In dieser Zeit sind sie weniger gut vor ihren Fressfeinden geschützt. Die Zikaden haben also einen Vorteil, wenn sie in Jahren über der Erde sind, in denen weniger Fressfeinde auftreten. Einige Zikadenarten nutzen genau diesen Vorteil: Sie vermehren sich im Abstand von 13 oder 17 Jahren über der Erde.

Was passiert also mit ihren Fressfeinden? Für solche, die ohnehin in jedem Jahr auftreten, ändert sich nichts. Allerdings gibt es auch solche, die selbst nur in gewissen Jahren auftreten. Beispielsweise existiert eine zikadenjagende Wespe, die alle zwei bis drei Jahre auftritt. Nehmen wir also eine Art an, die alle 2 Jahre auftritt. Würden sich die Zikaden alle 12 Jahre vermehren, so würde in jedem dieser Jahre auch die Wespenart auftreten und die Zikaden hätten es mit deutlich mehr Fressfeinden zu tun. Nun ist der Zyklus der Zikaden aber 13 Jahre lang. Sie müssen also nur alle 26 Jahre mit jener Wespenart fertig werden. Somit haben sie einen deutlichen Vorteil darin, sich zu vermehren.

Primzahltests

Sieb des Eratosthenes

Das Sieb des Eratosthenes ist eines der ältesten Verfahren zur Bestimmung aller Primzahlen, bis hin zu einer frei wählbaren oberen Grenze. Das Verfahren ist nach dem griechischen Mathematiker Eratosthenes von Kyrene (ca. 276 v.Chr. bis ca. 194 v.Chr) benannt. Konzeptionell arbeitet das Verfahren auf Liste von Zahlen, beginnend mit der 2 bis hin zu der oberen Grenze N. Anschließend werden nacheinander alle Zahlen in dieser Liste betrachtet. Ist die betrachtete Zahl nicht markiert, so ist sie eine Primzahl und alle ihre Vielfachen können gestrichen werden. Ist die Zahl bereits markiert, kann man zur nächsten weitergehen. So werden nacheinander alle Primzahlen aus der Liste "herausgesiebt".

Ablauf des Algorithmus

Wähle eine obere Grenze N, bis zu der alle Primzahlen bestimmt werden sollen.
Schreibe alle natürlichen Zahlen von 2 bis N auf (um das Ganze anschaulicher zu machen ordnet man die Zahlen meist in einem rechteckigen Schema an, wobei hier die Vielfachen von 10 am Ender einer Reihe stehen). Im Folgenden werden alle Zahlen die keine Primzahlen sind gestrichen.
Begonnen wird mit der 2. Die 2 selbst ist eine Primzahl, es können aber alle Vielfachen von 2 gestrichen werden, da sie selbst keine Primzahlen sind.
Die nächste nicht gestrichene Zahl ist die Primzahl 3. Wieder können alle Vielfachen von 3 gestrichen werden. Begonnen werden kann hier mit der Quadratzahl von 3 (9) (warum?)
Die 4 wurde bereits im 2. Schritt gestrichen und die nächste Zahl kann betrachtet werden.
Dieses Vorgehen wird mit allen folgenden Zahlen wiederholt. Ist eine Zahl noch nicht gestrichen worden, wenn man sie betrachtet, so ist sie eine Primzahl und ihre Vielfachen können gestrichen werden. Andernfalls kann die nächste Zahl betrachtet werden.
Der Vorgang wird wiederholt, bis man bei der oberen Grenze N angelangt ist.

Der Algorithmus selbst ist recht Intuitiv und leicht nach zu vollziehen. Auch erklärt sich durch den Algorithmus, wie der Name "_Sieb_ des Eratosthenes" zu stande kommt.

Bemerkung: Spielt man den Algorithmus durch, kann man schnell erkennen, dass beim Streichen von Kandidaten, viele Zahlen mehrfach gestrichen werden. (TODO: Beispiel) Dabei handelt es sich letztlich um überflüssige Operationen.

#include <iostream>

int main(int argc, const char** argv) {
    const unsigned int N = 100;
    bool Liste[N] = { false };

    // iteriere über alle Zahlen in der Liste
    for (int i = 2; i <= N; i++) {

        // falls Index noch nicht gestrichen sind
        if (Liste[i] == false) {

            // streiche alle Vielfachen beginnend mit dem Quadrat der gegenwärtig betrachteten Zahl an der Stelle i
            for (int j = i*i; j < N; j += i) {
                Liste[j] = true;
            }
        }
    }
    
    // gebe alle Primzahlen aus
    for (int i = 2; i <= N; i++){
        if (Liste[i] == false){
            std::cout << i << std::endl;
        }
    }

    return 0;
}

Primzahlen in der Kryptographie

Die Tatsache, dass es bis heute keine effiziente Methode zum Zerlegen einer großen Zahl in ihre Primfaktoren gibt, ermöglicht einige Anwendungen in der Kryptographie. So verwenden einige Verfahren, die eine verschlüsselte Kommunikation gewährleisten, Primzahlen. Wie wichtig solche Verfahren sind, wird deutlich, wenn man sich ansieht, wobei diese benutzt werden. Das umfasst Anwendungen wie Emails, Chats und Internettelefonie, aber auch weitaus sensiblere Daten, wie beispielsweise beim Onlinebanking.

RSA-Verfahren

Das RSA-Verfahren wurde 1978 von Ron Rivest, Adi Shamir und Leonard Adleman vorgestellt und nach ihnen benannt. Es ist ein public-key Krytosystem, nutzt also ein Schlüsselpaar, das aus einem öffentlichen und einem privaten Schlüssel besteht. Dies hat den Vorteil, dass der öffentlichen Schlüssel nicht geheim weitergegeben werden muss und so der Schlüsselaustausch kein Sicherheitsrisiko darstellt.

Public-key System

Bei einem Public-key System besitzt jeder Anwender sein eigenes Schlüsselpaar aus privatem und öffentlichen Schlüssel und somit auch sein eigenes Ver- und Entschlüsselungsverfahren. Dabei wird der geheime Schlüssel vom Anwender geheimgehalten, während der öffentliche Schlüssel an alle anderen Anwender, mit denen kommuniziert wird, verteilt wird.

Der Verschlüsselungsprozess wird mit [math] D [/math] bezeichnet, der Entschlüsselungsprozess mit [math] E [/math]. Ein Schlüsselpaar besteht aus zwei Zahlen. Dabei gelten für eine Nachricht im Klartext M die folgenden Eigenschaften:

[math] D(E(M)) = M [/math]
[math] E(D(M)) = M [/math]
E und D sind für sich genommen leicht zu berechnen
E kann aus D nicht einfach berechnet werden

Ein Entschlüsselungsprozess [math] E [/math] heißt trap-door one-way function, wenn er die Eigenschaften a, c und d erfüllt. Handelt es sich außerdem um einen Prozess, der b erfüllt, so wird daraus eine trap-door one-way permutation. Dann ist jeder Geheimtext eine potenzielle Nachricht und jede Nachricht ein potenzieller Geheimtext.

Betrachten wir nun das Konzept des RSA-Verfahrens an einem Beispiel. Im Folgenden möchte Felix Ari eine Nachricht schicken. Dementsprechend besitzt Felix die Schlüsselverfahren [math] D_F [/math] und [math] E_F [/math], Ari entsprechend [math] D_A [/math] und [math] E_A [/math].

Wie sieht nun der Nachrichtenaustausch aus? Zuallererst müssen Felix und Ari ihre öffentlichen Schlüssel austauschen. Somit erhält Ari die Möglichkeit [math] E_F [/math] durchzuführen, Felix [math] E_A [/math].

Nun führt Felix auf seiner Nachricht [math] E_A [/math] aus. Er nutzt also den öffentlichen Schlüssel von Ari und versendet dann die Nachricht. Bekommt Ari nun die verschlüsselte Nachricht, so kann er sie mit [math] D_A [/math] entschlüsseln. Da nur er seinen privaten Schlüssel hat, kann auch niemand anderes die Nachricht entschlüsseln und lesen. Für die Antwort nutzt Ari dann [math] E_F [/math] für die Verschlüsselung.

Die Mathematik dahinter

Die Nachricht

Die Nachricht M selbst wird als positive ganze Zahl zwischen 0 und [math] n-1 [/math] kodiert, damit man leicht mit ihr rechnen kann. Wie groß [math] n [/math] ist, hängt vom einzelnen Schlüsselpaar ab. Ist die Nachricht zu groß, so wird sie in einzelne Blöcke aufgeteilt und jeder Block einzeln betrachtet. Eine mögliche Umwandlung von Buchstaben in Zahlen ist beispielsweise das ASCII-Format (hier Link einfügen).

Die Schlüsselpaare

Jeder der beiden Schlüssel besteht aus einem Tupel. \[ E = (e,n) \hspace{2cm} D = (d,n) \text{ wobei e, d, n positive ganze Zahlen sind.} \] Dabei gilt für den Ver- und Entschlüsselungsprozess eines Klartextes M und eines Geheimtextes C

[math] C \equiv E(M) \equiv M^e \text{ mod } n [/math]
[math] M \equiv D(C) \equiv C^d \text{ mod } n [/math]

Der Verschlüsselungsschlüssel an sich

Zwei zufällige große Primzahlen [math] und \lt math\gt q [/math] auswählen. Diese sollten in der Realität mehrere hundert Stellen haben.
- [math] n = p * q [/math]
- Weil [math] p [/math] und [math] q [/math] so groß sind, ist es nicht in realistischem Zeitaufwand möglich, aus [math] n [/math] [math] p [/math] und [math] q [/math] zu berechnen.
Eine zufällige ganze Zahl d wählen, die folgende Bedingung erfüllt
- ggT([math]d, (q-1) * (p-1)) = 1[/math]
- ggT bezeichnet dabei den größten gemeinsamen Teiler (Hier Link einfügen)
- [math]d[/math] und [math] (q-1) * (p-1)[/math] müssen also teilerfremd sein
e aus d bestimmen

\[ e * d = 1 (\text{ mod } \varphi(n)) \] (Hier Aussehen testen)

- [math] \varphi(n)[/math] bezeichnet die Eulersche [math] \varphi[/math]-Funktion (Hier Link einfügen)

Warum funktioniert das?

Signatures

Zwar schützt dieses Verfahren soweit vor fremden Mitleser, aber es ist immernoch möglich, falsche Nachrichten im Namen von Felix zu versenden. Nehmen wir an, Johanna möchte Ari im Namen von Felix eine Nachricht senden. Mit dem bisherigen Verfahren kann Johanna ebenso Aris öffentlichen Schlüssel verwenden und Ari kann sich nicht sicher sein, ob die Nachricht tatsächlich von Felix stammt oder von Johanna.

Um dieses Problem zu lösen, wird die Eigenschaft b genutzt. Einer Nachricht wird eine Signatur angehängt, die mit dem privaten Schlüssel ver- und mit dem öffentlichen Schlüssel entschlüsselt wird. Will also Felix nun Ari eine Nachricht schicken, so verschlüsselt er zuerst nur die Signatur mit seinem privaten Schlüssel, dann die ganze Nachricht mit Aris öffentlichem Schlüssel. Für die verschlüsselte Nachricht [math] C [/math] ergibt sich also

\[ C = E_A(D_F(M)) \]

Kommt die Nachricht nun bei Ari an, so entschlüsselt er zuerst die ganze Nachricht mit seinem privaten Schlüssel und dann die Signatur mit dem öffentlichen Schlüssel von Felix. Für die Entschlüsselung ergibt sich also

\[ M = D_A(E_F(C))) \]

Insgesamt ergibt sich also

\[ M = D_A(E_F(E_A(D_F(M)))) \]

Nun kann Ari anhand der Signatur erkennen, ob die Nachricht von Felix stammt, denn nur wenn der korrekte private Schlüssel verwendet wurde, ist die Signatur nun korrekt.

Team

Johanna Riedel, Felix Elser,Arianit Miftari

@@ Zeile 106: / Zeile 106: @@
 }
 </pre>
+== Primzahlen in der Kryptographie ==
+Die Tatsache, dass es bis heute keine effiziente Methode zum Zerlegen einer großen Zahl in ihre Primfaktoren gibt, ermöglicht einige Anwendungen in der Kryptographie. So verwenden einige Verfahren, die eine verschlüsselte Kommunikation gewährleisten, Primzahlen. Wie wichtig solche Verfahren sind, wird deutlich, wenn man sich ansieht, wobei diese benutzt werden. Das umfasst Anwendungen wie Emails, Chats und Internettelefonie, aber auch weitaus sensiblere Daten, wie beispielsweise beim Onlinebanking.
+=== RSA-Verfahren ===
+Das RSA-Verfahren wurde 1978 von Ron Rivest, Adi Shamir und Leonard Adleman vorgestellt und nach ihnen benannt. Es ist ein public-key Krytosystem, nutzt also ein Schlüsselpaar, das aus einem öffentlichen und einem privaten Schlüssel besteht. Dies hat den Vorteil, dass der öffentlichen Schlüssel nicht geheim weitergegeben werden muss und so der Schlüsselaustausch kein Sicherheitsrisiko darstellt.
+==== Public-key System ====
+Bei einem Public-key System besitzt jeder Anwender sein eigenes Schlüsselpaar aus privatem und öffentlichen Schlüssel und somit auch sein eigenes Ver- und Entschlüsselungsverfahren. Dabei wird der geheime Schlüssel vom Anwender geheimgehalten, während der öffentliche Schlüssel an alle anderen Anwender, mit denen kommuniziert wird, verteilt wird. <br>
+Der Verschlüsselungsprozess wird mit <math> D </math> bezeichnet, der Entschlüsselungsprozess mit <math> E </math>. Ein Schlüsselpaar besteht aus zwei Zahlen. Dabei gelten für eine Nachricht im Klartext M die folgenden Eigenschaften:
+<ol style="list-style-type:lower-alpha">
+  <li><math> D(E(M)) = M </math></li>
+  <li><math> E(D(M)) = M </math></li>
+  <li>E und D sind für sich genommen leicht zu berechnen</li>
+  <li>E kann aus D nicht einfach berechnet werden</li>
+</ol>
+Ein Entschlüsselungsprozess <math> E </math> heißt trap-door one-way function, wenn er die Eigenschaften a, c und d erfüllt. Handelt es sich außerdem um einen Prozess, der b erfüllt, so wird daraus eine trap-door one-way permutation. Dann ist jeder Geheimtext eine potenzielle Nachricht und jede Nachricht ein potenzieller Geheimtext.<br>
+Betrachten wir nun das Konzept des RSA-Verfahrens an einem Beispiel. Im Folgenden möchte Felix Ari eine Nachricht schicken. Dementsprechend besitzt Felix die Schlüsselverfahren <math> D_F </math> und <math> E_F </math>, Ari entsprechend <math> D_A </math> und <math> E_A </math>.<br>
+Wie sieht nun der Nachrichtenaustausch aus? Zuallererst müssen Felix und Ari ihre öffentlichen Schlüssel austauschen. Somit erhält Ari die Möglichkeit <math> E_F </math> durchzuführen, Felix <math> E_A </math>. <br>
+Nun führt Felix auf seiner Nachricht <math> E_A </math> aus. Er nutzt also den öffentlichen Schlüssel von Ari und versendet dann die Nachricht. Bekommt Ari nun die verschlüsselte Nachricht, so kann er sie mit <math> D_A </math> entschlüsseln. Da nur er seinen privaten Schlüssel hat, kann auch niemand anderes die Nachricht entschlüsseln und lesen. Für die Antwort nutzt Ari dann <math> E_F </math> für die Verschlüsselung.
+=== Die Mathematik dahinter ===
+==== Die Nachricht ====
+Die Nachricht M selbst wird als positive ganze Zahl zwischen 0 und <math> n-1 </math> kodiert, damit man leicht mit ihr rechnen kann. Wie groß <math> n </math> ist, hängt vom einzelnen Schlüsselpaar ab. Ist die Nachricht zu groß, so wird sie in einzelne Blöcke aufgeteilt und jeder Block einzeln betrachtet. Eine mögliche Umwandlung von Buchstaben in Zahlen ist beispielsweise das ASCII-Format (hier Link einfügen).
+==== Die Schlüsselpaare ====
+Jeder der beiden Schlüssel besteht aus einem Tupel.
+\[ E = (e,n) \hspace{2cm} D = (d,n) \text{ wobei e, d, n positive ganze Zahlen sind.} \]
+Dabei gilt für den Ver- und Entschlüsselungsprozess eines Klartextes M und eines Geheimtextes C
+* <math> C \equiv E(M) \equiv M^e \text{ mod } n </math>
+* <math> M \equiv D(C) \equiv C^d \text{ mod } n </math>
+==== Der Verschlüsselungsschlüssel an sich ====
+# Zwei zufällige große Primzahlen <math p </math> und <math> q </math> auswählen. Diese sollten in der Realität mehrere hundert Stellen haben.
+#* <math> n = p * q </math>
+#* Weil <math> p </math> und <math> q </math> so groß sind, ist es nicht in realistischem Zeitaufwand möglich, aus <math> n </math> <math> p </math> und <math> q </math> zu berechnen.
+# Eine zufällige ganze Zahl d wählen, die folgende Bedingung erfüllt
+#* ggT(<math>d, (q-1) * (p-1)) = 1</math>
+#* ggT bezeichnet dabei den größten gemeinsamen Teiler (Hier Link einfügen)
+#* <math>d</math> und <math> (q-1) * (p-1)</math> müssen also teilerfremd sein
+# e aus d bestimmen
+\[ e * d = 1 (\text{ mod } \varphi(n)) \] (Hier Aussehen testen)
+#* <math> \varphi(n)</math> bezeichnet die Eulersche <math> \varphi</math>-Funktion (Hier Link einfügen)
+==== Warum funktioniert das? ====
+=== Signatures ===
+Zwar schützt dieses Verfahren soweit vor fremden Mitleser, aber es ist immernoch möglich, falsche Nachrichten im Namen von Felix zu versenden. Nehmen wir an, Johanna möchte Ari im Namen von Felix eine Nachricht senden. Mit dem bisherigen Verfahren kann Johanna ebenso Aris öffentlichen Schlüssel verwenden und Ari kann sich nicht sicher sein, ob die Nachricht tatsächlich von Felix stammt oder von Johanna. <br>
+Um dieses Problem zu lösen, wird die Eigenschaft b genutzt. Einer Nachricht wird eine Signatur angehängt, die mit dem privaten Schlüssel ver- und mit dem öffentlichen Schlüssel entschlüsselt wird. Will also Felix nun Ari eine Nachricht schicken, so verschlüsselt er zuerst nur die Signatur mit seinem privaten Schlüssel, dann die ganze Nachricht mit Aris öffentlichem Schlüssel. Für die verschlüsselte Nachricht <math> C </math> ergibt sich also
+\[ C = E_A(D_F(M)) \]
+Kommt die Nachricht nun bei Ari an, so entschlüsselt er zuerst die ganze Nachricht mit seinem privaten Schlüssel und dann die Signatur mit dem öffentlichen Schlüssel von Felix. Für die Entschlüsselung ergibt sich also
+\[ M = D_A(E_F(C))) \]
+Insgesamt ergibt sich also
+\[ M = D_A(E_F(E_A(D_F(M)))) \]
+Nun kann Ari anhand der Signatur erkennen, ob die Nachricht von Felix stammt, denn nur wenn der korrekte private Schlüssel verwendet wurde, ist die Signatur nun korrekt.