A CRT-Based Montgomery Multiplication for Finite Fields of Small Characteristic

Jean-Claude Bajard 1 Laurent Imbert 1, 2 Graham Jullien 2 Hugh Williams 2
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We propose a new CRT-based multiplication algorithm for finite fields F_p^k of small prime characteristic, whose complexity does not depend on a special form of the reduction polynomial. With a complexity of O(k^3/2) this is the first general subquadratic algorithm for fields of small odd characteristic.
Type de document :
Communication dans un congrès
IMACS: Scientific Computation, Applied Mathematics and Simulation, Jul 2005, Paris, France. 2005
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106455
Contributeur : Christine Carvalho de Matos <>
Soumis le : lundi 16 octobre 2006 - 08:29:21
Dernière modification le : vendredi 20 juillet 2018 - 23:14:58
Document(s) archivé(s) le : jeudi 20 septembre 2012 - 11:55:31

Fichier

Identifiants

  • HAL Id : lirmm-00106455, version 1

Collections

Citation

Jean-Claude Bajard, Laurent Imbert, Graham Jullien, Hugh Williams. A CRT-Based Montgomery Multiplication for Finite Fields of Small Characteristic. IMACS: Scientific Computation, Applied Mathematics and Simulation, Jul 2005, Paris, France. 2005. 〈lirmm-00106455〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

97