Computeralgebra-Tagung 2014

Die sechste Computeralgebra-Tagung der Fachgruppe fand vom 15. bis 17. Mai 2014 am Institut für Mathematik der Universität Kassel statt. Die lokale Leitung lag in den Händen von Prof. Wolfram Koepf.

Den von der Fachgruppe Computeralgebra mit 500 Euro dotierten Nachwuchspreis für den den besten Vortrag eines Nachwuchswissenschaftlers erhielt Christian Eder.

Hauptvorträge

Prof. Dr. Bettina Eick (TU Braunschweig):
Algorithmen in der Gruppentheorie

In dem Vortrag wird ein kurzer Überblick über den Stand der Forschung in der algorithmischen Gruppentheorie gegeben. Dann werden einige der aktuellen Forschungsgebiete beschrieben, dazu gehören z.B. Algorithmen für Matrixgruppen, Algorithmen in der Theorie der p-Gruppen und der nilpotenten Gruppen und die Klassifikation von Gruppen.

Prof. Dr. Raymond Hemmecke (TU München):
Algebraische Methoden in der ganzzahligen Optimierung

Algebraische Methoden finden in der ganzzahligen Optimierung auf verschiedene Weisen ihren Einsatz: z. B. als Optimalitätszertifikate (= Gröbnerbasen torischer Ideale), zur effizienten Kodierung von Gitterpunktmengen (= rationale Erzeugendenfunktionen) oder als Nichtlösbarkeitszertifikate (= mittels Hilberts Nullstellensatz). In meinem Vortrag gebe ich einen Überblick über diese Ansätze und den aktuellen Forschungsstand.

Prof. Dr. Jan Steffen Müller (Universität Oldenburg):
Diophantische Gleichungen und Computeralgebra

Eine diophantische Gleichung ist eine Gleichung der Form f = 0, wobei f = f(x_1,…,x_n) ein Polynom mit ganzzahligen Koeffizienten ist. Matiyasevich hat bewiesen, dass es keinen Algorithmus geben kann, mit dem die Lösbarkeit beliebiger diophantischer Gleichungen in ganzen Zahlen entschieden werden kann.  Für eine gegebene diophantische Gleichung kann aber trotzdem nach der Lösbarkeit in ganzen (oder rationalen) Zahlen sowie nach der Struktur der ganzzahligen (oder rationalen) Lösungen gefragt werden.  In diesem Vortrag werde ich einen Überblick darüber geben, wie geometrische Methoden und Computeralgebra für solche Fragestellungen genutzt werden können.

Severin Neumann (Universität Passau):
Parallele und verteilte Algorithmen zur Berechnung von Gröbnerbasen

Parallelisierung ermöglicht es einen Algorithmus auf eine Vielzahl von Prozessoren und Computern zu verteilen. Auch für die komplexe Berechnung von Gröbnerbasen kann diese Technik verwendet werden. In diesem Vortrag wird ausgehend von Faugères F4 Algorithmus zunächst gezeigt, wie auf einem Multiprozessorsystem eine Gröbnerbasis um ein Vielfaches schneller berechnet werden kann. Im nächsten Schritt wird eine weitere Variante dieses Verfahrens vorgestellt, die es ermöglicht eine weitere Beschleunigung auf Mehrcomputersystemen zu erzielen. Im Rahmen des Vortrags wird auch auf verschiedene Werkzeuge zur Parallelisierung eingegangen, wie beispielsweise SSE, OpenMP, Intel TBB und MPI, um einen Einblick in die Möglichkeiten, Herausforderungen und Grenzen der Parallelisierung zu bieten. Die Implementierung des vorgestellten Verfahrens ist als OpenSource-Projekt verfügbar unter https://github.com/svrnm/parallelGBC

Dr. Jens Zumbrägel (TU Dresden):
Neue Algorithmen für das diskrete Logarithmusproblem in Körpern kleiner Charakteristik

Zahlreiche Kryptosysteme beruhen auf der Schwierigkeit, das diskrete Logarithmusproblem (DLP) in einem endlichen Körper zu lösen, und so ist die Entwicklung von DLP-Algorithmen ein seit Jahrzehnten bedeutender Forschungsgegenstand.  In diesem Vortrag stelle ich die verschiedenen Algorithmen für das DLP vor und gehe auf neue Index-Calculus-Methoden ein, die insbesondere in Erweiterungskörpern kleiner Charakteristik sehr effizient sind. Die neuen Algorithmen resultieren sowohl auf theoretischer Seite in kürzeren asymptotischen Laufzeiten als auch bei praktischen Implementierungen in beträchtlichen neuen DLP-Rekorden; sie beeinträchtigen außerdem die Sicherheit von einigen paarungsbasierten Kryptosystemen.