On the computation of discrete logarithms in finite prime fields
Damian Weber · Publications of the UdS (Saarland University) · 1997
In this thesis we write about practical experience when solving congruences of the form a^x = b mod p, a,b,p,x Element Z, p prime. This is referred to as the discrete logarithm problem in (Z/pZ)*. Many cryptographic protocols such as signature schemes, message encryption, key exchange and identification depend on the difficulty of this problem. We are concerned with the practicability of different index calculus variants, which are the asymtotically fastest known algorithms at present to solve this problem. We present computations for p having up to 85 decimal digits. We include a partial solution to McCurley's challenge with a 129-digit p, which has a special form. In dieser Arbeit berichten wir uber praktische Erfahrungen mit der Losung von Kongruenzen der Form a^x = b mod p, a,b,p,x Element Z, p Primzahl. Dies ist das Problem der Diskreten Logarithmen in (Z/pZ)*. Zahlreiche kryptographische Protokolle wie digitale Unterschriften, Verschlusselung von Nachrichten, Schlusselaustausch und Identifikation basieren auf der Schwierigkeit dieses Problems. In dieser Arbeit befassen wir uns mit der Praktikabilitat verschiedener Index-Calculus Verfahren, die zur Zeit die asymptotisch schnellsten Algorithmen liefern, um dieses Problem zu losen. Wir prasentieren Berechnungen mit bis zu 85-stelligem p und legen eine partielle Losung zu McCurley's Challenge vor, die ein 129-stelliges p von spezieller Form benutzt.