A New Sparse Algorithm for Polynomial GCD over Integers
We describe a new greatest common divisor (GCD) algorithm for polynomials with integer coefficients. The bit complexity of the new algorithm is polynomial in the input and output sizes and the individual degree bounds.Our algorithm follows the standard approach by reducing multivariate polynomial GCD to univariate polynomial GCD. Our algorithm reduces a multivariate polynomial GCD to a single univariate polynomial GCD. The main idea of our algorithm is a new variable substitution which reduces a multivariate polynomial to a separated one, that is, the coefficients in a main variable are all…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.10626
curl -X POST /api/v1/records/arxiv/2609.10626/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.10626/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'