Lösen großer dünnbesetzter Gleichungssysteme über endlichen Primkörpern

Abstract

Die kryptographische Sicherheit der relevantesten Public Key Verfahren hängt von der Schwierigkeit des Faktorisierungsproblems bzw. des Diskreten Logarithmen (DL) Problems in endlichen Primkörpern ab. Sowohl bei allgemeinen Faktorisierungsverfahren als auch bei sogenannten Index-Calculus-Verfahren zur Bestimmung diskreter Logarithmen stellt das Lösen eines großen dünnbesetzten Gleichungssystems einen wichtigen Teil der Berechnung dar. In dieser Arbeit wird ein Gleichungslöser vorgestellt, der erfolgreich beim Lösen großer dünnbesetzter Gleichungssysteme über endlichen Primkörpern eingesetzt wurde. Er wurde beim Aufstellen des aktuellen Weltrekords eingesetzt und besteht aus 3 Teilen: - einer Modifikation der Double Large Prime Variante des Number Field Sieve, - einem Preprocessingschritt, der aufbauend auf Ideen der strukturierten Gaußelimination die Laufzeit des Lanczos Verfahrens minimiert und - einer (sequentiellen bzw. parallelen) Implementierung des Lanczos Verfahrens.

There are numerous crypto-systems whose security is based on the difficulty of factoring integers and solvind the discrete logarithm (DL)problem in finite fields. One of the main computational problems that occur in general factoring and DL-algorithms is to solve a sparse huge system of linear equations over a finite field. In this thesis a solver that was successfully used in a computation of discrete logarithms which is the current world record. It consists of three parts:- A modification of the Double Large Prime Variation for the Number Field Sieve. - A reprocessing step which minimizes the running time of the Lanczos algorithm. It is based on the ideas of the Structured Gaussian Elimination. - A sequential and a parrallel implementation of the Lanczos algorithm.