Student Thesis STUD-2007

BibliographyHoffmann, Benjamin: Faktorisierung grosser Zahlen mit dem Quadratischen Sieb.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Student Thesis No. 2007 (2005).
43 pages, german.
CR-SchemaF.2.1 (Numerical Algorithms and Problems)
I.1.2 (Symbolic and Algebraic Manipulation Algorithms)
KeywordsQuadratisches Sieb; Faktorisieren; Zahlentheorie; Kryptographie
Abstract

Die Bestimmung der Primfaktorzerlegung einer natuerlichen Zahl stellt ein schwieriges Problem dar, fuer das bis zum heutigen Zeitpunkt kein effizientes Loesungsverfahren bekannt ist. Bis in die fruehen 1970er Jahre konnten Zahlen mit bis zu 20 Stellen faktorisiert werden. Dann stellten 1975 Brillhart und Morrison ihre continued fraction factoring method vor, die die Faktorisierung von 50-stelligen Zahlen ermoeglichte. Der naechste grosse Fortschritt in diesem Bereich kam dann 1982, als Carl Pomerance das Quadratische Sieb einfuehrte. Mit dieser Methode kann man momentan Zahlen mit ueber 150 Stellen zerlegen.

Ziel der Studienarbeit war es, das Quadratische Sieb zu implementieren. Als Programmiersprache diente C++, die erforderliche Langzahlarithmetik wurde durch die GNU Multiple Precision Arithmetic Library (GMP) bereitgestellt.

Full text and
other links
PDF (282131 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateSeptember 9, 2005
   Publ. Computer Science