It is a long-standing open problem in computer algebra to find a deterministic polynomial-time algorithm that factorizes a given univariate polynomial f(X) over a finite field 𝔽p. Such an algorithm is not known even under the generalized Riemann hypothesis (GRH). In this talk, I will discuss a unifying approach for this problem based on a family of combinatorial objects called P-schemes. Our approach subsumes known GRH-based results and also leads to some new results. In particular, we show how to beat Evdokimov’s algorithm when a polynomial f̃ (X)∈ℤ[X] lifting f(X) is given whose Galois group has a “linear” structure.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
