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 : Friday, January 10, 2020 - 3:36:04 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

198

Files downloads

242