Titel (deu): Primzahlen

Autor: Gaubitzer, K. (Katharina)

Beschreibung (deu): St. Pölten, FH-StG für Telekommunikation u. Medien, Dipl.-Arb., 2002

Beschreibung (deu): Von der Antike bis weit in die Neuzeit hinein sahen Mystiker in den Zahlen geheimnisvolle Bedeutungen und magische Kräfte verborgen.
Die vorliegende Arbeit beschäftigt sich mit einem der ältesten Gebiete der Zahlentheorie: dem der Primzahlen. Die Primzahlen sind die Bausteine der natürlichen Zahlen, und schon die alten Griechen erkannten deren Wichtigkeit. Eines der faszinierendsten Phänomene auf diesem Gebiet ist, dass sich viele Fragen und Probleme mühelos formulieren lassen, aber die dazugehörenden Beweise unerhört schwierig zu führen und vielfach noch gar nicht erbracht worden sind. Im Kapitel Primzahlen werden Primzahlen im Allgemeinen beschrieben. Primzahlen sind ein wichtiger Teil der Zahlentheorie, welche näher erläutert wird. In der Folge werden algebraische Strukturen erklärt, um die darauf folgenden Kapitel besser verstehen zu können. Ein Teil des ersten Kapitels befasst sich mit der Geschichte der Primzahlenforschung. Schon um 300 v. Chr. konnte Euklid den Beweis führen, dass es unendlich viele Primzahlen gibt, und Eratosthenes entdeckte 200 v. Chr. einen Algorithmus zur Berechnung von Primzahlen, den man heute „Sieb des
Eratosthenes“ nennt. Damit kann man gewisse Strukturen erkennen, wie zum Beispiel Primzahlenzwillinge. Primzahlenzwillinge sind immer zwei
Primzahlen, die die Differenz zwei haben. Mersenne entdeckte, dass Zahlen der Form 2p –1 - wobei p auch eine Primzahl ist - meist auch wieder Primzahlen sind. Diese Form der Primzahlen nennt man heute Mersenne’sche Primzahlen. Auch vollkommene Zahlen haben große Bedeutung. Vollkommene Zahlen
sind keine Primzahlen, doch jede vollkommene Zahl besitzt genau eine
Mersennesche Primzahl als Teiler und jede Mersennesche Primzahl legt
genau eine vollkommene Zahl fest.
Fermat beschäftigte sich mit Zahlen der Form 22 1 n+ , wobei n eine natürliche Zahl ist. Diese Zahlen werden Fermat’sche Zahlen genannt. Fermat vermutete, dass alle Zahlen dieser Form Primzahlen sind, jedoch hat sich gezeigt, dass dies nur auf einige Zahlen dieser Form zutrifft. Weiters hat er „Fermats kleinen Satz“ definiert, mit dem sich beweisen lässt, ob eine bestimmte Zahl eine Primzahl sein könnte oder eine zusammengesetzte Zahl ist. Weiters wird im ersten Kapitel auf Carmichael Zahlen eingegangen. Diese
Zahlen sind zusammengesetzte Zahlen, die der Fermat-Test nicht als solche erkennt. Im nächsten Kapitel werden zwei Algorithmen erklärt, die beweisen sollen, ob eine Zahl prim ist oder nicht. Bei diesen Algorithmen handelt es sich um den Solovay-Strassen-Algorithmus und den Lehmann-Algorithmus. Im dritten Kapitel werden die wichtigsten Algorithmen gezeigt, die zur Entdeckung von Primzahlen verwendet werden. Dabei handelt es sich um das Sieb des Eratosthenes, den Fermat-Test, den Rabin-Miller-Test - der eine Erweiterung des Fermat-Tests ist, um die Carmichael Zahlen zu erkennen - und den Lucas-Lehmer-Test, der die Mersenneschen Primzahlen verwendet. Diese Algorithmen bauen auf das Wissen aus dem Kapitel Primzahlen auf.
Außer den Beschreibungen dazu findet man hier noch für jeden Test ein
kleines Programm, das in C++ geschrieben wurde. Abschließend werden im letzten Kapitel die Anwendungen der Primzahlen erläutert. Primzahlen haben große Bedeutung in der Kryptographie. Viele der kryptographischen Algorithmen benötigen große Primzahlen, wie der RSAAlgorithmus, der näher beschrieben wird. Die Riemann’sche Vermutung schließt auf die Anzahl der Primzahlen in einem bestimmten Intervall. Unterdessen wiesen einige Methoden aus dem Quantenchaos den Weg, wie man die Riemann’sche Vermutung beweisen könnte. Die Goldbach’sche Vermutung besagt, dass sich jede gerade Zahl aus der
Summe von zwei Primzahlen darstellen lässt. Die Goldbach’sche Vermutung ist bisher weder widerlegt noch bestätigt worden. Und zum Abschluß wird ein Projekt vorgestellt, dass sich GIMPS „Great Internet Mersenne Prime Search“ nennt. Unter GIMPS versteht man ein Suchprogramm für Mersenne’sche Primzahlen mit Hilfe des Lucas-Lehmer-Tests. Dabei kann jeder über Internet seine Rechnerleistung zur Verfügung stellen und so bei der Suche nach einer möglichst großen Primzahl mitmachen.

Beschreibung (eng): Of the antiquity far into the modern times saw mystic meanings mysterious in the numbers and magic strengths concealed. The present work is occupied with one of the oldest fields of number theory: that of the prime numbers. The prime numbers are the elements of the natural numbers and already the old Greeks recognized its importance. One the fascinating it is phenomena on this field, that many questions and problems can easily be formulated but the pertinent evidence were still at all not produced. The chapter “prime numbers” deals with prime numbers in general. Prime numbers are an important feature of Number theory. In addition we will also offer an insight into the nature of algebraical structures serving as a basis for further steps. A huge part of the first chapter explains the history of prime number research. In 300 B.C. Euklid proofed the existence of an infinite number of prime numbers. A hundred years later Eratosthenes introduced a method of prime number estimation referred to as “sieve of the Eratosthenes”. This method is capable of revealing specific structures like prime number twins. Prime number twins have a constant difference of two. Mersenne explored the nature of numbers based on the composition rule 2p –1, where p represents a prime number. He discovered that in most cases those numbers were prime themselves. These prime numbers are called Mersenne numbers. Perfect numbers are of great importance too: Perfect numbers do not represent prime numbers. Every perfect number has exactly one corresponding Mersenne number as a divisor, and each Mersenne prime number serves as a definition for a specific perfect number. Fermat dedicated a lot of his research activities to numbers corresponding to the composition rule 22 1 n+ , where n represents a natural number. Those numbers are called Fermat numbers. His first speculation for prime number nature of these numbers did not hold and is valid for a restricted number of observations only. He also proposed the famous theorem of „Fermats small theorem“ which is capable of testing if numbers are of prime - or compositional nature. In addition the first chapter also covers Carmichael Numbers. These numbers are compound figures, that cannot be detected by Fermat´s test. The next chapter mainly deals with two algorithms, that try to reveal whether a
number is prime or not. These two algorithms are refered to as “Solovay
Strassen-algorithm”, respectively “Lehmann-algorithm”. In the third chapter we will introduce some of the most important algorithms used in order to discover prime numbers. These are “sieve of the Eratosthenes”, Fermat´s test, Rabin-Miller-test - an extension to Fermats test with an intension to find Carmichael numbers - and finally the Lucas-Lehmertest, which is based on Mersenne prime numbers. All these algorithms are based on prime number theory. In addition to a general description, a C++ implementation is offered in each case. The last chapter will provide an insight into different applications for prime numbers. Prime numbers are of great importance in the field of cryptography. Most chryptographic algorithms, such as the RSA algorithm, that will be covered in detail, are based on prime numbers.
Riemann’s hypothesis is a quantitiy measure for the count of prime numbers within a specific interval. Methods of quantum chaos theory show possibilities of proofing Riemann´s hypothesis. Goldbach´s hypothesis states, that every straight number can be expressed by the sum of two prime numbers. Goldbach´s hypothesis has not been proofed or rejected yet. Finally we present GIMPS (Great Internet Mersenne Prime Search) project. GIMPS is an internet based search engine for Mersenne Primnumbers, that implements the Lucas Lehmer test. By pooling unemployed PC processor
resources over the internet, home users may contribute to the exploration of undiscovered prime number phenomena.

Sprache des Objekts: Deutsch

Datum: 2002

Rechte: © Alle Rechte vorbehalten

Klassifikation: Primzahlen

Permanent Identifier