Simultaneous modular reduction and Kronecker substitution for small finite fields

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

Authors: Jean-Guillaume Dumas, Laurent Fousse, Bruno Salvy 

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

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

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

• Pseudo-Paley graphs and skew Hadamard difference sets from presemifields
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Solving linear equations over GF(2): Block Lanczos algorithm
• A p-Adic Quasi-Quadratic Time Point Counting Algorithm
• Q-adic transform revisited
• Title not available (Why is that?)
• Faster polynomial multiplication via multipoint Kronecker substitution

Cited In (3)

• Q-adic transform revisited
• Fast convolutions meet Montgomery
• 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)