Diviseurs de la forme 2D-G sans sections et rang de la multiplication dans les corps finis (Divisors of the form 2D-G without sections and bilinear complexity of multiplication in finite fields)

2011/03/22 by Hugues Randriam, Randriam, Hugues
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Coding theory and cryptography #Cryptography and Residue Arithmetic #cs.CC #cs.IT #math.AG #math.IT #math.NT

paper · pdf · doi:10.48550/arxiv.1103.4335

35 pages, in French; French and English abstract

arxiv created 2011/03/24 · arxiv updated 2011/03/25

Abstract

Let X be an algebraic curve, defined over a perfect field, and G a divisor on X. If X has sufficiently many points, we show how to construct a divisor D on X such that l(2D-G)=0, of essentially any degree such that this is compatible the Riemann-Roch theorem. We also generalize this construction to the case of a finite number of constraints, l(k_i.D-G_i)=0, where |k_i|≤ 2. Such a result was previously claimed by Shparlinski-Tsfasman-Vladut, in relation with the Chudnovsky-Chudnovsky method for estimating the bilinear complexity of the multiplication in finite fields based on interpolation on curves; unfortunately, as noted by Cascudo et al., their proof was flawed. So our work fixes the proof of Shparlinski-Tsfasman-Vladut and shows that their estimate m_q≤ 2(1+1/(A(q)-1)) holds, at least when A(q)≥ 5. We also fix a statement of Ballet that suffers from the same problem, and then we point out a few other possible applications.

Related

• Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
• Linear algebra algorithms for divisors on an algebraic curve
• Decomposing Jacobians of Curves over Finite Fields in the Absence of\n Algebraic Structure
• Totally real divisors on curves
• Gaps between prime numbers and tensor rank of multiplication in finite\n fields