Factorization of polynomials over finite fields: Difference between revisions

Revision as of 09:42, 7 February 2022

Revision as of 01:03, 30 March 2022

Line 225:

Like the algorithms of the preceding section, [[Victor Shoup]]'s algorithm is an equal-degree factorization algorithm.<ref>Victor Shoup, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.9136&rep=rep1&type=pdf On the deterministic complexity of factoring polynomials over finite fields], Information Processing Letters 33:261-267, 1990</ref> Unlike them, it is a deterministic algorithm. However, it is less efficient, in practice, than the algorithms of preceding section. For Shoup's algorithm, the input is restricted to polynomials over prime fields '''F'''_''p''.

The worst case [[time complexity]] of Shoup's algorithm has a factor <math>\sqrt{p}.</math> Although exponential, this complexity is much better thatthan previous deterministic algorithms (Berlekamp's algorithm) which have {{math|''p''}} as a factor. However, there are very few polynomials for which the computing time is exponential, and the average time complexity of the algorithm is polynomial in <math>d\log(p),</math> where {{mvar|''d''}} is the degree of the polynomial, and {{math|''p''}} is the number of elements of the ground field.

Let ''g'' = ''g''₁ ... ''g_k'' be the desired factorization, where the ''g_i'' are distinct monic irreducible polynomials of degree ''d''. Let ''n'' = deg(''g'') = ''kd''. We consider the [[ring (mathematics)|ring]] ''R'' = '''F'''_''q''[''x'']/''g'' and denote also by ''x'' the image of ''x'' in ''R''. The ring ''R'' is the direct product of the fields ''R_i'' = '''F'''_''q''[''x'']/''g_i'', and we denote by ''p_i'' the natural [[homomorphism]] from the ''R'' onto ''R_i''. The [[Galois group]] of ''R_i'' over '''F'''_''q'' is cyclic of order ''d'', generated by the [[field automorphism]] ''u'' → ''u^p''. It follows that the roots of ''g_i'' in ''R_i'' are