Simultaneous modular reduction and Kronecker substitution for small finite fields

DOI10.1016/J.JSC.2010.08.015MaRDI QIDQ540334zbMATH OpenOpenAlexFDO

Authors Jean-Guillaume Dumas, Laurent Fousse, Bruno Salvy

Publication date 1 June 2011

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

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)

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.

Recommendations

• Faster polynomial multiplication via multipoint Kronecker substitution
• Q-adic transform revisited
• Fast polynomial factorization and modular composition
• Efficient modular reduction algorithm in \(\mathbb F_q[x]\) and its application to ``left to right modular multiplication in \(\mathbb F_2[x]\).
• Modular composition via factorization

Cites work

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

Cited in

(4)

• Q-adic transform revisited
• Fast convolutions meet Montgomery
• Reducing the number of operations in certain finite- field transforms (Corresp.)
• Modular SIMD arithmetic in \textsc{Mathemagix}

Describes a project that uses

Uses Software

• NTL
• Givaro
• FFLAS-FFPACK

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)