Extended Tower Number Field Sieve: A New Complexity for Medium Prime Case.
Taechan Kim · 2015
Abstract. In this paper, we extend the tower number field sieve (TNFS) proposed by Barbulescu, Gaudry, and Kleinjung in Asaicrypt 2015. Our generalization based on the JLSV algorithm (by Joux, Lercier, Smart, and Vercautern, Crypto 2006) shows that one can solve the discrete logarithm over the field FQ: = Fpn in time complexity, LQ(1/3, (64/9) 1/3), for p = LQ(`p) with some `p> 1/3. This should be compared that the previous NFS algorithms only assures this bound either when `p> 2/3 (the JLSV algorithm) or when p is of special form when 1/3 < `p < 2/3 (by Joux and Pierrot, Pairing 2013). Even more, when we apply some variants (such as the multiple number field sieve or the special number field sieve) to our algorithm, then we show that the above complexity is further improved.