Lesson plan

Evdokimov's algorithm

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 n over an explicitly given finite field of cardinality q . Assuming the generalized Riemann hypothesis the algorithm runs in deterministic time (n^{\log n}\log q)^{{\mathcal O}(1)} (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 n ; however, both of them are exponential if no restriction is made. The factorization of a polynomial f over a ground field k is reduced to the case when f has no multiple roots and is completely splitting over k (i.e. f has n distinct roots in k ). In order to find a root of f in this case, the algorithm deals with polynomials not only over the ground field k but also over a completely splitting semisimple algebra over k (an example of such an algebra is given by k[X]/(f) = k[A] , where A = X\bmod f ). 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.…

Back to article

Article summary

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 n over an explicitly given finite field of cardinality q . Assuming the generalized Riemann hypothesis the algorithm runs in deterministic time (n^{\log n}\log q)^{{\mathcal O}(1)} (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 n ; however, both of them are exponential if no restriction is made. The factorization of a polynomial f over a ground field k is reduced to the case when f has no multiple roots and is completely splitting over k (i.e. f has n distinct roots in k ). In order to find a root of f in this case, the algorithm deals with polynomials not only over the ground field k but also over a completely splitting semisimple algebra over k (an example of such an algebra is given by k[X]/(f) = k[A] , where A = X\bmod f ). 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.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.