Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm

Kévin Atighehchi; Stéphane Ballet; Alexis Bonnecaze; Robert Rolland

doi:10.1016/j.crma.2015.12.001

Number theory/Computer science

Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm

Presented by: the Editorial Board

Kévin Atighehchi ¹; Stéphane Ballet ²; Alexis Bonnecaze ²; Robert Rolland ²

¹ Aix-Marseille Université, Laboratoire d'informatique fondamentale de Marseille, case 901, 13288 Marseille cedex 9, France
² 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.

Abstract
Résumé

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.

À 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.

Received: 2015-09-22
Accepted: 2015-12-01
Published online: 2016-01-15

DOI: 10.1016/j.crma.2015.12.001

Author's affiliations:

Kévin Atighehchi ¹; Stéphane Ballet ²; Alexis Bonnecaze ²; Robert Rolland ²

¹ Aix-Marseille Université, Laboratoire d'informatique fondamentale de Marseille, case 901, 13288 Marseille cedex 9, France
² 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/

References
Cited by

[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 $F_{q}$ , 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

Cited by Sources:

Comments - Policy