ausblenden:
Schlagwörter:
-
Zusammenfassung:
In this paper, we provide polynomial bounds on the worst case bit-complexity of
two formulations of the continued fraction algorithm.
In particular, for a square-free integer polynomial of degree $n$ with
coefficients of bit-length $L$, we show that the bit-complexity
of Akritas' formulation is $\wt{O}(n^8L^3)$, and the bit-complexity
of a formulation by Akritas and Strzebo\'nski is $\wt{O}(n^7L^2)$;
here $\wt{O}$ indicates that we are omitting logarithmic factors.
The analyses use a bound by Hong to compute
the floor of the smallest positive root of a polynomial, which is a crucial
step in the continued fraction algorithm. We also propose a modification
of the latter formulation that achieves a bit-complexity of $\wt{O}(n^5L^2)$.
