On exact division and divisibility testing for sparse polynomials
| Autor: | Armelle Perret du Cray, Bruno Grenet, Pascal Giorgi |
|---|---|
| Přispěvatelé: | Exact Computing (ECO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Symbolic Computation Discrete mathematics Exact division [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Polynomial 010102 general mathematics 0102 computer and information sciences Divisibility rule Symbolic Computation (cs.SC) 01 natural sciences Ring of integers Randomized algorithm Finite field 010201 computation theory & mathematics 0101 mathematics Time complexity Quotient Mathematics |
| Zdroj: | ISSAC |
| Popis: | No polynomial-time algorithm is known to test whether a sparse polynomial G divides another sparse polynomial F . While computing the quotient Q = F quo G can be done in polynomial time with respect to the sparsities of F , G and Q, this is not yet sufficient to get a polynomial-time divisibility test in general. Indeed, the sparsity of the quotient Q can be exponentially larger than the ones of F and G. In the favorable case where the sparsity #Q of the quotient is polynomial, the best known algorithm to compute Q has a non-linear factor #G#Q in the complexity, which is not optimal.In this work, we are interested in the two aspects of this problem. First, we propose a new randomized algorithm that computes the quotient of two sparse polynomials when the division is exact. Its complexity is quasi-linear in the sparsities of F , G and Q. Our approach relies on sparse interpolation and it works over any finite field or the ring of integers. Then, as a step toward faster divisibility testing, we provide a new polynomial-time algorithm when the divisor has a specific shape. More precisely, we reduce the problem to finding a polynomial S such that QS is sparse and testing divisibility by S can be done in polynomial time. We identify some structure patterns in the divisor G for which we can efficiently compute such a polynomial S. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|