An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves
ENGE, Andreas
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
ENGE, Andreas
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
< Leer menos
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Idioma
en
Article de revue
Este ítem está publicado en
Journal of Cryptology. 2011, vol. 24, p. 24-41
Springer Verlag
Resumen en inglés
We present an algorithm for solving the discrete logarithm problem in Jacobians of families of plane curves whose degrees in $X$ and $Y$ are low with respect to their genera. The finite base fields $\FF_q$ are arbitrary, ...Leer más >
We present an algorithm for solving the discrete logarithm problem in Jacobians of families of plane curves whose degrees in $X$ and $Y$ are low with respect to their genera. The finite base fields $\FF_q$ are arbitrary, but their sizes should not grow too fast compared to the genus. For such families, the group structure and discrete logarithms can be computed in subexponential time of $L_{q^g}(1/3, O(1))$. The runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve.< Leer menos
Palabras clave en inglés
discrete logarithm
algebraic curve
subexponentiality
function field sieve
Orígen
Importado de HalCentros de investigación