The Special Function Field Sieve
Oliver Schirokauer · SIAM Journal on Discrete Mathematics · 2002
Let p be a prime number and n a positive integer, and let q=p n . Adleman and Huang [Inform. and Comput., 151 (1999), pp. 5--16] have described a version of the function field sieve which is conjectured to compute a logarithm in the field of q elements in expected time L q [1/3;(32/9) 1/3 +o(1)], where L q [s;c]=exp(c(log q) s (log log q) 1-s ) and the o(1) is for $q\to\infty$ under the constraint that p 6 \leq n$. In this paper, we present a modification of their method which runs conjecturally in expected time L q [1/3;(32/9) 1/3 +o(1)] so long as $q\to\infty$ with $p\leq n^{o(\sqrt{n})}$. The technique we use can also be applied to the special number field sieve and results in an algorithm which, in expected time L p [1/3;(32/9) 1/3 +o(1)], is conjectured to compute a logarithm in a prime field whose cardinality p is of the form $r^e-s$, with r and s small in absolute value.