Simultaneous modular reduction and Kronecker substitution for small finite fields

DOI10.1016/J.JSC.2010.08.015zbMATH Open1217.65074arXiv0809.0063OpenAlexW2040829540MaRDI QIDQ540334FDOQ540334

Bruno Salvy, Laurent Fousse, Jean-Guillaume Dumas

Publication date: 1 June 2011

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We present algorithms to perform modular polynomial multiplication or modular dot product efficiently in a single machine word. We pack polynomials into integers and perform several modular operations with machine integer or floating point arithmetic. The modular polynomials are converted into integers using Kronecker substitution (evaluation at a sufficiently large integer). With some control on the sizes and degrees, arithmetic operations on the polynomials can be performed directly with machine integers or floating point numbers and the number of conversions can be reduced. We also present efficient ways to recover the modular values of the coefficients. This leads to practical gains of quite large constant factors for polynomial multiplication, prime field linear algebra and small extension field arithmetic.

Full work available at URL: https://arxiv.org/abs/0809.0063

zbMATH Keywords

algorithmsnumerical examplesfinite fieldcompressed matrix multiplicationKronecker substitutionmodular polynomial multiplicationREDQ (simultaneous modular reduction)small extension field

Mathematics Subject Classification ID

Polynomials over finite fields (11T06)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pseudo-Paley graphs and skew Hadamard difference sets from presemifields
• On the computational power of pushdown automata
• Modular Multiplication Without Trial Division
• Modern computer algebra
• Distributed matrix-free solution of large sparse linear systems over finite fields
• FFPACK
• Solving linear equations over GF(2): Block Lanczos algorithm
• A p-Adic Quasi-Quadratic Time Point Counting Algorithm
• Q-adic transform revisited
• Faster polynomial multiplication via multipoint Kronecker substitution

Cited In (1)

• Reducing the number of operations in certain finite- field transforms (Corresp.)

Uses Software

• FFLAS-FFPACK
• Givaro
• NTL

This page was built for publication: Simultaneous modular reduction and Kronecker substitution for small finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540334)