Factorization of polynomials over finite fields: Difference between revisions

Revision as of 23:51, 5 June 2019

Revision as of 09:10, 7 July 2019

Line 222:

====Victor Shoup's algorithm====

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, thatthan 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 that 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.