Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Christine Carvalho de Matos Connect in order to contact the contributor
Submitted on : Monday, October 16, 2006 - 8:29:21 AM
Last modification on : Friday, January 10, 2020 - 3:36:04 PM
Long-term archiving on: : Thursday, September 20, 2012 - 11:55:31 AM



  • HAL Id : lirmm-00106455, version 1



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. ⟨lirmm-00106455⟩



Record views


Files downloads