Finding Integer Roots of Polynomials in Nearly Optimal Time
Source: arxiv.org/abs/2611.04730
Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\widetilde O(nb+\min(n,b)^3b^2)$, which is $\widetilde…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.04730
curl -X POST /api/v1/records/arxiv/2611.04730/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04730/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'