The Function Field Sieve algorithm consists of a precomputation where the discrete logarithms of irreducible polynomials of small degree are found and a reduction step where they are combined to the logarithm of b. Functions that decompose into irreducible function of degree smaller than some bound B are called B-smooth. This is analogous to the definition of a
smooth number and such functions are useful because their decomposition can be found relatively fast. The set of those functions S = \{g(x) \in \mathbb{F}_p[x] \mid \text{ irreductible with } \deg(g) is called the factor base. A pair of functions (r,s) is doubly-smooth if rm + s and N(ry+s) are both smooth, where N(\cdot,\cdot) is the norm of an element of K over \mathbb{F}_p, m \in \mathbb{F}_p[x] is some parameter and ry+s is viewed as an element of the function field of C. The sieving step of the algorithm consists of finding doubly-smooth pairs of functions. In the subsequent step we use them to find linear relations including the logarithms of the functions in the decompositions. By solving a linear system we then calculate the logarithms. In the reduction step we express \log_a(b) as a combination of the logarithm we found before and thus solve the DLP.
Precomputation Parameter selection The algorithm requires the following parameters: an irreducible function f of degree n, a function m \in \mathbb{F}_p[x] and a curve C(x,y) of given degree d such that C(x,m) \equiv 0 \text{ mod } f. Here n is the power in the order of the base field \mathbb{F}_{p^n}. Let K denote the function field defined by C. This leads to an isomorphism \mathbb{F}_{p^n} \simeq \mathbb{F}_p[x]/f and a homomorphism \phi: \mathbb{F}_p[x,y]/C \to \mathbb{F}_p[x]/f, y \mapsto m. Using the isomorphism each element of \mathbb{F}_{p^n} can be considered as a polynomial in \mathbb{F}_p[x]/f. One also needs to set a smoothness bound B for the factor base S.
Sieving In this step doubly-smooth pairs of functions (r,s) \in \mathbb{F}_p[x] \times \mathbb{F}_p[x] are found. One considers functions of the form f = (rm+s)N(ry+s), then divides f by any g \in S as many times as possible. Any f that is reduced to one in this process is B-smooth. To implement this,
Gray code can be used to efficiently step through multiples of a given polynomial. This is completely analogous to the sieving step in other sieving algorithms such as the
Number Field Sieve or the
index calculus algorithm. Instead of numbers one sieves through functions in \mathbb{F}_p[x] but those functions can be factored into irreducible polynomials just as numbers can be factored into primes.
Finding linear relations This is the most difficult part of the algorithm, involving function fields,
places and divisors as defined above. The goal is to use the doubly-smooth pairs of functions to find linear relations involving the discrete logarithms of elements in the factor base. For each irreducible function in the factor base we find places v_1, v_2, ... of K that lie over them and surrogate functions \alpha_1, \alpha_2, ... that correspond to the places. A surrogate function \alpha_i \in K corresponding to a place v_i satisfies \text{div}(\alpha_i)=h(v_i-f_{v_i}u) where h is the class number of K and u is any fixed discrete valuation with f_u=1. The function defined this way is unique up to a constant in \mathbb{F}_p. By the definition of a divisor \text{div}(ry+s) = \sum a_i v_i for a_i = v_i(ry+s). Using this and the fact that \sum a_i f_{v_i} = \deg(\text{div}(ry+s)) = 0 we get the following expression: :\text{div}((ry + s)^h) = \sum ha_iv_i = \sum ha_iv_i - \sum ha_if_{v_i}v + hv \sum a_if_{v_i} = \sum a_ih(v_i-f_{v_i}v) ) = \text{div}(\prod \alpha_i^{a_i}) where v is any valuation with f_v = 1. Then, using the fact that the divisor of a surrogate function is unique up to a constant, one gets :(ry+s)^h = c \prod \alpha_i^{a_i} \text{ for some } c \in F_p^* :\implies \phi((ry+s)^h) = \phi(c) \prod \phi(\alpha_i)^{a_i} We now use the fact that \phi(ry+s) = rm+s and the known decomposition of this expression into irreducible polynomials. Let e_g be the power of g \in S in this decomposition. Then : \prod_{g \in S} g^{he_g} \equiv \phi(c) \prod \phi(\alpha_i)^{a_i} \text{ mod } f Here we can take the discrete logarithm of the equation up to a unit. This is called the restricted discrete logarithm \log_*(x). It is defined by the equation a^{\log_*(x)} = ux for some unit u \in \mathbb{F}_p. : \sum_{g \in S} e_g \log_*g \equiv \sum a_i h_1 \log_*(\phi(\alpha_i)) \text{ mod } (p^n-1)/(p-1), where h_1 is the inverse of h modulo (p^n-1)/(p-1). The expressions h_1 \log_* (\phi(\alpha_i)) and the logarithms \log_*(g) are unknown. Once enough equations of this form are found, a linear system can be solved to find \log_*(g) for all g \in S. Taking the whole expression h_1 log_* (\phi(\alpha_i)) as an unknown helps to gain time, since h, h_1, \alpha_i or \phi(\alpha_i) don't have to be computed. Eventually for each g \in S the unit corresponding to the restricted discrete logarithm can be calculated which then gives \log_a(g) = \log_*(g) - \log_a(u).
Reduction step First a^lb mod f are computed for a random l . With sufficiently high probability this is \sqrt{nB} -smooth, so one can factor it as a^lb = \prod b_i for b_i \in \mathbb{F}_p[x] with \deg(b_i) . Each of these polynomials b_i can be reduced to polynomials of smaller degree using a generalization of the
Coppersmith method. We can reduce the degree until we get a product of B-smooth polynomials. Then, taking the logarithm to the base a, we can eventually compute :\log_a(b) = \sum_{g_i \in S} \log_a(g_i) - l, which solves the DLP. == Complexity ==