Function field sieve

In mathematics the Function Field Sieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field. It has heuristic subexponential complexity. Leonard Adleman developed it in 1994 ^[1] and then elaborated it together with M. D. Huang in 1999.^[2] Previous work includes the work of D. Coppersmith ^[3] about the DLP in fields of characteristic two.

The discrete logarithm problem in a finite field consists of solving the equation ${\displaystyle a^{x}=b}$ for ${\displaystyle a,b\in \mathbb {F} _{p^{n}}}$, ${\displaystyle p}$ a prime number and ${\displaystyle n}$ an integer. The function ${\displaystyle f:\mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},a\mapsto a^{x}}$ for a fixed ${\displaystyle x\in \mathbb {N} }$ is a one-way function used in cryptography. Several cryptographic methods are based on the DLP such as the Diffie-Hellman key exchange, the El Gamal cryptosystem and the Digital Signature Algorithm.

Number theoretical background

Function Fields

Let ${\displaystyle C(x,y)}$ be a polynomial defining an algebraic curve over a finite field ${\displaystyle \mathbb {F} _{p}}$. A function field may be viewed as the field of fractions of the affine coordinate ring ${\displaystyle \mathbb {F} _{p}[x,y]/(C(x,y))}$, where ${\displaystyle (C(x,y))}$ denotes the ideal generated by ${\displaystyle C(x,y)}$. This is a special case of an algebraic function field. It is defined over the finite field ${\displaystyle \mathbb {F} _{p}}$ and has transcendence degree one. The transcendent element will be denoted by ${\displaystyle 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.^[4] This correspondence is frequently used in the Function Field Sieve algorithm.

Divisors

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

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

Method

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 ${\displaystyle b}$.

Functions that decompose into irreducible function of degree smaller than some bound ${\displaystyle B}$ are called ${\displaystyle 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 ${\displaystyle S=\{g(x)\in \mathbb {F} _{p}[x]\mid {\text{ irreductible with }}\deg(g)<B\}}$ is called the factor base. A pair of functions ${\displaystyle (r,s)}$ is doubly-smooth if ${\displaystyle rm+s}$ and ${\displaystyle N(ry+s)}$ are both smooth, where ${\displaystyle N(\cdot ,\cdot )}$ is the norm of an element of ${\displaystyle K}$ over ${\displaystyle \mathbb {F} _{p}}$, ${\displaystyle m\in \mathbb {F} _{p}[x]}$ is some parameter and ${\displaystyle ry+s}$ is viewed as an element of the function field of ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle f}$ of degree ${\displaystyle n}$, a function ${\displaystyle m\in \mathbb {F} _{p}[x]}$ and a curve ${\displaystyle C(x,y)}$ of given degree ${\displaystyle d}$ such that ${\displaystyle C(x,m)\equiv 0{\text{ mod }}f}$. Here ${\displaystyle n}$ is the power in the order of the base field ${\displaystyle \mathbb {F} _{p^{n}}}$. Let ${\displaystyle K}$ denote the function field defined by ${\displaystyle C}$.

This leads to an isomorphism ${\displaystyle \mathbb {F} _{p^{n}}\simeq \mathbb {F} _{p}[x]/f}$ and a homomorphism

Using the isomorphism each element of ${\displaystyle \mathbb {F} _{p^{n}}}$ can be considered as a polynomial in ${\displaystyle \mathbb {F} _{p}[x]/f}$.

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

Sieving

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

One considers functions of the form ${\displaystyle f=(rm+s)N(ry+s)}$, then divides ${\displaystyle f}$ by any ${\displaystyle g\in S}$ as many times as possible. Any ${\displaystyle f}$ that is reduced to one in this process is ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle v_{1},v_{2},...}$ of ${\displaystyle K}$ that lie over them and surrogate functions ${\displaystyle \alpha _{1},\alpha _{2},...}$ that correspond to the places. A surrogate function ${\displaystyle \alpha _{i}\in K}$ corresponding to a place ${\displaystyle v_{i}}$ satisfies ${\displaystyle {\text{div}}(\alpha _{i})=h(v_{i}-f_{v_{i}}u)}$ where ${\displaystyle h}$ is the class number of ${\displaystyle K}$ and ${\displaystyle u}$ is any fixed discrete valuation with ${\displaystyle f_{u}=1}$. The function defined this way is unique up to a constant in ${\displaystyle \mathbb {F} _{p}}$.

By the definition of a divisor ${\textstyle {\text{div}}(ry+s)=\sum a_{i}v_{i}}$ for ${\displaystyle a_{i}=v_{i}(ry+s)}$. Using this and the fact that ${\textstyle \sum a_{i}f_{v_{i}}=\deg({\text{div}}(ry+s))=0}$ we get the following expression:

${\displaystyle {\text{div}}((ry+s)^{h})=\sum ha_{i}v_{i}=\sum ha_{i}v_{i}-\sum ha_{i}f_{v_{i}}v+hv\sum a_{i}f_{v_{i}}=\sum a_{i}h(v_{i}-f_{v_{i}}v))={\text{div}}(\prod \alpha _{i}^{a_{i}})}$

where ${\displaystyle v}$ is any valuation with ${\displaystyle f_{v}=1}$. Then, using the fact that the divisor of a surrogate function is unique up to a constant, one gets

${\displaystyle (ry+s)^{h}=c\prod \alpha _{i}^{a_{i}}{\text{ for some }}c\in F_{p}^{*}}$

${\displaystyle \implies \phi ((ry+s)^{h})=\phi (c)\prod \phi (\alpha _{i})^{a_{i}}}$

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

${\displaystyle \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 ${\displaystyle \log _{*}(x)}$. It is defined by the equation ${\displaystyle a^{\log _{*}(x)}=ux}$ for some unit ${\displaystyle u\in \mathbb {F} _{p}}$.

${\displaystyle \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 ${\displaystyle h_{1}}$ is the inverse of ${\displaystyle h}$ modulo ${\displaystyle (p^{n}-1)/(p-1)}$.

The expressions ${\displaystyle h_{1}\log _{*}(\phi (\alpha _{i}))}$ and the logarithms ${\displaystyle \log _{*}(g)}$ are unknown. Once enough equations of this form are found, a linear system can be solved to find ${\displaystyle \log _{*}(g)}$ for all ${\displaystyle g\in S}$. Taking the whole expression ${\displaystyle h_{1}log_{*}(\phi (\alpha _{i}))}$ as an unknown helps to gain time, since ${\displaystyle h}$, ${\displaystyle h_{1}}$, ${\displaystyle \alpha _{i}}$ or ${\displaystyle \phi (\alpha _{i})}$ don't have to be computed. Eventually for each ${\displaystyle g\in S}$ the unit corresponding to the restricted discrete logarithm can be calculated which then gives ${\displaystyle \log _{a}(g)=\log _{*}(g)-\log _{a}(u)}$.

Reduction step

First ${\displaystyle a^{l}b}$ mod ${\displaystyle f}$ are computed for a random ${\displaystyle l<n}$. With sufficiently high probability this is ${\displaystyle {\sqrt {nB}}}$-smooth, so one can factor it as ${\displaystyle a^{l}b=\prod b_{i}}$ for ${\displaystyle b_{i}\in \mathbb {F} _{p}[x]}$ with ${\displaystyle \deg(b_{i})<{\sqrt {nB}}}$. Each of these polynomials ${\displaystyle b_{i}}$ can be reduced to polynomials of smaller degree using a generalization of the Coppersmith method.^[2] We can reduce the degree until we get a product of ${\displaystyle B}$-smooth polynomials. Then, taking the logarithm to the base ${\displaystyle a}$, we can eventually compute

${\displaystyle \log _{a}(b)=\sum _{g_{i}\in S}\log _{a}(g_{i})-l}$, which solves the DLP.

Complexity

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

${\displaystyle \exp \left(\left({\sqrt[{3}]{\frac {32}{9}}}+o(1)\right)(\ln p)^{\frac {1}{3}}(\ln \ln p)^{\frac {2}{3}}\right)=L_{p}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {32}{9}}}\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 ${\displaystyle (rm+s)N(ry+s)}$ behave like random numbers in a given range.

Comparison with other methods

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.^[5] 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 ${\displaystyle \mathbb {F} _{p^{n}}}$ as well.

The Number Field Sieve for the DLP in ${\displaystyle \mathbb {F} _{p^{n}}}$ has a complexity of ${\displaystyle L_{p}[1/3,(64/9)^{1/3}+o(1)]}$ ^[6] and is therefore slightly slower than the best performance of the Function Field Sieve. However, it is faster than the Function Field Sieve when ${\displaystyle n<<(\log(p))^{1/2}}$. 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 ${\displaystyle L_{p}[1/2,{\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 ${\displaystyle B}$, so most of the computations can be done with smaller numbers.

See also

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

References