International Association
for Cryptologic Research

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 $\\F_Q := \\F_{p^n}$ in time complexity,

L_Q( 1/3, (64/9)^{1/3} ), for p = L_Q( \\ell_p) with some \\ell_p > 1/3.

This should be compared that the previous NFS algorithms only assures

this bound either when $\\ell_p > 2/3$ (the JLSV algorithm) or

when $p$ is of special form when $1/3 < \\ell_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.