Campus Event Calendar
Event Entry
What and Who
Theoretische und experimentelle Untersuchungen zu einem hocheffizienten randomisierten Primzahltest
Christian Hoffmann
Ph.D. application talk
AG 1, AG 2, AG 3, AG 4, AG 5
MPI Audience
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 30 September 2005
14:00
30 Minutes
46.1 - MPII
0.24
Saarbrücken
Abstract
Theoretische und experimentelle Untersuchungen zu einem
hocheffizienten randomisierten Primzahltest
Primzahltests sind Algorithmen, die Primzahlen von zusammengesetzten
Zahlen unterscheiden. Wir betrachten hierbei Monte-Carlo-Algorithmen
mit einseitigem beschränkten Fehler. Sie klassifizieren Primzahlen
immer richtig, während sie zusammengesetzte Zahlen mit unabhängig von
der Eingabe beschränkter Wahrscheinlichkeit auch fälschlicherweise als
Primzahlen einstufen können. Durch mehrmalige Wiederholung eines
solchen Primzahltests erhält man ein für die Praxis ausreichend
verlässliches Verfahren zur Erkennung von Primzahlen.
Sehr häufig wird der Miller-Rabin-Primzahltest eingesetzt. Er hat eine
Fehlerwahrscheinlichkeit von höchstens 1/4. Ein neuer Primzahltest ist
der randomisierte starke quadratische Frobenius-Test (RQFT), der in
[Gra98] vorgeschlagen wird und Fehlerwahrscheinlichkeit <1/7710 hat,
während die Laufzeit asymptotisch der von drei Iterationen des
Miller-Rabin-Tests entspricht.
Im Vortrag wird der RQFT vorgestellt. Dazu werden die wichtigsten der
mathematischen Zusammenhänge, die der Test ausnutzt, genannt. Außerdem
wird darauf eingegangen, wie der RQFT effizient implementiert werden
kann. In diesem Zusammenhang werden auch Ergebnisse von
experimentellen Laufzeitmessungen vorgestellt.
[Gra98] Grantham, Jon: A Probable Prime Test With High Confidence.
Journal of Number Theory, 72:32--47, 1998.
hocheffizienten randomisierten Primzahltest
Primzahltests sind Algorithmen, die Primzahlen von zusammengesetzten
Zahlen unterscheiden. Wir betrachten hierbei Monte-Carlo-Algorithmen
mit einseitigem beschränkten Fehler. Sie klassifizieren Primzahlen
immer richtig, während sie zusammengesetzte Zahlen mit unabhängig von
der Eingabe beschränkter Wahrscheinlichkeit auch fälschlicherweise als
Primzahlen einstufen können. Durch mehrmalige Wiederholung eines
solchen Primzahltests erhält man ein für die Praxis ausreichend
verlässliches Verfahren zur Erkennung von Primzahlen.
Sehr häufig wird der Miller-Rabin-Primzahltest eingesetzt. Er hat eine
Fehlerwahrscheinlichkeit von höchstens 1/4. Ein neuer Primzahltest ist
der randomisierte starke quadratische Frobenius-Test (RQFT), der in
[Gra98] vorgeschlagen wird und Fehlerwahrscheinlichkeit <1/7710 hat,
während die Laufzeit asymptotisch der von drei Iterationen des
Miller-Rabin-Tests entspricht.
Im Vortrag wird der RQFT vorgestellt. Dazu werden die wichtigsten der
mathematischen Zusammenhänge, die der Test ausnutzt, genannt. Außerdem
wird darauf eingegangen, wie der RQFT effizient implementiert werden
kann. In diesem Zusammenhang werden auch Ergebnisse von
experimentellen Laufzeitmessungen vorgestellt.
[Gra98] Grantham, Jon: A Probable Prime Test With High Confidence.
Journal of Number Theory, 72:32--47, 1998.
Contact
Kerstin Meyer-Ross
226
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Ph.D. application talks
Friederike Gerndt, 09/29/2005 15:58
Friederike Gerndt, 09/29/2005 14:38 -- Created document.
Friederike Gerndt, 09/29/2005 14:38 -- Created document.