Titelaufnahme

Titel
Ausgewählte Primzahltests / vorgelegt von Gernot Koller
Verfasser/ VerfasserinKoller, Gernot
Begutachter / BegutachterinLettl, Guenter
Erschienen2015
Umfang80 Bl. : Zsfassungen (2 Bl.) ; graph. Darst.
HochschulschriftGraz, Univ., Dipl.-Arb., 2015
Anmerkung
Zsfassungen in dt. und engl. Sprache
SpracheDeutsch
DokumenttypDiplomarbeit
Schlagwörter (GND)Primzahltest
URNurn:nbn:at:at-ubg:1-85619 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Ausgewählte Primzahltests [0.59 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Primzahltests (d.s. Tests, die untersuchen, ob eine für gewöhnlich große Zahl eine Primzahl ist oder nicht) sind in der heutigen Zeit zu einer wichtigen Grundlage für die Kryptographie und damit für unseren Alltag (z.B. E-Mails) geworden. Doch wie funktionieren derartige Tests? In dieser Arbeit werden einige davon vorgestellt und besprochen. Einerseits gibt es Tests, die uns ganz sicher sagen können, ob eine Zahl n prim ist, die dafür aber mit einem hohen Rechenaufwand verbunden sind oder eine Primfaktorisierung der Zahl n-1 benötigen, wie die Umkehrung des Satzes von Fermat nach Lucas und Lehmer. Andererseits gibt es die sogenannten probabilistischen Primzahltests, die nur mit einer meist sehr hohen Wahrscheinlichkeit Auskunft darüber geben können, ob eine Zahl n prim ist, wie z.B. der Solovay-Strassen-Primzahltest oder der Miller-Rabin-Primzahltest. Außerdem wird noch ein Test angeführt, der auf Lucas-Folgen basiert. Vom Leser werden dabei nur grundlegende Kenntnisse der Algebra und Zahlentheorie erwartet, wie man sie etwa nach dem Besuch einer einführenden Vorlesung in dem Bereich hat. Die übrige Theorie, die für die Tests benötigt wird, wird Schritt für Schritt im Rahmen der Arbeit erläutert (z.B. Theorie über quadratische Reste oder quadratische Zahlkörper).

Zusammenfassung (Englisch)

Recently, primality tests (i.e. tests that tell us whether a usually large number is a prime number or not) have become very important because of their use in cryptography and therefore in our everyday life (e.g. in emails). But how do these tests work? In this thesis some selected primality tests are covered: There are tests that tell us exactly whether a given number n is prime or not. However, it may be complicated to compute the test or a factorisation of n-1 is needed, like in the converse of Fermats theorem by Lucas and Lehmer. There are also probabilistic tests which only tell us whether a number n is prime to a (usually very) high probability, like the test by Solovay and Strassen or the test by Miller and Rabin. Furthermore, a test based upon Lucas sequences is described. Only elementary knowledge on the topics of algebra and number theory (like it is covered in a beginners course on this topic at universities) is required as a prerequisite for the reader; the remaining theory that is necessary is explained in the thesis itself (such as theory of quadratic residues or quadratic fields).