On the computing time of the continued fractions method (Q438690)

The authors show that, when classical computation is used, the maximum computing time of the continued fractions method (CF-method) with root bounds dominates \(n^5\) where \(n\) is the degree of the input polynomial. This computing time is realized for an infinite sequence of polynomials of increasing degrees, each having the same coefficients. The recursion trees for those polynomials do not depend on the use of root bounds in the CF-method. The height of each tree is more than half of the degree. When the degree exceeds one hundred, more than one third of the nodes along the longest path are associated with primitive polynomials whose low-order and high-order coefficients are large negative integers. The length of the forty-five percent highest order coefficients and of the ten percent lowest order coefficients is at least linear in the degree of the input polynomial multiplied by the level of the node. Hence the time required to compute one node from the previous node using classical methods is at least proportional to the cube of the degree of the input polynomial multiplied by the level of the node. The intervals that the CF-method returns are characterized using a matrix factorization algorithm.