On The Effective Construction of Asymmetric Chudnovsky Multiplication Algorithms in Finite Fields Without Derivated Evaluation

Preprint English OPEN
Ballet, Stéphane; Baudru, Nicolas; Bonnecaze, Alexis; Tukumuli, Mila;
  • Subject: Mathematics - Algebraic Geometry

The Chudnovsky and Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear whith respect to the degree of the extension. Recently, Randriambololona has generalized the method, allowing asymmetry... View more
  • References (32)
    32 references, page 1 of 4

    T : −→ 7−→ 5.2.3. The basis of L(D1 + D2). As seen in Section 3.3.3, BD1+D2 = (f1,...,fn,fn+1,...,f2n+g−1) where, for j ∈ {1,...,2n − 1}, the fi are defined above. The basis is completed with

    [1] N. Arnaud. Évaluation Dérivées, Multiplication dans les Corps Finis et Codes Correcteurs. PhD Thesis, 2006. Université de la Méditerranée, Institut de Mathématiques de Luminy.

    [2] K. Atighehchi, S. Ballet, A. Bonnecaze, R. Rolland. Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm. C. R. Acad. Sci. Paris, Ser. I 354 (2016) 137-141.

    [3] K. Atighehchi, S. Ballet, A. Bonnecaze, R. Rolland. On Chudnovsky-Based Arithmetic Algorithms in Finite Fields. arXiv:1510.00090 [cs.DM]

    [4] S. Ballet, A. Bonnecaze, M. Tukumuli. On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields. Journal of Algebra and Its Applications, Vol. 15, No. 1 (2016) 1650005.

    [5] S. Ballet. Curves with many points and multiplication complexity in any extension of Fq. Finite Fields and their Applications, 5(4), 364-377, 1999.

    [6] S. Ballet. Quasi-optimal algorithms for multiplication in the extensions of F16 of degree 13, 14 and 15. Journal of Pure and Applied Algebra, 171(2-3), 149-164, 2002.

    [7] S. Ballet and D. Le Brigand. On the existence of non special divisor of degree g and g − 1 in algebraic function fields over Fq. Journal of Number Theory, 116, 293-310, 2006.

    [8] S. Ballet and J. Pieltant. On the tensor rank of multiplication in any extension of F2. Journal of Complexity, 27, 230-245, 2011.

    [9] S. Ballet and R. Rolland. Multiplication algorithm in a finite field and tensor rank of the multiplication. Journal of Algebra, 272/1, 173-185, 2004.

  • Metrics
    No metrics available
Share - Bookmark