Probabilistic algorithm for finding roots of linearized polynomials
A probabilistic algorithm is presented for finding a basis of the root space of a linearized polynomial L(x) = Sigma(t)(i=0) L(i)x(qi) over F(q)n. The expected time complexity of the presented algorithm is O (nt) operations in F(q)n.
probabilistic algorithms linearized polynomials root-finding algorithms symbolic gcd