Computing sparse multiples of polynomials
type: Item
instance of: scholarly article
title: Computing sparse multiples of polynomials
zbMATH Open document ID: 1282.68198
author: Daniel S. Roche
author: Hrushikesh Tilak
author: Mark Giesbrecht
published in: Algorithmica
publication date: 2013-01-28T00:00:00Z
review text: Given a polynomial \(P\), for example with integer coefficients, a classical question is: is it true that \(P\) has some ``simple'' mutiple? for example a multiple with coefficients \(0\) or \(\pm1\)? Here the authors consider the existence of sparse multiples, i.e. multiples with only few non-zero coefficients. They give an algorithm to answer such a question in the case of polynomials over the rational numbers. They also study this problem for polynomials with coefficients in a finite field and show -- in a certain sense -- that this is a hard problem.
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 13P05
zbMATH DE Number: 6131856
zbMATH Keywords: sparse polynomials
zbMATH Keywords: sparsest multiple
reviewed by: Maurice Mignotte
MaRDI profile type: Publication
full work available at URL: s00453-012-9652-4
OpenAlex ID: W2019463665
cites work: Q4847943
cites work: A sieve algorithm for the shortest lattice vector problem
cites work: $\mathcal{TCH}o$ : A Hardware-Oriented Trapdoor Cipher
cites work: On the inherent intractability of certain coding problems (Corresp.)
cites work: Algorithms for Finding Almost Irreducible and Almost Primitive Trinomials
cites work: Sparsification of rectangular matrices
cites work: Q4914762
cites work: Computing Sparse Multiples of Polynomials
cites work: Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
cites work: A Practical Key Recovery Attack on Basic TCHo
cites work: Factoring polynomials with rational coefficients
cites work: Q4252162
cites work: Groups, Factoring, and Cryptography
cites work: On the Order and Degree of Solutions to Pure Equations
cites work: Approximate formulas for some functions of prime numbers
cites work: Searching for Primitive Roots in Finite Fields
cites work: The intractability of computing the minimum distance of a code
cites work: Q4406533
cites work: Q4502647
cites work: Q5525481
DOI: 10.1007/S00453-012-9652-4
description: scientific article; zbMATH DE number 6131856