Factorization of polynomials over finite fields: Difference between revisions

Revision as of 03:44, 8 December 2020

Revision as of 22:45, 13 January 2021

Line 203:

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'''_''q'' 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 | booktitlebook-title = Automata, languages and programming (Aarhus, 1982)| series = Lecture Notes in Comput. Sci.|volume = 140|pages = 239–251|publisher = Springer|year=1982|doi=10.1007/BFb0012773|isbn=978-3-540-11576-2}}</ref>

In the typical case where ''d''log(''q'') > ''n'', this complexity may be reduced to