An L(1/3) algorithm for the discrete logarithm problem in low degree curves
主 题: An L(1/3) algorithm for the discrete logarithm problem in low degree curves
报告人: Andreas Enge (INRIA, CNRS, Université de Bordeaux)
时 间: 2012-05-29 15:10-16:10
地 点: 理教301
Starting with the work by Adleman, DeMarrais and Huang almost twenty years ago, it has been well-established that the discrete logarithm problem in Jacobians of curves of high genus over finite fields is easier to solve than in elliptic curves of the same size. The algorithms for computing discrete logarithms in high genus curves have a complexity of L (1/2, c). This is in contrast on one hand to elliptic curves, for which so far only exponential algorithms are known except for some rare special cases, but also to the computation of discrete logarithms in finite prime fields, for which the number field sieve yields a more efficient algorithm in L (1/3, c). I present the first subexponential algorithm of complexity L (1/3, c) that we have found to compute discrete logarithms in a class of algebraic curves over finite fields, characterised by a relatively low degree compared to their genus.
