Faster initial splitting for small characteristic composite extension degree fields Abstract   Let p be a small prime and    n      n    1      n    2    u003e  1    be a composite integer. For the function field sieve algorithm applied to      F      p    n       , Guillevic (2019) had proposed an algorithm for initial splitting of the target in the individual logarithm phase. This algorithm generates polynomials and tests them for Bsmoothness for some appropriate value of B. The amortised cost of generating each polynomial is    O  (    n    2    2    )    multiplications over      F      p      n    1         . In this work, we propose a new algorithm for performing the initial splitting which also generates and tests polynomials for Bsmoothness. The advantage over Guillevic splitting is that in the new algorithm, the cost of generating a polynomial is    O  (  n    log    p    xe2x81xa1  (  1    xcfx80  )  )    multiplications in      F    p     , where xcfx80 is the relevant smoothness probability.

Refined analysis to the extended tower number field sieve Abstract   The hardness of discrete logarithm problem over finite fields is the security foundation of many cryptographic protocols. When the characteristic of the finite field is medium or large, the stateofart algorithms for solving the corresponding problem are the number field sieve and its variants. In 2016, Kim and Barbulescu presented the extended tower number field sieve, which achieves a new complexity in the medium prime case and imposes a new estimation of the security of concrete parameters in certain cryptosystems such as pairingbased cryptosystems. In this paper, a refined analysis to this algorithm is given as follows.  xe2x80x93   Firstly, a uniform formula is given for the total complexity of the extended tower number field sieve. For a given polynomial selection method, this formula can directly give the complexity in this case.   xe2x80x93   Then, a method is proposed to improve the computation in the smoothing phase by exploring subfield structures when the extension degree is composite.   xe2x80x93   At last, the complexity of the descent phase is analyzed when sieving over degreeone polynomials and highdegree polynomials respectively and it is shown still negligible compared to the improved smoothing phase.