Content deleted Content added
m clean up, typo(s) fixed: 1-2 → 1–2 (2) |
|||
Line 201:
This implies that the polynomial gcd(''g'', ''u'') is the product of the factors of ''g'' for which the component of ''g'' is zero.
It has been shown that the average number of iterations of the while loop of the algorithm is less than <math>2.5 \log_2 r</math>, giving an average number of arithmetic operations in '''F'''<sub>''q''</sub> which is <math>O(dn^2\log(r)\log(q))</math>.<ref>{{citation|first1=Philippe|title=Automata, Languages and Programming|last1=Flajolet|first2=Jean-Marc | last2=Steayaert |
In the typical case where ''d''log(''q'') > ''n'', this complexity may be reduced to
| |||