Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleSimultaneous modular reduction and Kronecker substitution for small finite fields
Author(s) Jean-Guillaume Dumas, Laurent Fousse, Bruno Salvy
TypeArticle in Journal
AbstractWe present algorithms to perform modular polynomial multiplication or a modular dot product efficiently in a single machine word. We use a combination of techniques. Polynomials are packed into integers by Kronecker substitution; several modular operations are performed at once with machine integer or floating point arithmetic; normalization of modular images is avoided when possible; some conversions back to polynomial coefficients are avoided; the coefficients are recovered efficiently by preparing them before conversion. We discuss precisely the required control on sizes and degrees. We then present applications to polynomial multiplication, prime field linear algebra and small extension field arithmetic, where these techniques lead to practical gains of quite large constant factors.
KeywordsKronecker substitution, Finite field, Modular polynomial multiplication, REDQ (simultaneous modular reduction), Small extension field, Compressed matrix multiplication
URL http://www.sciencedirect.com/science/article/pii/S0747717110001458
JournalJournal of Symbolic Computation
Pages823 - 840
NoteSpecial Issue in Honour of Keith Geddes on his 60th Birthday
Translation No
Refereed No