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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106455
Contributor : Christine Carvalho de Matos <>
Submitted on : Monday, October 16, 2006 - 8:29:21 AM
Last modification on : Tuesday, December 11, 2018 - 5:16:02 PM
Long-term archiving on : Thursday, September 20, 2012 - 11:55:31 AM

File

Identifiers

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

Share

Metrics

Record views

193

Files downloads

236