Im Rahmen der Arbeit sollen verschiedene Varianten und Optimierungen des LLL-Algorithmus effizient und, wenn algorithmisch möglich und sinnvoll, parallelisiert in C++ implementiert werden. Die Effizienz ist durch Einsatz von Werkzeugen für Performance-Analyse zu validieren und zu belegen.

Hierzu ist zu Beginn eine Literaturrecherche über bestehende Algorithmen/Verfahren und existierende Implementierungen durchzuführen. Anschließend sollen die erstellten Implementierungen bezüglich ihrer Laufzeit und ihrem algorithmischem Verhalten (z.B. benötigten Iterationen, Anzahl der Reihenfolgenänderungen) miteinander verglichen werden.

Publications

• Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász: Factoring polynomials with rational coefficients.
• Felix Fontein, Michael Schneider, and Urs Wagner: Potlll: a polynomial time version of lll with deep insertions.
• Masaya Yasuda and Junpei Yamaguchi: A new polynomial-time variant of lll with deep inserti- ons for decreasing the squared-sum of gram–schmidt lengths.