Comptes Rendus
no. 2
Number theory/Computer science
Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm
[Arithmétique effective dans les corps finis basée sur l'algorithme de multiplication de Chudnovsky]

Présenté par : the Editorial Board

Kévin Atighehchi1 ; Stéphane Ballet2 ; Alexis Bonnecaze2 ; Robert Rolland2
1 Aix-Marseille Université, Laboratoire d'informatique fondamentale de Marseille, case 901, 13288 Marseille cedex 9, France
2 Aix-Marseille Université, Institut de mathématiques de Marseille, case 930, 13288 Marseille cedex 9, France
Comptes Rendus. Mathématique, Volume 354 (2016) no. 2, pp. 137-141.

À partir d'une nouvelle construction de l'algorithme de multiplication de Chudnovsky et Chudnovsky, nous concevons des algorithmes efficaces pour la multiplication et l'exponentiation dans les corps finis. Ils sont adaptés à une implémentation matérielle et sont parallélisables, tout en gardant un nombre de multiplications bilinéaires très bas.

Thanks to a new construction of the Chudnovsky and Chudnovsky multiplication algorithm, we design efficient algorithms for both the exponentiation and the multiplication in finite fields. They are tailored to hardware implementation and they allow computations to be parallelized, while maintaining a low number of bilinear multiplications.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2015.12.001
Kévin Atighehchi 1 ; Stéphane Ballet 2 ; Alexis Bonnecaze 2 ; Robert Rolland 2

1 Aix-Marseille Université, Laboratoire d'informatique fondamentale de Marseille, case 901, 13288 Marseille cedex 9, France
2 Aix-Marseille Université, Institut de mathématiques de Marseille, case 930, 13288 Marseille cedex 9, France 
@article{CRMATH_2016__354_2_137_0,
     author = {K\'evin Atighehchi and St\'ephane Ballet and Alexis Bonnecaze and Robert Rolland},
     title = {Effective arithmetic in finite fields based on {Chudnovsky's} multiplication algorithm},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {137--141},
     publisher = {Elsevier},
     volume = {354},
     number = {2},
     year = {2016},
     doi = {10.1016/j.crma.2015.12.001},
     language = {en},
}
TY  - JOUR
AU  - Kévin Atighehchi
AU  - Stéphane Ballet
AU  - Alexis Bonnecaze
AU  - Robert Rolland
TI  - Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm
JO  - Comptes Rendus. Mathématique
PY  - 2016
SP  - 137
EP  - 141
VL  - 354
IS  - 2
PB  - Elsevier
DO  - 10.1016/j.crma.2015.12.001
LA  - en
ID  - CRMATH_2016__354_2_137_0
ER  - 
%0 Journal Article
%A Kévin Atighehchi
%A Stéphane Ballet
%A Alexis Bonnecaze
%A Robert Rolland
%T Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm
%J Comptes Rendus. Mathématique
%D 2016
%P 137-141
%V 354
%N 2
%I Elsevier
%R 10.1016/j.crma.2015.12.001
%G en
%F CRMATH_2016__354_2_137_0
Kévin Atighehchi; Stéphane Ballet; Alexis Bonnecaze; Robert Rolland. Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm. Comptes Rendus. Mathématique, Volume 354 (2016) no. 2, pp. 137-141. doi : 10.1016/j.crma.2015.12.001. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2015.12.001/

[1] K. Atighehchi; S. Ballet; A. Bonnecaze; R. Rolland Arithmetic in finite fields based on Chudnovsky multiplication algorithm (preliminary version submitted for publication) | arXiv

[2] S. Ballet Curves with many points and multiplication complexity in any extension of Fq, Finite Fields Appl., Volume 5 (1999), pp. 364-377

[3] D. Chudnovsky; G. Chudnovsky Algebraic complexities and algebraic curves over finite fields, J. Complex., Volume 4 (1988), pp. 285-316

[4] D. Coppersmith; S. Winograd Matrix multiplication via arithmetic progressions, J. Symb. Comput., Volume 9 (1990) no. 3, pp. 251-280

[5] J.-M. Couveignes; R. Lercier Elliptic periods for finite fields, Finite Fields Appl., Volume 15 (2009) no. 1, pp. 1-22

[6] S. Gao; J. von zur Gathen; D. Panario; V. Shoup Algorithms for exponentiation in finite fields, J. Symb. Comput., Volume 29 (2000) no. 6, pp. 879-889

[7] J. von zur Gathen Efficient and optimal exponentiation in finite fields, Comput. Complex., Volume 1 (1991), pp. 360-394

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation

Stéphane Ballet; Nicolas Baudru; Alexis Bonnecaze; ...

C. R. Math (2017)