An L(1/3) algorithm for discrete logarithm computation and principality testing in certain number fields

2012/04/05 by Biasse, Jean-François
#58F17 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Primary: 58F15 #Secondary: 53C35

paper · doi:10.48550/arxiv.1204.1292

Abstract

We analyse the complexity of solving the discrete logarithm problem and of testing the principality of ideals in a certain class of number fields. We achieve the subexponential complexity in O(L(1/3,O(1))) when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge, Gaudry and Thomé in the context of algebraic curves over finite fields.

Related

• An L(1/3) algorithm for ideal class group and regulator computation in certain number fields
• A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic
• An L (1/3) Discrete Logarithm Algorithm for Low Degree Curves
• New algorithm for the discrete logarithm problem on elliptic curves
• A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic