On each iteration, the most time-consuming task is to select formula_6. We know that there are formula_50 possible values, so we can find formula_6 using formula_52 comparisons. Each comparison will require evaluating formula_53. In the "k"th iteration, formula_2 has formula_55 digits, and the polynomial can be evaluated with formula_56 multiplications of up to formula_57 digits and formula_58 additions of up to formula_57 digits, once we know the powers of formula_2 and formula_6 up through formula_62 for formula_2 and formula_5 for formula_6. formula_6 has a restricted range, so we can get the powers of formula_6 in constant time. We can get the powers of formula_2 with formula_69 multiplications of up to formula_57 digits. Assuming formula_5-digit multiplication takes time formula_72 and addition takes time formula_73, we take time