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

Jean-Claude Bajard 1 Laurent Imbert 1 A. Jullien G. C. Williams H.
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'05 : World Congress: Scientific Computation, Applied Mathematics and Simulation, Jul 2005, Paris (France), pp.CDROM, 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 : jeudi 11 janvier 2018 - 06:26:07
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, A. Jullien G., C. Williams H.. A CRT-Based Montgomery Multiplication for Finite Fields of Small Characteristic. IMACS'05 : World Congress: Scientific Computation, Applied Mathematics and Simulation, Jul 2005, Paris (France), pp.CDROM, 2005. 〈lirmm-00106455〉

Partager

Métriques

Consultations de la notice

139

Téléchargements de fichiers

94