Treffer: An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves
Title:
An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves
Authors:
Contributors:
Lithe and fast algorithmic number theory (LFANT), Institut de Mathématiques de Bordeaux (IMB), Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de l'Université de Bordeaux, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Cryptology, Arithmetic: Hardware and Software (CARAMEL), Centre Inria de l'Université de Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Source:
Journal of Cryptology. 24:24-41
Publisher Information:
CCSD; Springer Verlag, 2011.
Publication Year:
2011
Collection:
collection:CNRS
collection:INRIA
collection:IMB
collection:INRIA-BORDEAUX
collection:INSMI
collection:INRIA_TEST
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:TESTBORDEAUX
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA-ALGO-TEST5
collection:LORIA
collection:LORIA-ALGO
collection:UNIVERSITE-BORDEAUX
collection:AM2I-UL
collection:IMB12
collection:INRIA
collection:IMB
collection:INRIA-BORDEAUX
collection:INSMI
collection:INRIA_TEST
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:TESTBORDEAUX
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA-ALGO-TEST5
collection:LORIA
collection:LORIA-ALGO
collection:UNIVERSITE-BORDEAUX
collection:AM2I-UL
collection:IMB12
Subject Terms:
discrete logarithm, algebraic curve, subexponentiality, function field sieve, ACM: G.: Mathematics of Computing, G.4: MATHEMATICAL SOFTWARE, G.4.0: Algorithm design and analysis, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.1: Numerical Algorithms and Problems, F.2.1.4: Number-theoretic computations (e.g., factoring, primality testing), [INFO.INFO-CR]Computer Science [cs], Cryptography and Security [cs.CR], [MATH.MATH-AG]Mathematics [math], Algebraic Geometry [math.AG]
Original Identifier:
ARXIV: 0905.2177
HAL:
HAL:
Document Type:
Zeitschrift
article<br />Journal articles
Language:
English
ISSN:
0933-2790
1432-1378
1432-1378
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/0905.2177; info:eu-repo/semantics/altIdentifier/doi/10.1007/s00145-010-9057-y
DOI:
10.1007/s00145-010-9057-y
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00383941v2
Database:
HAL
Weitere Informationen
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.