Function field sieve

{{main|Algebraic function field}}

Let $C(x,y)$ be a polynomial defining an algebraic curve over a finite field $\backslash mathbb\{F\}\_\{p\}$. A function field may be viewed as the field of fractions of the affine coordinate ring $\backslash mathbb\{F\}\_p[x,y]/(C(x,y))$, where $(C(x,y))$ denotes the ideal generated by $C(x,y)$. This is a special case of an algebraic function field. It is defined over the finite field $\backslash mathbb\{F\}\_p$ and has transcendence degree one. The transcendent element will be denoted by $x$.

There exist bijections between valuation rings in function fields and equivalence classes of places, as well as between valuation rings and equivalence classes of valuations.M. Fried and M. Jarden. In: "Field Arithmetic". vol. 11. (Jan. 2005). Chap. 2.1. DOI: 10.1007/b138352. This correspondence is frequently used in the Function Field Sieve algorithm.

A discrete valuation of the function field $K/\backslash mathbb\{F\}\_p$, namely a discrete valuation ring $\backslash mathbb\{F\}\_p\; \backslash subset\; O\; \backslash subset\; K$, has a unique maximal ideal $P$ called a prime of the function field. The degree of $P$ is $deg(P)\; =\; [O/P\; :\; \backslash mathbb\{F\}\_p]$ and we also define $f\_O\; =\; [O/P\; :\; \backslash mathbb\{F\}\_p]$.

A divisor is a $\backslash mathbb\{Z\}$-linear combination over all primes, so $d\; =\; \backslash sum\; \backslash alpha\_PP$ where $\backslash alpha\_P\; \backslash in\; \backslash mathbb\{Z\}$ and only finitely many elements of the sum are non-zero. The divisor of an element $x\; \backslash in\; K$ is defined as $\backslash text\{div\}(x)\; =\; \backslash sum\; v\_P(x)P$, where $v\_P$ is the valuation corresponding to the prime $P$.

The degree of a divisor is $\backslash deg(d)\; =\; \backslash sum\; \backslash alpha\_P\; \backslash deg(P)$.

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 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(\backslash cdot,\backslash cdot)$ is the norm of an element of $K$ over $\backslash mathbb\{F\}\_p$, $m\; \backslash in\; \backslash 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 $\backslash log\_a(b)$ as a combination of the logarithm we found before and thus solve the DLP.

The algorithm requires the following parameters: an irreducible function $f$ of degree $n$, a function $m\; \backslash in\; \backslash mathbb\{F\}\_p[x]$ and a curve $C(x,y)$ of given degree $d$ such that $C(x,m)\; \backslash equiv\; 0\; \backslash text\{\; mod\; \}\; f$. Here $n$ is the power in the order of the base field $\backslash mathbb\{F\}\_\{p^n\}$. Let $K$ denote the function field defined by $C$.

This leads to an isomorphism $\backslash mathbb\{F\}\_\{p^n\}\; \backslash simeq\; \backslash mathbb\{F\}\_p[x]/f$ and a homomorphism $$\backslash phi:\; \backslash mathbb\{F\}\_p[x,y]/C\; \backslash to\; \backslash mathbb\{F\}\_p[x]/f,\; y\; \backslash mapsto\; m.$$Using the isomorphism each element of $\backslash mathbb\{F\}\_\{p^n\}$ can be considered as a polynomial in $\backslash mathbb\{F\}\_p[x]/f$.

One also needs to set a smoothness bound $B$ for the factor base $S$.

In this step doubly-smooth pairs of functions $(r,s)\; \backslash in\; \backslash mathbb\{F\}\_p[x]\; \backslash times\; \backslash mathbb\{F\}\_p[x]$ are found.

One considers functions of the form $f\; =\; (rm+s)N(ry+s)$, then divides $f$ by any $g\; \backslash 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 $\backslash mathbb\{F\}\_p[x]$ but those functions can be factored into irreducible polynomials just as numbers can be factored into primes.

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 $\backslash alpha\_1,\; \backslash alpha\_2,\; ...$ that correspond to the places. A surrogate function $\backslash alpha\_i\; \backslash in\; K$ corresponding to a place $v\_i$ satisfies $\backslash text\{div\}(\backslash 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

$\backslash mathbb\{F\}\_p$.

By the definition of a divisor $\backslash text\{div\}(ry+s)\; =\; \backslash sum\; a\_i\; v\_i$ for $a\_i\; =\; v\_i(ry+s)$. Using this and the fact that $\backslash sum\; a\_i\; f\_\{v\_i\}\; =\; \backslash deg(\backslash text\{div\}(ry+s))\; =\; 0$ we get the following expression:

:$\backslash text\{div\}((ry\; +\; s)^h)\; =\; \backslash sum\; ha\_iv\_i\; =\; \backslash sum\; ha\_iv\_i\; -\; \backslash sum\; ha\_if\_\{v\_i\}v\; +\; hv\; \backslash sum\; a\_if\_\{v\_i\}\; =\; \backslash sum\; a\_ih(v\_i-f\_\{v\_i\}v)\; )\; =\; \backslash text\{div\}(\backslash prod\; \backslash 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\; \backslash prod\; \backslash alpha\_i^\{a\_i\}\; \backslash text\{\; for\; some\; \}\; c\; \backslash in\; F\_p^*$

:$\backslash implies\; \backslash phi((ry+s)^h)\; =\; \backslash phi(c)\; \backslash prod\; \backslash phi(\backslash alpha\_i)^\{a\_i\}$

We now use the fact that $\backslash phi(ry+s)\; =\; rm+s$ and the known decomposition of this expression into irreducible polynomials. Let $e\_g$ be the power of $g\; \backslash in\; S$ in this decomposition. Then

:$\backslash prod\_\{g\; \backslash in\; S\}\; g^\{he\_g\}\; \backslash equiv\; \backslash phi(c)\; \backslash prod\; \backslash phi(\backslash alpha\_i)^\{a\_i\}\; \backslash text\{\; mod\; \}\; f$

Here we can take the discrete logarithm of the equation up to a unit. This is called the restricted discrete logarithm $\backslash log\_*(x)$. It is defined by the equation $a^\{\backslash log\_*(x)\}\; =\; ux$ for some unit $u\; \backslash in\; \backslash mathbb\{F\}\_p$.

:$\backslash sum\_\{g\; \backslash in\; S\}\; e\_g\; \backslash log\_*g\; \backslash equiv\; \backslash sum\; a\_i\; h\_1\; \backslash log\_*(\backslash phi(\backslash alpha\_i))\; \backslash 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\; \backslash log\_*\; (\backslash phi(\backslash alpha\_i))$ and the logarithms $\backslash log\_*(g)$ are unknown. Once enough equations of this form are found, a linear system can be solved to find $\backslash log\_*(g)$ for all $g\; \backslash in\; S$. Taking the whole expression $h\_1\; log\_*\; (\backslash phi(\backslash alpha\_i))$ as an unknown helps to gain time, since $h$, $h\_1$, $\backslash alpha\_i$ or $\backslash phi(\backslash alpha\_i)$ don't have to be computed.

Eventually for each $g\; \backslash in\; S$ the unit corresponding to the restricted discrete logarithm can be calculated which then gives $\backslash log\_a(g)\; =\; \backslash log\_*(g)\; -\; \backslash log\_a(u)$.

First $a^lb$ mod $f$ are computed for a random . With sufficiently high probability this is $\backslash sqrt\{nB\}$-smooth, so one can factor it as $a^lb\; =\; \backslash prod\; b\_i$ for $b\_i\; \backslash in\; \backslash mathbb\{F\}\_p[x]$ with . 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

:$\backslash log\_a(b)\; =\; \backslash sum\_\{g\_i\; \backslash in\; S\}\; \backslash log\_a(g\_i)\; -\; l$, which solves the DLP.

The Function Field Sieve is thought to run in subexponential time in

:$\backslash exp\backslash left(\; \backslash left(\backslash sqrt[3]\{\backslash frac\{32\}\{9\}\}\; +\; o(1)\backslash right)(\backslash ln\; p)^\{\backslash frac\{1\}\{3\}\}(\backslash ln\; \backslash ln\; p)^\{\backslash frac\{2\}\{3\}\}\backslash right)\; =L\_p\backslash left[\backslash frac\{1\}\{3\},\backslash sqrt[3]\{\backslash frac\{32\}\{9\}\}\backslash right]$

using the L-notation. There is no rigorous proof of this complexity since it relies on some heuristic assumptions. For example in the sieving step we assume that numbers of the form $(rm+s)N(ry+s)$ behave like random numbers in a given range.

There are two other well known algorithms that solve the discrete logarithm problem in sub-exponential time: the index calculus algorithm and a version of the Number Field Sieve.D. Gordon. "Discrete Logarithm in GF(P) Using the Number Field Sieve". In: Siam Journal on Discrete Mathematics - SIAMDM 6 (Feb. 1993), pp. 124-138. DOI: 10.1137/0406010. In their easiest forms both solve the DLP in a finite field of prime order but they can be expanded to solve the DLP in $\backslash mathbb\{F\}\_\{p^n\}$ as well.

The Number Field Sieve for the DLP in $\backslash mathbb\{F\}\_\{p^n\}$ has a complexity of $L\_p[1/3,\; (64/9)^\{1/3\}\; +\; o(1)]$ R. Barbulescu, P. Gaudry, T. Kleinjung. "The Tower Number Field Sieve". In: Advances in Cryptology – Asiacrypt 2015. Vol. 9453. Springer, May 2015. pp. 31-58 and is therefore slightly slower than the best performance of the Function Field Sieve. However, it is faster than the Function Field Sieve when . It is not surprising that there exist two similar algorithms, one with number fields and the other one with function fields. In fact there is an extensive analogy between these two kinds of global fields.

The index calculus algorithm is much easier to state than the Function Field Sieve and the Number Field Sieve since it does not involve any advanced algebraic structures. It is asymptotically slower with a complexity of $L\_p[1/2,\; \backslash sqrt\{2\}]$. The main reason why the Number Field Sieve and the Function Field Sieve are faster is that these algorithms can run with a smaller smoothness bound $B$, so most of the computations can be done with smaller numbers.

• Algebraic function field
• Number field sieve
• Index calculus algorithm

{{reflist}}

{{Number-theoretic algorithms}}

Category:Field (mathematics)