Algorithm for factorization of polynomials
In computational number theory, Evdokimov's algorithm, named after Sergei Evdokimov, is an algorithm for factorization of polynomials over finite fields. It was the fastest algorithm known for this problem, from its publication in 1994 until 2020. It can factorize a one-variable polynomial of degree formula_1 over an explicitly given finite field of cardinality formula_2. Assuming the generalized Riemann hypothesis the algorithm runs in deterministic time formula_3 (see Big O notation). This is an improvement of both Berlekamp's algorithm and Rónyai's algorithm in the sense that the first algorithm is polynomial for small characteristic of the field, whearas the second one is polynomial for small formula_1; however, both of them are exponential if no restriction is made.
The factorization of a polynomial formula_5 over a ground field formula_6 is reduced to the case when formula_5 has no multiple roots and is completely splitting 
over formula_6 (i.e. formula_5 has formula_1 distinct roots in formula_6). In order to find a root of formula_5 in this case, the algorithm deals with 
polynomials not only over the ground field formula_6 but also over a completely splitting semisimple algebra over formula_6 (an example of such an algebra is given by formula_15, where formula_16). The main problem here is to find efficiently a nonzero zero-divisor in the algebra. The GRH is used only to take roots in finite fields in polynomial time. Thus the Evdokimov algorithm, in fact, solves a polynomial equation over a finite field "by radicals" in quasipolynomial time.
The analyses of Evdokimov's algorithm is closely related with some problems in the association scheme theory. With the help of this approach, it was proved 
 that if formula_1 is a prime and formula_18 has a ‘large’ formula_19-smooth divisor formula_20, then a modification of the Evdokimov algorithm finds a nontrivial factor of the polynomial formula_5 in deterministic formula_22 time, assuming GRH and that formula_23.