Multiplication in finite fields with Chudnovsky-type algorithms over the projective line

We propose a recursive polynomial generic construction (RPGC) of multiplication algorithms in any finite field F q n \mathbb {F}_{q^n} based on the method of D.V. and G.V. Chudnovsky (1987) specialized to the projective line. These algorithms improve those of Lempel-Seroussi-Winograd (1983) and the Karatsuba algorithm can be seen as a particular case of this construction. We give upper bounds for the bilinear complexity of these algorithms, and show that it is uniformly in q q quasi-linear with respect to the extension degree n n . We also prove that the construction of these algorithms is deterministic and can be done in polynomial time. We give an asymptotic bound for the complexity of their construction.