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

Atighehchi, Kévin1 ; Ballet, Stéphane2 ; Bonnecaze, Alexis2 ; Rolland, Robert2
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, Tome 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
Atighehchi, Kévin 1 ; Ballet, Stéphane 2 ; Bonnecaze, Alexis 2 ; Rolland, Robert 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 = {Atighehchi, K\'evin and Ballet, St\'ephane and Bonnecaze, Alexis and Rolland, Robert},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2015.12.001/}
}
TY  - JOUR
AU  - Atighehchi, Kévin
AU  - Ballet, Stéphane
AU  - Bonnecaze, Alexis
AU  - Rolland, Robert
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2015.12.001/
DO  - 10.1016/j.crma.2015.12.001
LA  - en
ID  - CRMATH_2016__354_2_137_0
ER  - 
%0 Journal Article
%A Atighehchi, Kévin
%A Ballet, Stéphane
%A Bonnecaze, Alexis
%A Rolland, Robert
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2015.12.001/
%R 10.1016/j.crma.2015.12.001
%G en
%F CRMATH_2016__354_2_137_0
Atighehchi, Kévin; Ballet, Stéphane; Bonnecaze, Alexis; Rolland, Robert. Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm. Comptes Rendus. Mathématique, Tome 354 (2016) no. 2, pp. 137-141. doi : 10.1016/j.crma.2015.12.001. http://www.numdam.org/articles/10.1016/j.crma.2015.12.001/

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

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

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

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

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

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

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

Cité par Sources :