RECORD
Polynomial modular product verification and its implications
Symbolic Computation · Submitted 6 Jan 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations. We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. | gap 0.80 | 0.06 | 0.02 | asserted 0.89 |
| s2 | This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. | gap 0.92 | 0.04 | 0.04 | hedged possibility 0.73 |
| s3 | While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations. | background 0.96 | 0.05 | 0.05 | asserted 0.99 |
| s4 | We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. | contribution 1.00 | 0.64 | 0.04 | asserted 0.82 |
| s5 | We investigate its bit complexity for both dense and sparse multiplicands. | contribution 0.98 | 0.75 | 0.04 | asserted 0.79 |
| s6 | In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. | result 0.97 | 0.91 | 0.44 | asserted 0.99 |
| s7 | We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. | contribution 0.65 | 0.92 | 0.17 | asserted 0.99 |
| s8 | In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product. | result 0.57 | 0.96 | 0.74 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations. We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.