CAIPI Symposium : Programme de l'édition de juin 2026 (original) (raw)

June 2026: Algorithms for curves

Info

Titles and Abstracts

Jean-Marc Couveignes

IMB, University of Bordeaux

Evaluation and interpolation on algebraic curves.

Evaluation and interpolation of polynomials in one variable have many applications to fast arithmetic. In the context of finite fields, there might be not enough points where to evaluate large degree polynomials. This motivates the introduction of algebraic curves of higher genus. The purpose of these two lectures will be to set the grounds, to present the involved theoretical tools, to report on the main classical results in these fields, and to present some more recent work.

In the first lecture I will recall basics of complexity theory (straight line programs, rank of 3-tensors) with a view toward fast multiplication. I will also motivate and outline various ways of representing and computing with algebraic curves : finding convenient models, computing with divisors and functions, computing Riemann-Roch spaces, navigating in the Picard group, constructing abelian covers.

In the second talk I will focus on the problem of fast multiplication in finite field extensions and the contribution of algebraic curves to solving this problem. I will present now classical results by Shparlinsky, Tsfasmann, Vladut, Shokrollahi, Ballet and Rolland, Chaumine, Randriambololona and others on the bilinear complexity of multiplication in this context. I will then adress the problem of bounding the linear part of the complexity using the various tools introduced in the first talk.

Adrien Poteaux

CFHP team, CRISTAL, University of Lille

The OM algorithm.

Can we factorise P = (x² − 2)² − 2t² over K[[t]][x]? The answer is straightforward if we consider K = Q(√2), as P = (x² − 2 − √2·t)(x² − 2 + √2·t). But what about K = Q ? A good intuition can lead to the solution, but this is not obvious. Valuation theory is a way to answer such a question, using the OM algorithm.

The OM algorithm is named after Ore, Mac Lane, Okutsu and Montes. Historically, it consists of an iteration of a double dissection process (one according to some Newton polygon, and one according to some residual polynomial). Along this process, one builds a so-called Mac Lane–Vaquié chain, consisting of a sequence of augmented valuations on K[x], involving the computation of_key polynomials_.

This has been made very efficient lately, and has many applications, like for arithmetic or number theory problems (integral bases, Riemann–Roch spaces…), or geometric problems (curve desingularisation…).

In this talk, we will provide a description of the OM algorithm, showing that it essentially consists of residual polynomial computation and some Hensel lifting, a variant of the classical algorithm that we name valuated Hensel lifting.

1. We will start with several examples to illustrate the notion of residual polynomial and provide the main ideas of the algorithm. In particular, we will answer the above question.
2. Then, we will focus on the recent improvements of the algorithm and its complexity.

The main developments on the algorithm these last twenty years are due to Enric Nart et al., while the complexity improvements come from a collaboration with Martin Weimann.

Pierre-Jean Spaenlehauer

Inria center of the University of Lorraine, CARAMBA

Elliptic curve methods for univariate polynomials over finite fields

Several algorithms for univariate polynomials over a finite field Fq rely on the structure of the multiplicative group of

F

q. Examples include FFT-based methods for polynomial multiplication and various probabilistic and deterministic root-finding algorithms, whose efficiency depends on the divisibility of q-1 by a large smooth number. In certain situations, the multiplicative group can advantageously be replaced by the group of rational points of other algebraic groups.
In the first talk, we will describe methods that replace the multiplicative group with the group of rational points of an elliptic curve defined over

F

q in algorithms for univariate polynomials. This approach requires, in particular, lifting elements of the finite field to rational points on elliptic curves and designing efficient methods for manipulating divisors. In the second talk, we will focus more specifically on applying this framework to deterministic root-finding for univariate polynomials over finite fields.

Programme (provisional)