Search

Chudnovsky-type algorithms of multiplication in finite fields are well known for their good bilinear complexity. Recently, two advances have been obtained in the study of these algorithms: a strategy to optimize the scalar complexity of the original algorithm and the development of a generic recursive construction over the projective line. The construction of recursive Chudnodvsky-type algorithms over the projective line makes possible an efficient generic strategy to optimize their complexity (number of scalar and bilinear multiplications and additions in the base field). Then, several examples are given. In particular, considering Baum-Shokrollahi’s experiment (1992), this constructive method provides a Chudnovsky-type algorithm of multiplication in F 256 / F 4 \mathbb {F}_{256}/\mathbb {F}_4 with the best known complexity, while being much more efficient than existing optimization methods.

International audience

International audience; The Chudnovsky and Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear with respect to the degree of the extension. Recently, Ran-driambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. In this article, we first translate this generalization into the language of algebraic function fields. Then, we propose a strategy to effectively construct asymmetric algorithms using places of higher degrees and without derivated evaluation. Finally, we provide examples of three multiplication algorithms along with their Magma implementation: in F 16 13 using only rational places, in F 4 5 using also places of degree two, and in F 2 5 using also places of degree four.

We propose a Recursive Polynomial Generic Construction (RPGC) of multiplication algorithms in any finite field $\mathbb{F}_{q^n}$ based on the method of D.V. and G.V. Chudnovsky specialized on the projective line. They are usual polynomial interpolation algorithms in small extensions and the Karatsuba algorithm is seen as a particular case of this construction. Using an explicit family of such algorithms, we show that their bilinear complexity is quasi-linear with respect to the extension degree n, and we give a uniform bound for this complexity. 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., Comment: 30 pages

International audience; We propose a new construction for the multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve scalar algebraic complexity. In particular, we improve the Baum-Shokrollahi construction for multiplication in F256/F4 based on the elliptic Fermat curve x 3 + y 3 = 1.

We propose a new construction for the multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve scalar algebraic complexity. In particular, we improve the Baum-Shokrollahi construction for multiplication in F256/F4 based on the elliptic Fermat curve x 3 + y 3 = 1.

International audience; Presented by the Editorial Board 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.; 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.

International audience

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 in the interpolation procedure and leading to new upper bounds on the bilinear complexity. We describe the effective algorithm of this asymmetric method, without derivated evaluation. Finally, we give examples with the finite field $\F_{16^{13}}$ using only rational places, $\F_{4^{13}}$ using also places of degree two and $\F_{2^{13}}$ using also places of degree four., Comment: arXiv admin note: text overlap with arXiv:1510.00090

International audience; Every second year, the GEOCRYPT conference brings together researchers from arithmetic geometry and cryptography. After Guadeloupe in 2009 and Corsica in 2011, French Polynesia was the host of its 2013 edition which took place in Punaauia, on the island of Tahiti, October 7-11. The main topic of GEOCRYPT has always been the application of pure mathematical techniques to the safety and efficiency of modern communication systems, with particular interest in the fields of arithmetic and algebraic geometry over finite fields, algorithms for finite fields, error correcting codes, cryptology, boolean functions, discrete dynamical systems, and their interactions. The 2013 edition had the honour to feature six invited and eleven contributed talks from renowned international experts presenting strong results recently obtained on topics ranging from pure mathematics to cryptographic algorithms. The GEOCRYPT 2013 Program Committee carefully evaluated the submitted abstracts and selected the best contributions for presentation at the conference.

International audience; We propose new results on low weight codewords of affine and projective generalized Reed–Muller (GRM) codes. In the affine case we prove that if the cardinality of the ground field is large compared to the degree of the code, the low weight codewords are products of affine functions. Then, without this assumption on the cardinality of the field, we study codewords associated to an irreducible but not absolutely irreducible polynomial, and prove that they cannot be second, third or fourth weight depending on the hypothesis. In the projective case the second distance of GRM codes is estimated, namely a lower bound and an upper bound on this weight are given.

Nous donnons des bornes inf\'erieures sur le nombre de diviseurs effectifs de degr\'e $\leq g-1$ par rapport au nombre de places d'un certain degr\'e d'un corps de fonctions alg\'ebriques de genre $g$ d\'efini sur un corps fini. Nous d\'eduisons des bornes inf\'erieures du nombre de classes qui am\'eliorent les bornes de Lachaud - Martin-Deschamps et des bornes inf\'erieures asymptotiques atteignant celles de Tsfasman-Vladut. Nous donnons des exemples de tours de corps de fonctions alg\'ebriques ayant un grand nombre de classes., We give lower bounds on the number of effective divisors of degree $\leq g-1$ with respect to the number of places of certain degrees of an algebraic function field of genus $g$ defined over a finite field. We deduce lower bounds for the class number which improve the Lachaud - Martin-Deschamps bounds and asymptotically reaches the Tsfasman-Vladut bounds. We give examples of towers of algebraic function fields having a large class number.

We propose new results on low weight codewords of affine and projective generalized Reed-Muller codes. In the affine case we prove that if the size of the working finite field is large compared to the degree of the code, the low weight codewords are products of affine functions. Then in the general case we study some types of codewords and prove that they cannot be second, thirds or fourth weight depending on the hypothesis. In the projective case the second distance of generalized Reed-Muller codes is estimated, namely a lower bound and an upper bound of this weight are given., Comment: New version taking into account recent results from Elodie Leducq on the characterization of the next-to-minimal codewords (cf. arXiv:1203.5244)

International audience; In this paper, we obtain new bounds for the tensor rank of multiplication in any extension of $\F_2$. In particular, it also enables us to obtain the best known asymptotic bound. To this aim, we use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over $\F_2$ of a Garcia-Stichtenoth tower of algebraic function fields defined over $\F_{2^4}$.

We give lower bounds for the number of effective divisors of degree $\leq g-1$ of an algebraic function field of one variable of genus $g\geq 2$ defined over a finite field. We deduce lower bounds for the class number,depending mainly on the number of places of a certain degree, which improve the best known lower bounds in many cases. Moreover, we prove that any family of algebraic function fields having asymptotically (with respect to the genus) a large number of places of a certain degree $r\geq1$, have a large asymptotical class number for which we give an estimate., On donne des minorations du nombre de diviseurs effectifs de degr\'e $\leq g-1$ d'un corps de fonctions alg\'ebriques en une variable de genre $g\geq 2$ d\'efini sur un corps fini ${\mathbb{F}}_q$. On en d\'eduit alors des minorations du nombre de classes, d\'ependant essentiellement du nombre de places d'un certain degr\'e $r$, qui am\'eliorent les meilleures bornes inf\'erieures connues dans de nombreux cas. De plus, nous montrons que toutes les familles de corps de fonctions alg\'ebriques en une variable ayant asymptotiquement (relativement au genre) un grand nombre de places d'un certain degré $r\geq1$, possèdent un nombre de classe asymptotiquement grand dont nous donnons une estimation.

We prove the existence of asymptotically exact sequences of algebraic function fields defined over any finite field $\F_q$ having an asymptotically maximum number of places of a degree $r$ where $r$ is an integer $\geq 1$. It turns out that these particular families have an asymptotic class numberwidely greater than all the Lachaud - Martin-Deschamps bounds when $r>1$.We emphasize that we exhibit explicit asymptotically exact sequences of algebraic function fields over any finite field$\F_q$, in particular when $q$ is not a square, with $r=2$. We explicitly construct an example for $q=2$ and $r=4$. We deduce of this study that for any finite field $\F_q$ there exists a sequence of algebraic function fields defined over any finite field $\F_q$ reaching the generalized Drinfeld - Vladut bound., Nous prouvons l'existence de familles asymptotiquement exactes de corps de fonctions alg\'ebriques d\'efinis sur un corps fini $\F_q$ qui ont un nombre maximum de places de degr\'e $r$ o\`u $r$ est un entier $\geq 1$. Il s'av\`ere que pour ces familles particuli\`eres le nombre de classes est asymptotiquement beaucoup plus grand que la borne g\'en\'erale de Lachaud - Martin-Deschamps quand $r>1$. Pour $r=2$ nous construisons explicitement des suites de corps de fonctions alg\'ebriques sur tout corps fini $\F_q$ qui sont asymptotiquement exactes et ceci m\^eme lorsque $q$ n'est pas un carr\'e. Nous construisons un exemple pour $r=4$ dans le cas o\`u $q=2$. Nous d\'eduisons de cette \'etude que pour tout corps fini $\F_q$ il existe une suite de corps de fonctions alg\'ebriques sur $\F_q$ qui atteint la borne de Drinfeld - Vladut g\'en\'eralis\'ee.

International audience; Yao’s theorem gives an equivalence between the indistinguishability of a pseudo-random generator and the unpredictability of the next bit from an asymptotic point of view. In this paper we present with detailed proofs, modified versions of Yao’s theorem which can be of interest for the study of practical cryptographic primitives. In particular we consider non-asymptotic versions. We study the case of one pseudo-random generator, then the case of a family of pseudo-random generators with the same fixed length and finally we consider the asymptotic case. We compute in each case the cost of the reduction (in the sense of complexity theory) between the two algorithms.

In this paper, we give a survey of the known results concerning the tensor rank of the multiplication in the finite fields and we establish new asymptotical and not asymptotical upper bounds about it.

We study and explicitly construct some families of asymptotically exact sequences of algebraic function fields. It turns out that these families have an asymptotical class number widely greater than the general Lachaud - Martin-Deschamps bounds. We emphasize that we obtain asymptotically exact sequences of algebraic function fields over any finite field $\F_q$, in particular when $q$ is not a square and that these sequences are dense towers., Comment: 13 pages

International audience