Primzahltests

Zwischen Wissenschaft und Schule


Bachelorarbeit, 2011
41 Seiten, Note: 1,1

Leseprobe

Inhaltsverzeichnis

1 Einleitung
1.1 Definition
1.2 Kryptologie
1.2.1 RSA-Verfahren

2 Primzahltests
2.1 Probedivision
2.2 Siebmethoden
2.2.1 SIEB DES ERATOSTHENES
2.2.2 SIEB VON ATKIN
2.2.3 Weitere Siebmethoden
2.3 Probabilistische Primzahltests
2.3.1 FERMAT-Test
2.3.2 SOLOVAY-STRASSEN-Test
2.3.3 MILLER-RABIN-Test
2.4 Primzahltests beruhend auf dem kleinen Satz von FERMAT
2.4.1 LUCAS-Test
2.4.2 PÉPIN-Test
2.4.3 LUCAS-LEHMER-Test
2.5 AKS-Methode
2.5.1 Ausgangspunkt der AKS-Methode
2.5.2 Die Grundstruktur des AKS-Algorithmus
2.5.3 Der AKS-Algorithmus

3 Anwendung in der Schule
3.1 Lehrplananalyse
3.2 Das SIEB DES ERATOSTHENES in der Schule
3.3 Potenziale anderer Primzahltests

4 Schluss

1 Einleitung

In der vorliegenden Bachelorarbeit soll das große Spektrum der Primzahltests näher un- tersucht werden. Ziel soll es sein, ausgehend von ersten und einfachen Erkenntnissen, was die Definition von Primzahlen und allererste Ergebnisse auf diesem Gebiet umfasst, im- mer weiter vorzudringen. Schlussendlich soll ein verständlicher Weg aufgezeichnet sein, wie sich die Entwicklung von Primzahltest in unserer Gesellschaft immer weiter vollzo- gen hat. Zum Abschluss dieses Abschnittes wird der neueste Primzahltest, der im Jahre 2002 entdeckt wurde, stehen. Die AKS-Methode und der Algorithmus, den sie beinhal- tet unterscheiden sich von den meisten bisherigen Tests mit Praxisbedeutung in seiner Determiniertheit. Diesen neuesten wissenschaftlichen Erkenntnissen auf dem Gebiet des Primalitätsproblems werde ich einen größeren Anteil meiner Arbeit widmen. Trotz allem nutzt der AKS-Algorithmus die Erkenntnisse seiner Vorläufer. So soll auch die Arbeit gestaltet sein, welche einen Überblick über die verschiedenen Tests und ihre Anwendung geben soll. Dabei werde ich mich vor allem auf das Buch “PRIMZAHLTESTS FÜR EIN- STEIGER” von LASSE REMPE & REBECCA WALDECKER ([RW09]) stützen.

In Bezug auf die Anwendbarkeit von Primzahltests in der Schule eignen sich meiner An- sicht nach die Siebmethoden für eine nähere Betrachtung. Der didaktische Bezug und die Anwendung in der Schule, insbesondere der Frage inwieweit Primzahlen in der gymnasia- len Oberstufe eine Rolle spielen, sollen den letzten Teil dieser Arbeit darstellen. Hierbei soll noch einmal aufgegriffen werden, inwieweit Primzahlen und die Bestimmung einer Zahl als Primzahl Anwendung in der Schule finden, und an welchen Stellen sich eine sinnvolle didaktische Eingliederung anbietet. Auch welche anderen Tests sich aus meiner Sicht besonders für eine verständliche Betrachtung in der Schule eignen, soll dabei noch einmal eine Rolle spielen.

In der gesamten Arbeit wird die Effizienz und Alltagsrelevanz der verschiedenen Prim- zahltests immer wieder betrachtet. Die Bewertungen werden sich aus eigenen Reflexionen und wissenschaftlichen Meinungen ergeben. Um die Notwendigkeit von Primzahltests und somit den Sinn dieser Arbeit, wird es sich in dem ersten Teil drehen. In diesem wer- de ich allgemein die heute bedeutendste Anwendung der Primzahlen, genau benannt in der Kryptologie, kurz vorstellen. Hierbei gehe ich noch einmal gesondert auf das RSA- Verfahren ein, welches auch meinen ersten Berührungspunkt mit der Kryptologie dar- stellt.

1.1 Definition

Um in das Thema der Primzahltests eindringen zu können, muss zu erst einmal geklärt werden, was eine Primzahl ist. Umgangssprachlich ist eine Primzahl, eine Zahl die nur durch 1 und sich selbst teilbar ist. Mathematisch ausgedrückt erhält man:

p ∈ N heißt Primzahl, wenn p > 1 und p nur die trivialen Teiler ± 1und ± p besitzt.” (Wolfahrt 2011[Wol11], S.6)

Alle anderen Zahlen bezeichnet man auch als zusammengesetzte Zahlen, da sie sich alle über Produkte von Primzahlen darstellen lassen, der Fachbegriff hierfür lautet Primfak- torzerlegung.

Allgemein bekannt ist ebenfalls, und nur durchaus logisch, dass die Anzahl der Primzah- len in einer betrachteten Menge immer kleiner wird, je größer diese betrachtete Teilmenge der natürlichen Zahlen gewählt wird. Das heißt, die Wahrscheinlichkeit, dass eine belie- bige natürliche Zahl eine Primzahl ist, nimmt ab, je größer die Zahl wird. Beispielhaft ergibt sich folgender Sachverhalt: Betrachtet man die Menge von 1 - 100, so liegen in dieser Menge 25 Primzahlen, also 25,0 %. Erweitert man die Menge von 1 - 1.000 lie- gen 168 Primzahlen in dieser, was nur noch 16,8 % entspricht. Schaut man weiter und betrachtet die Menge 1 - 100.000 so liegen immerhin 9.592 Zahlen in dieser Menge, die prim sind, was nur noch einem prozentualen Anteil von rund 9,6 % entspricht. Die Wahr- scheinlichkeit sinkt also bereits bei diesen verhältnismäßig kleinen Mengen von 0,250 auf 0,096. Bedenkt man, dass Primzahlen in der Praxis erst ab 100 oder 1000 Stellen sinnvol- le Anwendungen finden, wird schnell klar, dass es immer schwieriger wird, zufällig eine Primzahl auszuwählen. Allerdings ist unumstritten, dass es unendlich viele Primzahlen gibt. Der Beweis dazu stammt von EUKLID.

Die Seltenheit der Primzahlen im gesamten Bereich der natürlichen Zahlen fand erst recht spät eine praktische Anwendung. Erst mit dem Aufkommen von elektronischen Rechen- maschinen erlangte die Primzahl und vielmehr die Frage, ob eine beliebig große Zahl eine Primzahl ist und wie man dies möglichst effizient und schnell herausfindet, an Bedeutung.

1.2 Kryptologie

Das größte Anwendungsgebiet heutzutage ist die sogenannte Kryptologie. Diese umfasst die beiden Wissenschaften Kryptografie, welche das Verschlüsseln von Informationen meint und “sich mit der Sicherung von Nachrichten gegen einen unbefugten Zugriff [be- schäftigt]” (Karpfinger 2011[KK10], S.1 ; Umstellung: K.K.), und die Kryptoanalyse, welche Methoden und Techniken entwickelt, um die Informationen aus den verschlüs- selten Daten zu gewinnen. Der Begriff Krytopgrafie wird aber häufig für Kryptologie verwendet.

Viele der Verfahren, die zur Verschlüsselung in der Kryptologie genutzt werden, beruhen auf dem Nutzen von möglichst großen Primzahlen. Hier haben Zahlen, die prim sind und vorzugsweise mehr als 100 Stellen haben, eine fundamentale Bedeutung. Eines der bekanntesten Verfahren, welches die Verschlüsselung mittels großer Primzahlen nutzt, möchte ich kurz vorstellen, um einen Alltagsbezug des Themas herzustellen.

1.2.1 RSA-Verfahren

Das Verfahren wurde 1977 von R. L. RIVEST, A. SHAMIR und L. ADLEMAN vorgestellt und zählt zur Klasse der Public-Key-Verfahren, das heißt, der Schlüssel zum Verschlüsseln ist öffentlich zugänglich und funktioniert folgendermaßen:

Möchte der Sender S an den Empfänger E eine Nachricht N senden, so benutzt S einen öffentlichen Schlüssel e von E, den er in einem öffentlichen Verzeichnis findet. Dieser Schlüssel e wird auf N angewendet, und an E wird der erhaltende Code C = e (N) gesendet. Der Empfänger E hat wiederum einen geheimen Schlüssel d, mit dessen Hilfe er aus dem Geheimtext C die Nachricht N wieder herstellen kann, denn N = d (e (N)). Die Sicherheit dieses Verfahrens beruht auf der Tatsache, dass aus dem Code C = e (N) und dem öffentlichen Schlüssel e, keine Rückschlüsse in angemessener Zeit auf die Nachricht N und den geheimen Schlüssel d zu ziehen sind.

Damit die Sicherheit gewährleistet wird, ist es für das Verfahren sehr wichtig, dass es im Allgemeinen sehr schwer ist, eine (beim Verfahren benutzte und öffentlich bekannte) große natürliche Zahl n in ihre Primfaktoren zu zerlegen.

Das hierfür verwendete Kryptosystem ist asymmetrisch und zählt zu der Klasse der Exponentiationschiffren. Die Nachricht N, aufgefasst als Element von Z n, n ∈ N, wird über den Sender S verschlüsselt, indem mit dem öffentlichen Schlüssel e von E eine Potenz von N gebildet wird:

Abbildung in dieser Leseprobe nicht enthalten

Der Empfänger E hat den geheimen Schlüssel d so bestimmt, dass [Abbildung in dieser Leseprobe nicht enthalten] ergibt. Zu beachten ist außerdem, dass beide Schlüssel (also sowohl d als auch e) vom Empfänger E stammen. Das heißt, der öffentliche Schlüssel e ist jedem zugänglich, ergo kann jeder eine Nachricht an E schicken. Aber nur der Empfänger E kennt den geheimen Schlüssel d zum Entschlüsseln der Nachricht N. Folgerichtig kann nur E und niemand anderes (nicht einmal der Sender S) seine Nachricht N entschlüsseln.

Für n ∈ N mit ϕ (n) als EULERSCHE FUNKTION gilt:

Abbildung in dieser Leseprobe nicht enthalten

wobei für zwei verschiedenen Primzahlen p und q, n = pq ist.

Die Klartextmenge P und die Geheimtextmenge C sind beides gleich Z n, die Schlüsselmenge ist mit

Abbildung in dieser Leseprobe nicht enthalten

gegeben.

Die Verschlüsselungsfunktion fe mit e ∈ K ist definiert durch fe (N) = Ne für N ∈ P. Letztendlich ist die Entschlüsselungsfunktion fd mit d ∈ K definiert über fd (C) = Cd für C ∈ C, wobei gilt, dass ed ≡ 1(mod ϕ (n)). Dabei wird d mit Hilfe des euklidischen Algorithmus zu e ∈ K bestimmt. Die Entschlüsselung einer verschlüsselten Nachricht N liefert also wieder die Nachricht N selbst:

Abbildung in dieser Leseprobe nicht enthalten

Zu beachten ist hierbei, dass die Zahlen n = pq und e öffentlich bekannt sind. Dem potenziellen Angreifer darf die Zahl ϕ (n) = (p − 1)(q − 1) nicht bekannt sein. Er kann nun, ebenso wie der Empfänger E, unter Nutzung des euklidischen Algorithmus den geheimen Schlüssel d ermitteln. Wählt man die Primzalen p und q allerdings entsprechend groß, ist es im Allgemeinen sehr schwierig, aus der Kenntnis n = pq die Primfaktoren p und q und damit ϕ (n) = (p − 1)(q − 1) zu ermitteln. In der Praxis werden Primzahlen der Größenordnung 512 Bit gewählt. (vgl. [KK10], Kapitel 7)

Um nun solch einen sicheren Schlüssel d zu erzeugen, werden ausreichend große Prim- zahlen benötigt. Und genau das ist der zentrale Anknüpfungspunkt zu den Primzahltests. Bisher existiert keine Möglichkeit, Primzahlen zu konstruieren, “also etwa eine effizient berechenbare Funktion f: N P mit unendlicher Bildmenge.” ([KK10], S.141). Daher wird in der Praxis folgendes Vorgehen angewendet: Man wählt eine beliebig große, un- gerade natürliche Zahl n und prüft diese, ob sie eine Primzahl ist. Ergibt ein solcher Test, dass dies nicht der Fall ist, überprüft man eine ungerade natürliche Zahl in der Nähe von n. Denn der Primzahlsatz besagt, dass mit einer großen Wahrscheinlichkeit eine Primzahl in der Nähe von n liegt.

2 Primzahltests

Solche Tests zum Überprüfen, ob eine Zahl prim ist, werden als Primzahltests bezeichnet. Dabei unterscheiden sich die verschiedenen Tests sowohl in ihrer Komplexität, als auch in ihrer Genauigkeit. So unterscheidet man zwischen probabilistischen oder randomisierten Tests, welche aussagen, dass n nur mit einer gewissen Wahrscheinlichkeit wirklich eine Primzahl ist, und deterministischen Tests, das heißt, es wird stets ein konkretes Ergebnis geliefert. Wenn der Test also ergibt, dass n eine Primzahl ist, dann ist dies bei deterministischen Tests tatsächlich so, während die probabilistischen nur eine Vermutung aufstellen, dass es mit großer Wahrscheinlichkeit so ist.

Im Folgenden werde ich verschiedene Primzahltests vorstellen und ein Fazit zu ihrer An- wendungstauglichkeit ziehen. Der erste Test, mit dem ich mich beschäftigen möchte, ist nicht nur ein Primzahltest, sondern auch Voraussetzung für andere speziellere Verfahren.

2.1 Probedivision

Bei der Probedivision überprüft man, ob die Zahl n durch eine kleine, bekannte Primzahl p teilbar ist. Effizient wird eine Division mit Rest durchgeführt. Bleibt bei der Division durch p kein Rest, so hat man einen Teiler gefunden, das heißt, n ist keine Primzahl. Die Methode beruht auf dem einfachen Satz 1:

Wenn n eine zusammengesetzte natürliche Zahl ist, dann hat n Primteiler p, der nicht größer ist als √ n.

□Den Beweis kann man kurz fassen, indem man n als das Produkt zweier natürlicher Zahlen x und y schreibt, für die jeweils gilt 1 < x, y ≤ √ n. Da jede natürliche Zahl m > 1 einen Primteiler hat, haben auch x und y Primteiler. Diese müssen auch n teilen, somit folgt die Behauptung. ■ (vgl. Buchmann 2010 [Buc10], S.125).

Ein Beispiel wäre die Zahl n = 403; diese wird nacheinander mit Rest durch die be- kannten kleinen Primzahlen 2, 3, 5,7, 11 und 13 dividiert. Schlussendlich ergibt sich die n = 13 · 31.

Die Überprüfung von großen Zahlen auf Primalität ist prinzipiell möglich. Da man aber alle Primzahlen kleiner gleich √ n zur Division durchprobieren muss, ist diese Methode vor allem bei sehr großen Zahlen, wie sie in der Kryptologie bevorzugt werden, ineffizient, da die Bestimmung mit einem großen Aufwand verbunden ist. Die Primzahlen, die für die Division möglich sind, erstellt man typischerweise in einer Liste, meistens mit Hilfe des SIEB DES ERATOSTHENES.

2.2 Siebmethoden

Das SIEB DES ERATOSTHENES gehört zur Klasse der Siebmethoden, welche ein Teilge- biet der analytischen Zahlentheorie sind, welche wiederum der Zahlentheorie angehört. Siebmethoden beschäftigen sich mit den Eigenschaften der ganzen Zahlen, welche mit Addition und vor allem Multiplikation zusammenhängen, also Teilbarkeit, Faktorzerle- gung, Restklassen und auch Primzahlen, was in diesem Kontext besonders interessant ist. Inhaltlich befassen sie sich hauptsächlich sowohl mit der Bestimmung der Anzahl aller Zahlen unterhalb einer gegebenen Schranke, wobei die Zahlen alle eine bestimmte Eigen- schaft haben, als auch mit der Abschätzung von Summen zahlentheoretischer Funktionen.

2.2.1 Sieb des Eratosthenes

Das SIEB DES ERATOSTHENES ist wohl einer der einfachsten Primzahltests und wohl der älteste bekannte Test, um alle Primzahlen zu ermitteln, die kleiner oder gleich einer vorgegeben Zahl sind. Benannt wurde der Algorithmus nach dem griechischen Mathe- matiker ERATOSTHENES VON KYRENE, der im 3. Jahrhundert v. Chr. lebte. Allerdings führte dieser nur die Bezeichnung “Sieb” für das Verfahren ein, welches schon lange vor seiner Zeit bekannt war. ERATOSTHENES ist ebenfalls für seine recht genaue Berechnung des Erdumfangs bekannt, um die es hier aber in keiner Weise gehen soll.

Die Idee ist, nach und nach alle zusammengesetzten Zahlen bis zu einer bestimmten vor- gegebenen Zahl “auszusieben”, so dass am Ende nur noch die Primzahlen übrig bleiben. Zur Beschreibung der Vorgehensweise halte ich mich an (Rempe 2009 [RW09], Abschnitt 1.5).

Zuerst werden alle Zahlen von 1 bis zu einer frei gewählten natürlichen Zahl N, welche die obere Schranke darstellt, aufgeschrieben. Danach wird wie folgt verfahren:

- Da 1 keine Primzahl ist, wird sie gestrichen und bei 2 begonnen.
- 2 muss eine Primzahl sein, da als Teiler höchstens 1 und 2 in Frage kommen. Die Vielfachen von 2, angefangen von 4, werden nun gestrichen, da sie nicht prim sein können.
- Die nächste Zahl welche stehen geblieben ist, ist die 3, diese muss also eine Prim- zahl sein. Analog zu Schritt 2, werden nun alle Vielfachen von 3, beginnend bei 6, gestrichen.

- Die nächste nicht durchgestrichenen Zahl ist 5, und wiederrum werden hier alle

Vielfachen der Zahl gestrichen. Dieses Vorgehen wird fortgesetzt bis zu [Abbildung in dieser Leseprobe nicht enthalten]. Alle Zahlen zwischen [Abbildung in dieser Leseprobe nicht enthalten] und N, die keine Primzahlen sind, müssen mindestens einen Faktor besitzen, der höchstens so groß wie [Abbildung in dieser Leseprobe nicht enthalten] ist, und wurden somit bereits gestrichen. Siehe dazu auch den Satz und Beweis unter 2.1. Alle nichtgestrichenen Zahlen zwischen 1 und N sind also die Primzahlen.

Das ganze soll an einem Beispiel verdeutlicht werden. Für N = 400 sieht das Sieb am Ende wie folgt aus, dabei stehen die unterschiedlichen Graustufen für die einzelnen Sieb- schritte:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Sieb des Eratosthenes für N = 400

Die resultierenden Primzahlen zwischen 1 und 400 sind demnach folgende 78:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397

Diese Methode ist leicht einsehbar für jedermann, deswegen möchte ich im Kapitel 3 noch einmal auf diesen Algorithmus zurückkommen. Des Weiteren lässt sich das Verfahren sehr einfach auf den Computer implementieren und verwenden. Jedoch ist der Algorithmus für die Praxis, mit hunderten oder mehr Stellen, nicht zu gebrauchen, da die Berechnung und Streichung der einzelnen Zahlen zu viel Zeit in Anspruch nimmt. Deswegen ist dieses Verfahren ineffizient.

2.2.2 Sieb von Atkin

Eine Optimierung des SIEB DES ERATOSTHENES ist das SIEB VON ATKIN, welches schneller arbeitet, ebenfalls aber alle Primzahlen bis zu einer gewissen oberen Grenze bestimmt. Der Algorithmus wurde von A. O. L. ATKIN und DANIEL J. BERNSTEIN entwickelt und ist wie folgt aufgebaut. Dabei orientiere ich mich an den Darstellungen von ATKIN & BERNSTEIN 1999 ([AB99]) und 2004 ([AB04]).

- Die erste Festlegung sagt aus, dass alle Reste Modulo 60 Reste sind.
- Alle Zahlen, auch die Variablen x und y, sind natürliche Zahlen.
- In folgender Darstellung bedeutet Invertieren, dass das Merkmal (prim oder nichtprim) eines Eintrages in der Siebliste zum Gegenteil gewechselt wird.

1. Es wird eine Ergebnisliste erstellt, die mit 2, 3 und 5 gefüllt ist.
2. Es wird eine Siebliste mit allen natürlichen Zahlen erstellt, die am Anfang alle auf das Merkmal “nicht-prim” gesetzt werden.

3. Für jeden Eintrag in der Siebliste wird Folgendes ausgeführt:

- Falls der Eintrag eine Zahl mit Rest 1, 13, 17, 29, 37, 41, 49, oder 53 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 4 x2 + y2 = Eintragszahl.
- Falls der Eintrag eine Zahl mit Rest 7, 19, 31, oder 43 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3 x2 + y2 = Eintragszahl.
- Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3 x2y2 = Eintragszahl, wobei x > y.

4. Begonnen wird bei der kleinsten Zahl.
5. Die nächste Zahl, die in der Siebliste als prim markiert ist, wird der Ergebnis- liste zugeführt.
6. Diese Zahl wird quadriert und alle Vielfachen des Quadrates in der Siebliste als nicht-prim gekennzeichnet.
7. Wiederhole Schritt 5-7.

Der im ersten Moment etwas verwirrend aussehende Algorithmus lässt sich schnell und einleuchtend erklären.

Es werden alle Zahlen ignoriert, die durch 2, 3 oder 5 teilbar sind, denn:

- Alle natürlichen Zahlen, die mit Modulo 60 Rest 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, oder 58 ergeben, lassen sich durch 2 teilen und sind somit keine Primzahlen.
- Alle Zahlen mit Modulo 60 Rest 3, 9, 15, 21, 27, 33, 39, 45, 51, oder 57 sind wiederum teilbar durch 3 und daher nicht prim.
- Analog sind alle natürlichen Zahlen mit Modulo 60 Rest 5, 25, 35, oder 55 durch 5 teilbar und somit nicht prim. Diese Reste werden alle ignoriert.
- Des Weiteren haben alle Zahlen mit Modulo 60 Rest 1, 13, 17, 29, 37, 41, 49, oder 53 einen Modulo 4 Rest von 1. Diese Zahlen sind genau dann Primzahlen, wenn die Anzahl an Lösungen für 4 x2 + y2 = n ungerade ist und die Zahl quadratfrei ist.
- Alle natürlichen Zahlen mit Modulo 60 Rest 7, 19, 31, oder 43 haben einen Modulo 6 Rest von 1. Jene Zahlen sind genau dann prim, wenn die Anzahl der Lösungen für 3 x2 + y2 = n ungerade ist und die Zahl wieder quadratfrei ist.
- Entsprechend weisen alle Zahlen mit Modulo 60 Rest 11, 23, 47, oder 59 einen Modulo 12 Rest von 11 auf. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für 3 x2y2 = n ungerade ist. Auch hier wird die Quadratfreiheit vorausgesetzt.

Neben diesen sich recht ähnlichen Siebmethoden, gibt es auch noch andere, so zum Beispiel die Folgenden, welche ich nur kurz erwähnen möchte.

2.2.3 Weitere Siebmethoden

In meinen Recherchen fand ich heraus, dass die BRUNsche Siebmethode vor allem bei der Untersuchung von Primzahlzwillingen, also Primzahlen, die nur durch eine zusam- mengesetzte Zahl voneinander getrennt werden, Anwendung finden. Primzwillinge sind zum Beispiel (11; 13) oder (17; 19), aber auch (387; 389). Bis heute ist ungeklärt, ob die Menge der Primzwillinge ebenso unendlich ist wie die Menge der Primzahlen selbst. Mit der BRUNschen Siebmethode, welche 1920 von dem norwegischen Mathematiker VIGGO BRUN in die Zahlentheorie eingeführt wurde, sind untere und obere Abschätzun- gen möglich, die nahezu auf dem gleichen Weg gewonnen werden können. Im Einzelnen sind sie jedoch recht mühsam.

Eine deutlich einfachere Abschätzung, zumindest nach oben, erhält man durch die SELBERGsche Siebmethode. Aber auch hier beschäftigt sich die Siebmethode mit der Bestimmung von Primzahlzwillingen. ATLE SELBERG war ein Schüler von BRUN und veröffentlichte 1947 seine verbesserte Variante des BRUNschen Siebes.

[...]

Ende der Leseprobe aus 41 Seiten

Details

Titel
Primzahltests
Untertitel
Zwischen Wissenschaft und Schule
Hochschule
Technische Universität Dresden  (Institut für Algebra)
Note
1,1
Autor
Jahr
2011
Seiten
41
Katalognummer
V231584
ISBN (eBook)
9783656488934
ISBN (Buch)
9783656490494
Dateigröße
1018 KB
Sprache
Deutsch
Schlagworte
primzahltests
Arbeit zitieren
Karina Kliemank (Autor), 2011, Primzahltests, München, GRIN Verlag, https://www.grin.com/document/231584

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Primzahltests


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden