Factorization of Polynomials Over Finite Fields (Factorization of Polynomials Over Finite Fields)

From Algorithm Wiki
Revision as of 15:39, 15 February 2023 by Admin (talk | contribs)
Jump to navigation Jump to search

Description

Factor a given polynomial over a finite field into a product of irreducible polynomials.

Parameters

No parameters found.

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Schubert's algorithm 1940 $O(n^{3})$ $O(n)$ Exact Deterministic

Time Complexity Graph

Factorization of Polynomials Over Finite Fields - Time.png

Space Complexity Graph

Factorization of Polynomials Over Finite Fields - Space.png

Space-Time Tradeoff Improvements

Factorization of Polynomials Over Finite Fields - Pareto Frontier.png

References/Citation

https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/abs/pii/0020019090901954

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Factorization_of_Polynomials_Over_Finite_Fields&oldid=46608"