分野別セミナー

In this talk, 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( l_p) $with some$ l_p > 1/3 $. This should be compared that the previousNFS algorithms only assures this bound either when$ l_p > 2/3 $(the JLSV algorithm) or when p is of special form when $1/3 < l_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.