| Title | Simultaneous modular reduction and Kronecker substitution for small finite fields |
| Author(s) | Jean-Guillaume Dumas, Laurent Fousse, Bruno Salvy |
| Type | Article in Journal |
| Abstract | We 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. |
| Keywords | Kronecker substitution, Finite field, Modular polynomial multiplication, REDQ (simultaneous modular reduction), Small extension field, Compressed matrix multiplication |
| ISSN | 0747-7171 |
| URL |
http://www.sciencedirect.com/science/article/pii/S0747717110001458 |
| Language | English |
| Journal | Journal of Symbolic Computation |
| Volume | 46 |
| Number | 7 |
| Pages | 823 - 840 |
| Year | 2011 |
| Note | Special Issue in Honour of Keith Geddes on his 60th Birthday |
| Edition | 0 |
| Translation |
No |
| Refereed |
No |
