Factorization of polynomials over finite fields: Difference between revisions

Revision as of 12:44, 9 October 2021

Revision as of 13:48, 9 October 2021

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'''_''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 |title = Automata, languages and programming (|___location=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

Line 294:

*[[Keith Geddes|Geddes, Keith O.]]; Czapor, Stephen R.; Labahn, George (1992). [https://dx.doi.org/10.1007/b102438 Algorithms for computer algebra]. Boston, MA: Kluwer Academic Publishers. pp. xxii+585. {{ISBN|0-7923-9259-0}}.

{{Refend}}

==Notes==

{{Reflist}}

==External links==

Line 300 ⟶ 303:

* Galois Field:http://designtheory.org/library/encyc/topics/gf.pdf

* Factoring polynomials over finite fields: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf

==Notes==

{{Reflist}}

[[Category:Polynomials]]