> EDIT: Doesn’t https://www.sciencedirect.com/science/article/abs/pii/S0020019006001396 https://www.sciencedirect.com/science/article/abs/pii/S00200... show tha

> EDIT: Doesn’t https://www.sciencedirect.com/science/article/abs/pii/S0020019006001396 https://www.sciencedirect.com/science/article/abs/pii/S00200... show that this algorithm is in fact polynomial? No, they give a linear lower bound for the number of digits you need to compute and show that the bound is tight for certain special numbers, but they don't have a polynomial upper bound for the general case.