We introduce a new variant of the number field sieve algorithm for discrete logarithms in F_(p~n) called exTNFS. The most important modification is done in the polynomial selection step, which determines the cost of the whole algorithm: if one knows how to select good polynomials to tackle discrete logarithms in F_(p~κ), exTNFS allows to use this method when tackling F_(p~(ηκ)) whenever gcd(η, κ) = 1. This simple fact has consequences on the asymptotic complexity of NFS in the medium prime case, where the complexity is reduced from L_Q(1/3,(96/9)~(1/3)) to L_Q(1/3, (48/9)~(1/3), Q = p~n, respectively from L_Q(1/3,2.15) to L_Q(1/3, 1.71) if multiple number fields are used. On the practical side, exTNFS can be used when n = 6 and n = 12 and this requires to updating the keysizes used for the associated pairing-based cryptosystems.
展开▼
