On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation

Stéphane Ballet; Nicolas Baudru; Alexis Bonnecaze; Mila Tukumuli

doi:10.1016/j.crma.2017.06.002

L'algorithme de multiplication dans les corps finis de Chudnovsky a une complexité bilinéaire uniformément linéaire en le degré de l'extension. Randriambololona a récemment généralisé cette méthode en introduisant l'asymétrie dans la procédure d'interpolation et en obtenant ainsi de nouvelles bornes sur la complexité bilinéaire. Dans cette note, nous décrivons la construction de cette méthode asymétrique sans évaluation dérivée. Pour ce faire, nous traduisons cette généralisation dans le langage des corps de fonctions algébriques, et nous donnons une stratégie de construction et d'implantation.

The Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity uniformly linear with respect to the degree of the extension. Recently, Randriambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. In this note, we describe the construction of this asymmetric method without derived evaluation. To do this, we translate this generalization into the language of algebraic function fields and we give a strategy of construction and implementation.

1 Introduction

Let q be a prime power, $F_{q}$ the finite field with q elements and $F_{q^{n}}$ the degree n extension of $F_{q}$ . Among all algorithms of multiplications in $F_{q^{n}}$ , those based on the Chudnovsky–Chudnovsky [6] method are known to provide the lowest bilinear complexity. This method is based on interpolation on algebraic curves defined over a finite field and provides a bilinear complexity, which is linear in n. The original algorithm uses only points of degree 1, with multiplicity 1. Ballet and Rolland [4,5] and Arnaud [1] improved the algorithm, introducing interpolation at points of higher degree or higher multiplicity. The symmetry of the original construction involves 2-torsion points that represent an obstacle to the improvement of upper bilinear complexity bounds. To eliminate this difficulty, Randriambololona [8] allowed asymmetry in the interpolation procedure, and then Pieltant and Randriambololona [7] derived new bounds, uniform in q, of the bilinear complexity. Unlike symmetric constructions, no effective implementation of this asymmetric construction has been done yet. When $g = 1$ , it is known [3] that an asymmetric algorithm can always be symmetrized. However, for greater values of g, it may not be the case. Thus, it is of interest to know an effective construction of this asymmetric algorithm. So far, no effective implementation has been proposed for such an algorithm.

1.1 Multiplication algorithm and tensor rank

The multiplication of two elements of $F_{q^{n}}$ is an $F_{q}$ -bilinear application from $F_{q^{n}} \times F_{q^{n}}$ onto $F_{q^{n}}$ . Then it can be considered as an $F_{q}$ -linear application from the tensor product $F_{q^{n}} \otimes_{F_{q}} F_{q^{n}}$ onto $F_{q^{n}}$ . Consequently, it can also be considered as an element $T_{m}$ of ${F_{q^{n}}}^{⋆} \otimes_{F_{q}} {F_{q^{n}}}^{⋆} \otimes_{F_{q}} F_{q^{n}}$ where ⋆ denotes the dual. When $T_{m}$ is written

T_{m} = \sum_{i = 1}^{r} x_{i}^{⋆} \otimes y_{i}^{⋆} \otimes c_{i},

(1)

where the r elements

x_{i}^{⋆}

as well as the r elements

y_{i}^{⋆}

are in the dual

{F_{q^{n}}}^{⋆}

F_{q^{n}}

while the r elements

c_{i}

are in

F_{q^{n}}

, the following holds for any

x, y \in F_{q^{n}}

x \cdot y = \sum_{i = 1}^{r} x_{i}^{⋆} (x) y_{i}^{⋆} (y) c_{i}

. The decomposition (1) is not unique.

Definition 1.1

Every expression $x \cdot y = \sum_{i = 1}^{r} x_{i}^{⋆} (x) y_{i}^{⋆} (y) c_{i}$ defines a bilinear multiplication algorithm $U$ of bilinear complexity $μ (U) = r$ . Such an algorithm is said symmetric if $x_{i} = y_{i}$ for all i.

Definition 1.2

The minimal number of summands in a decomposition of the tensor $T_{m}$ of the multiplication is called the bilinear complexity (resp. symmetric bilinear complexity) of the multiplication and is denoted by $μ_{q} (n)$ (resp. $μ_{q}^{s y m} (n)$ ):

μ_{q} (n) = \min_{U} μ (U)

where

U

is running over all bilinear multiplication algorithms (resp. all bilinear symmetric multiplication algorithms) in

F_{q^{n}}

over

F_{q}

1.2 Organisation of the note

In Section 2, we give an explicit translation of the generalization of the Chudnovsky algorithm given by Randriambololona [8, Theorem 3.5]. Then in Section 3, by defining a new design of this algorithm, we give a strategy of construction and implementation. In particular, thanks to a suitable representation of the Riemann–Roch spaces, we present the first construction of asymmetric effective algorithms of multiplication in finite fields. These algorithms are tailored to hardware implementation and they allow computations to be parallelized while maintaining a low number of bilinear multiplications. In Section 4, we give an analysis of the not asymptotical complexity of this algorithm.

2 Multiplication algorithms of type Chudnovsky: generalization of Randriambololona

In this section, we present a generalization of Chudnovsky-type algorithms, introduced in [8, Theorem 3.5] by Randriambololona, which is possibly asymmetric. Since our aim is to describe explicitly the effective construction of this asymmetric algorithm, we transform the representation of this algorithm, initially made in the abstract geometrical language, in the more explicit language of algebraic function fields.

Let $F / F_{q}$ be an algebraic function field over the finite field $F_{q}$ of genus $g (F)$ . We denote by $N_{1} (F / F_{q})$ the number of places of degree one of F over $F_{q}$ . If D is a divisor, $L (D)$ denotes the Riemann–Roch space associated with D. We denote by $O_{Q}$ the valuation ring of the place Q and by $F_{Q}$ its residue class field $O_{Q} / Q$ , which is isomorphic to $F_{q^{\deg Q}}$ , where $\deg Q$ is the degree of the place Q.

In the framework of algebraic function fields, the result [8, Theorem 3.5] of Randriambololona can be stated as in Theorem 2.1. Note that we do not take into account derived evaluations, since we are not interested in asymptotic results. It means that we describe this asymmetric algorithm with the divisor $G = P_{1} + \dots + P_{N}$ where the $P_{i}$ are pairwise distinct closed points of degree $\deg P_{i} = d_{i}$ .

Let us define the following Hadamard product in $F_{q^{l_{1}}} \times F_{q^{l_{2}}} \times \dots \times F_{q^{l_{N}}}$ , where the $l_{i}$ 's denote positive integers, by $(u_{1}, \dots, u_{N}) ⊙ (v_{1}, \dots, v_{N}) = (u_{1} v_{1}, \dots, u_{N} v_{N})$ .

Theorem 2.1

Let $F / F_{q}$ be an algebraic function field of genus g over $F_{q}$ . Suppose that there exists a place Q of degree n. Let $P = {P_{1}, \dots, P_{N}}$ be a set of N places of arbitrary degree not containing the place Q. Suppose that there exist two effective divisors $D_{1}, D_{2}$ of $F / F_{q}$ such that:

(i) the place Q and the places of $P$ are not in the support of the divisors $D_{1}$ and $D_{2}$ ;
(ii) the natural evaluation maps $E_{i}$ for $i = 1, 2$ defined as follows are surjective
$E_{i} : {\begin{matrix} L (D_{i}) & ⟶ & F_{q^{n}} ≃ F_{Q} \\ f & ⟼ & f (Q) \end{matrix}$
(iii) the natural evaluation map defined as follows is injective
$T : {\begin{matrix} L (D_{1} + D_{2}) & ⟶ & F_{q^{\deg P_{1}}} \times F_{q^{\deg P_{2}}} \times \dots \times F_{q^{\deg P_{N}}} \\ f & ⟼ & (f (P_{1}), f (P_{2}), \dots, f (P_{N})) \end{matrix}$

Then for any two elements

x, y

F_{q^{n}}

, we have:

x y = E_{Q} \circ T_{| Im T}^{- 1} (T \circ E_{1}^{- 1} (x) ⊙ T \circ E_{2}^{- 1} (y)),

where

E_{Q}

denotes the canonical projection from the valuation ring

O_{Q}

of the place Q in its residue class field

F_{Q}

, ∘ the standard composition map,

T_{| Im T}^{- 1}

the restriction of the inverse map of T on the image of T,

E_{i}^{- 1}

the inverse map of the restriction of the map

E_{i}

on the quotient group

L (D_{i}) / \ker E_{i}

and ⊙ the Hadamard product in

F_{q^{\deg P_{1}}} \times F_{q^{\deg P_{2}}} \times \dots \times F_{q^{\deg P_{N}}}

; and

μ_{q} (n) \leq \sum_{i = 1}^{N} μ_{q} (\deg P_{i})

3 Effective algorithm

3.1 Method and strategy of implementation

The construction of the algorithm is based on the choice of the place Q, the effective divisors $D_{1}$ and $D_{2}$ , the bases of spaces $L (D_{1})$ , $L (D_{2})$ and $L (D_{1} + D_{2})$ and the basis of the residue class field $F_{Q}$ .

In practice, following the ideas of [2], divisors $D_{1}$ and $D_{2}$ are chosen as places of degree $n + g - 1$ . Furthermore, we require some additional properties, which are described below.

3.2 Finding good places $D_{1}$ , $D_{2}$ , and Q

In order to obtain the good places, we proceed as follows:

– we draw at random an irreducible polynomial $Q (x)$ of degree n in $F_{q} [X]$ and check that this polynomial is primitive and totally decomposed in the algebraic function field $F / F_{q}$ ;
– we choose a place Q of degree n above the polynomial $Q (x)$ ;
– we choose a place Q of degree n among the places of $F / F_{q}$ lying above the polynomial $Q (x)$ ;
– we draw at random a place $D_{1}$ of degree $n + g - 1$ and check that $D_{1} - Q$ is a non-special divisor of degree $g - 1$ , i.e. $\dim L (D_{1} - Q) = 0$ ;
– we draw at random a place $D_{2}$ of degree $n + g - 1$ and check that $D_{2} - Q$ is a non-special divisor of degree $g - 1$ , i.e. $\dim (D_{2} - Q) = 0$ .

3.3 Choosing good bases of the spaces

The residue field $F_{Q}$ .

We choose the canonical basis $B_{Q}$ generated by a root α of the polynomial $Q (x)$ , namely $B_{Q} = (1, α, α^{2}, . . ., α^{n - 1})$ . From now on, we identify $F_{q^{n}}$ to $F_{Q}$ , as the residue class field $F_{Q}$ of the place Q is isomorphic to the finite field $F_{q^{n}}$ .

The Riemann–Roch spaces $L (D_{1})$ and $L (D_{2})$ .

We choose as basis of $L (D_{i})$ the reciprocal image $B_{D_{i}}$ of the basis $B_{Q} = (ϕ_{1}, \dots, ϕ_{n})$ of $F_{Q}$ by the evaluation map $E_{i}$ , namely $B_{D_{i}} = (E_{i}^{- 1} (ϕ_{i}), \dots, E_{i}^{- 1} (ϕ_{n}))$ .

Let us denote $B_{D_{i}} = (f_{i, 1}, . . ., f_{i, n})$ with $f_{i, 1} = 1$ for $i = 1, 2$ .

The Riemann–Roch space $L (D_{1} + D_{2})$ .

Note that since $D_{1}$ and $D_{2}$ are effective divisors, we have $L (D_{1}) \subset L (D_{1} + D_{2})$ and $L (D_{2}) \subset L (D_{1} + D_{2})$ .

Lemma 3.1

Let $D_{1}$ and $D_{2}$ be two effective divisors with disjoint supports. Then $L (D_{1}) \cap L (D_{2}) = F_{q}$ .

Proposition 3.1

Let $D_{1}$ , $D_{2}$ and Q be places having the properties described in (3.2). Consider the map $Λ : L (D_{1} + D_{2}) \to F_{Q}$ such that $Λ (f) = f (Q)$ for $f \in L (D_{1} + D_{2})$ . There exists a vector space $M \subseteq \ker Λ$ of dimension g such that

L (D_{1} + D_{2}) = L (D_{1}) \oplus L_{r} (D_{2}) \oplus M,

where

L_{r} (D_{2})

is such that

L (D_{2}) = F_{q} \oplus L_{r} (D_{2})

and ⊕ denotes the direct sum. In particular, if

g = 0

, then

M = K e r Λ

is equal to {0}.

We choose as basis of $L (D_{1} + D_{2})$ the basis $B_{D_{1} + D_{2}}$ defined by $B_{D_{1} + D_{2}} = (f_{1}, \dots, f_{n}, f_{n + 1}, \dots, f_{2 n + g - 1})$ where $B_{D_{1}} = (f_{1}, \dots, f_{n})$ is the basis of $L (D_{1})$ , $(f_{n + 1}, \dots, f_{2 n - 1})$ is a basis of $L_{r} (D_{2})$ such that $f_{n + j} = f_{2, j + 1} \in B_{D_{2}}$ with $B_{D_{1}}$ and $B_{D_{2}}$ defined in Section 3.3 and $B_{M} = (f_{2 n}, \dots, f_{2 n + g - 1})$ is a basis of $M$ .

3.4 Product of two elements in $F_{q^{n}}$

Let $x = (x_{1}, \dots, x_{n})$ and $y = (y_{1}, \dots, y_{n})$ be two elements of $F_{q^{n}}$ given by their components over $F_{q}$ relative to the chosen basis $B_{Q}$ . According to the previous notation, we can consider that x and y are identified as respectively $f_{x} = \sum_{i = 1}^{n} x_{i} f_{1, i} \in L (D_{1})$ and $f_{y} = \sum_{i = 1}^{n} y_{i} f_{2, i} \in L (D_{2})$ .

The product $f_{x} f_{y}$ of the two elements $f_{x}$ and $f_{y}$ is their product in the valuation ring $O_{Q}$ . This product lies in $L (D_{1} + D_{2})$ , since $D_{1}$ and $D_{2}$ are effective divisors. We consider that x and y are respectively the elements $f_{x}$ and $f_{y}$ embedded in the Rieman–Roch space $L (D_{1} + D_{2})$ , via respectively the embeddings $I_{i} : L (D_{i}) ⟶ L (D_{1} + D_{2})$ , defined by $I_{1} (f_{x})$ and $I_{2} (f_{y})$ as follows. If, $f_{x}$ and $f_{y}$ have respectively coordinates $f_{x_{i}}$ and $f_{y_{i}}$ in $B_{D_{1} + D_{2}}$ , where $i \in {1, \dots, 2 n + g - 1}$ , we have: $I_{1} (f_{x}) = (f_{x_{1}} : = x_{1}, \dots, f_{x_{n}} : = x_{n}, 0, \dots, 0)$ and $I_{2} (f_{y}) = (f_{x_{1}} : = y_{1}, 0, \dots, 0, f_{y_{n + 1}} : = y_{2}, \dots, f_{y_{2 n - 1}} : = y_{n}, 0, \dots 0)$ . Now it is clear that knowing x (resp. y) or $f_{x}$ (resp. $f_{y}$ ) by their coordinates is the same thing.

Theorem 3.2

Let $P_{M^{s}}$ be the projection of $L (D_{1} + D_{2})$ onto $M^{s} = L (D_{1}) \oplus L_{r} (D_{2})$ , and let Λ be the map defined as in Proposition 3.1. Then, for any elements $x, y \in F_{q^{n}}$ , the product of x by y is such that

x y = Λ \circ P_{M^{s}} (T_{| Im T}^{- 1} (T \circ I_{1} \circ E_{1}^{- 1} (x) ⊙ T \circ I_{2} \circ E_{2}^{- 1} (y))),

where ∘ denotes the standard composition map,

T_{| Im T}^{- 1}

the restriction of the inverse map of T on the image of T, and ⊙ the Hadamard product as in Theorem 2.1.

We can now present the setup algorithm (Algorithm 1), which is done only once.

The multiplication algorithm (Algorithm 2) is presented hereafter.

4 Complexity analysis

In terms of number of multiplications in $F_{q}$ , the complexity of this multiplication algorithm is as follows: calculation of z and t needs $2 (2 n^{2} + n g - n)$ multiplications, calculation of u needs $(2 n + 2 g - 2 + r) \sup_{1 \leq i \leq r} \frac{μ_{q} (i)}{i}$ bilinear multiplications and calculation of $2 n - 1$ first components of w needs $(2 n + g - 1) (2 n - 1)$ multiplications (remark that, in Algorithm 2, we just have to compute the $2 n - 1$ first components of w). The calculation of xy needs $n + g$ multiplications. The total complexity in terms of multiplications is bounded by $8 n^{2} + n (4 g - 5) + (2 n + 2 g - 2 + r) \sup_{1 \leq i \leq r} \frac{μ_{q} (i)}{i}$ .

The general construction of the set-up algorithm involves some random choice of divisors having prescribed properties over an exponentially large set of divisors. To get a polynomially constructible algorithm with linear complexity, one needs to construct explicitly (i.e. polynomially) points of corresponding degrees n on curves of arbitrary genus with many rational points. Unfortunately, so far it is unknown how to produce such points (cf. [9, Section 4, Remark 5] and [8, Remark 6.6]). Hence, the asymptotic complexity of such a construction is an open problem.

1 Introduction

1.1 Multiplication algorithm and tensor rank

Definition 1.1

Definition 1.2

1.2 Organisation of the note

2 Multiplication algorithms of type Chudnovsky: generalization of Randriambololona

Theorem 2.1

3 Effective algorithm

3.1 Method and strategy of implementation

3.2 Finding good places D1, D2, and Q

3.3 Choosing good bases of the spaces

Lemma 3.1

Proposition 3.1

3.4 Product of two elements in Fqn

Theorem 3.2

4 Complexity analysis

3.2 Finding good places $D_{1}$ , $D_{2}$ , and Q

3.4 Product of two elements in $F_{q^{n}}$