Article

PDF
Access to the PDF text
Advertising


Free Article !

Comptes Rendus Mathématique
Volume 355, n° 7
pages 729-733 (juillet 2017)
Doi : 10.1016/j.crma.2017.06.002
Received : 21 November 2016 ;  accepted : 2 June 2017
On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation
Construction effective de l'algorithme asymétrique de multiplication de Chudnovsky dans les corps finis
 

Stéphane Ballet a , Nicolas Baudru b , Alexis Bonnecaze a , Mila Tukumuli a
a Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France 
b Aix Marseille Univ, CNRS, Centrale Marseille, LIF, Marseille, France 

Abstract

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.

The full text of this article is available in PDF format.
Résumé

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 full text of this article is available in PDF format.
Introduction

Let q be a prime power,   the finite field with q elements and   the degree n extension of  . Among all algorithms of multiplications in  , 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  , 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.

Multiplication algorithm and tensor rank

The multiplication of two elements of   is an  -bilinear application from   onto  . Then it can be considered as an  -linear application from the tensor product   onto  . Consequently, it can also be considered as an element   of   where ⋆ denotes the dual. When   is written
(1)Tm=∑i=1rxi⋆⊗yi⋆⊗ci, where the r elements   as well as the r elements   are in the dual   of   while the r elements   are in  , the following holds for any  :  . The decomposition ((1)) is not unique.

Definition 1.1

Every expression   defines a bilinear multiplication algorithm   of bilinear complexity  . Such an algorithm is said symmetric if   for all i .

Definition 1.2

The minimal number of summands in a decomposition of the tensor   of the multiplication is called the bilinear complexity (resp. symmetric bilinear complexity) of the multiplication and is denoted by   (resp.  ):
μq(n)=minU⁡μ(U) where   is running over all bilinear multiplication algorithms (resp. all bilinear symmetric multiplication algorithms) in   over  .

Organisation of the note

In Section 2, we give an explicit translation of the generalization of the Chudnovsky algorithm given by Randriambololona [[8]]. 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.

Multiplication algorithms of type Chudnovsky: generalization of Randriambololona

In this section, we present a generalization of Chudnovsky-type algorithms, introduced in [[8]] 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   be an algebraic function field over the finite field   of genus  . We denote by   the number of places of degree one of F over  . If D is a divisor,   denotes the Riemann–Roch space associated with D . We denote by   the valuation ring of the place Q and by   its residue class field  , which is isomorphic to  , where   is the degree of the place Q .

In the framework of algebraic function fields, the result [[8]] 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   where the   are pairwise distinct closed points of degree  .

Let us define the following Hadamard product in  , where the  's denote positive integers, by  .

Theorem 2.1

Let   be an algebraic function field of genus g over  . Suppose that there exists a place Q of degree n. Let   be a set of N places of arbitrary degree not containing the place Q. Suppose that there exist two effective divisors   of   such that:

(i)
the place Q and the places of   are not in the support of the divisors   and  ;
(ii)
the natural evaluation maps   for   defined as follows are surjective
Ei :  {L(Di)⟶Fqn≃FQf⟼f(Q)
(iii)
the natural evaluation map defined as follows is injective
T :   {L(D1+D2)⟶Fqdeg⁡P1×Fqdeg⁡P2×⋯×Fqdeg⁡PNf⟼(f(P1),f(P2),…,f(PN))
Then for any two elements   in  , we have: xy=EQ∘T|ImT−1(T∘E1−1(x)⊙T∘E2−1(y)), where   denotes the canonical projection from the valuation ring   of the place Q in its residue class field  ,the standard composition map,   the restriction of the inverse map of T on the image of T,   the inverse map of the restriction of the map   on the quotient group   andthe Hadamard product in  ; and  .

Effective algorithm
Method and strategy of implementation

The construction of the algorithm is based on the choice of the place Q , the effective divisors   and  , the bases of spaces  ,   and   and the basis of the residue class field  .

In practice, following the ideas of [[2]], divisors   and   are chosen as places of degree  . Furthermore, we require some additional properties, which are described below.

Finding good places  ,  , and Q

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

we draw at random an irreducible polynomial   of degree n in   and check that this polynomial is primitive and totally decomposed in the algebraic function field  ;
we choose a place Q of degree n above the polynomial  ;
we choose a place Q of degree n among the places of   lying above the polynomial  ;
we draw at random a place   of degree   and check that   is a non-special divisor of degree  , i.e.  ;
we draw at random a place   of degree   and check that   is a non-special divisor of degree  , i.e.  .

Choosing good bases of the spaces

The residue field  .

We choose the canonical basis   generated by a root α of the polynomial  , namely  . From now on, we identify   to  , as the residue class field   of the place Q is isomorphic to the finite field  .

The Riemann–Roch spaces   and  .

We choose as basis of   the reciprocal image   of the basis   of   by the evaluation map  , namely  .

Let us denote   with   for  .

The Riemann–Roch space  .

Note that since   and   are effective divisors, we have   and  .

Lemma 3.1

Let   and   be two effective divisors with disjoint supports. Then  .

Proposition 3.1

Let  ,   and Q be places having the properties described in (3.2). Consider the map   such that   for  . There exists a vector space   of dimension g such that
L(D1+D2)=L(D1)⊕Lr(D2)⊕M, where   is such that   anddenotes the direct sum. In particular, if  , then   is equal to {0}.

We choose as basis of   the basis   defined by   where   is the basis of  ,   is a basis of   such that   with   and   defined in Section 3.3 and   is a basis of  .

Product of two elements in  

Let   and   be two elements of   given by their components over   relative to the chosen basis  . According to the previous notation, we can consider that x and y are identified as respectively   and  .

The product   of the two elements   and   is their product in the valuation ring  . This product lies in  , since   and   are effective divisors. We consider that x and y are respectively the elements   and   embedded in the Rieman–Roch space  , via respectively the embeddings  , defined by   and   as follows. If,   and   have respectively coordinates   and   in  , where  , we have:   and  . Now it is clear that knowing x (resp. y ) or   (resp.  ) by their coordinates is the same thing.

Theorem 3.2

Let   be the projection of   onto  , and let Λ be the map defined as in Proposition 3.1. Then, for any elements  , the product of x by y is such that
xy=Λ∘PMs(T|ImT−1(T∘I1∘E1−1(x)⊙T∘I2∘E2−1(y))), wheredenotes the standard composition map,   the restriction of the inverse map of T on the image of T, andthe Hadamard product as in Theorem 2.1.

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



Algorithm 1


Algorithm 1. 

Setup algorithm.

Zoom

The multiplication algorithm (Algorithm 2) is presented hereafter.



Algorithm 2


Algorithm 2. 

Multiplication algorithm.

Zoom

Complexity analysis

In terms of number of multiplications in  , the complexity of this multiplication algorithm is as follows: calculation of z and t needs   multiplications, calculation of u needs   bilinear multiplications and calculation of   first components of w needs   multiplications (remark that, in Algorithm 2, we just have to compute the   first components of w ). The calculation of xy needs   multiplications. The total complexity in terms of multiplications is bounded by  .

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]] and [[8]]). Hence, the asymptotic complexity of such a construction is an open problem.

References

Arnaud N. Évaluation dérivées, multiplication dans les corps finis et codes correcteursPhD Thesis.   France: Université de la Méditerranée, Institut de mathématiques de Luminy (2006). 
Ballet S. Curves with many points and multiplication complexity in any extension of   Finite Fields Appl. 1999 ;  5 (4) : 364-377 [cross-ref]
Ballet S., Bonnecaze A., Tukumuli M. On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields J. Algebra Appl. 2016 ;  15 (1) : 1650005
Ballet S., Rolland R. Multiplication algorithm in a finite field and tensor rank of the multiplication J. Algebra 2004 ;  272 (1) : 173-185 [cross-ref]
Ballet S., Rolland R. On the bilinear complexity of the multiplication in finite fields Proceedings of the Conference Arithmetic, Geometry and Coding Theory (AGCT 2003) : Société mathématique de France (2005).  179-188
Chudnovsky D.V., Chudnovsky G.V. Algebraic complexities and algebraic curves over finite fields J. Complex. 1988 ;  4 : 285-316 [cross-ref]
Pieltant J., Randriambololona H. New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields Math. Comput. 2015 ;  84 : 2023-2045 [cross-ref]
Randriambololona H. Bilinear complexity of algebras and the Chudnovsky–Chudnovsky interpolation method J. Complex. 2012 ;  28 : 489-517 [cross-ref]
Shparlinski I., Tsfasman M., Vladut S. Curves with many points and multiplication in finite fields Coding Theory and Algebraic Geometry Berlin: Springer-Verlag (1992).  145-169



© 2017  Académie des sciences@@#104156@@
EM-CONSULTE.COM is registrered at the CNIL, déclaration n° 1286925.
As per the Law relating to information storage and personal integrity, you have the right to oppose (art 26 of that law), access (art 34 of that law) and rectify (art 36 of that law) your personal data. You may thus request that your data, should it be inaccurate, incomplete, unclear, outdated, not be used or stored, be corrected, clarified, updated or deleted.
Personal information regarding our website's visitors, including their identity, is confidential.
The owners of this website hereby guarantee to respect the legal confidentiality conditions, applicable in France, and not to disclose this data to third parties.
Close
Article Outline