A CRT-Based Montgomery Multiplication for Finite Fields of Small Characteristic - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2005

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

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.

Domains

Other [cs.OH]
Fichier principal
Vignette du fichier
D512.PDF (126.46 Ko) Télécharger le fichier

Dates and versions

lirmm-00106455 , version 1 (16-10-2006)

Identifiers

  • HAL Id : lirmm-00106455 , version 1

Cite

Jean-Claude Bajard, Laurent Imbert, Graham A. Jullien, Hugh C. 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⟩
111 View
572 Download

Share

Gmail Facebook X LinkedIn More