1
$\begingroup$

My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$.

Are there such algorithms that use poly$(n, \log q)$ bit operations?

I know that this is true if $q$ is a prime number - see the paper of Shoup V . "A new polynomial factorization algorithm and its implementation".

Is it true for an arbitrary finite field?

Improve this question
$\endgroup$
8
  • $\begingroup$ Try searching via google. This will lead you to the wikipedia page en.wikipedia.org/wiki/… and to a survey paper by von zur Gathen and Panario, which tell you what's known. There is no known deterministic polynomial time algorithm for this which works in every case. $\endgroup$
    – Michael Zieve
    Commented Jul 3, 2016 at 18:20
  • $\begingroup$ @MichaelZieve thank you, I was misled by the book "Number-theoretic Algorithms in Cryptography" by Vasilenko where he did not note that $q$ must be prime in the algorithm of Shoup $\endgroup$
    – Alexey Milovanov
    Commented Jul 3, 2016 at 18:34
  • $\begingroup$ @MaxAlekseyev, yes, of course. I have edited my question, I hope now it is clear $\endgroup$
    – Alexey Milovanov
    Commented Jul 5, 2016 at 19:41
  • 1
    $\begingroup$ There isn't even an algorithm that is unconditionally proved to factor quadratics over large prime fields in polynomial time. ("Unconditionally" because there is such an algorithm under the extended Riemann Hypothesis.) $\endgroup$
    – Noam D. Elkies
    Commented Jul 6, 2016 at 0:18
  • 1
    $\begingroup$ Find a quadratic nonresidue $r \ll \log^2(p)$ (if memory serves) by trying all candidates. Once you have a non-square in a finite field it's easy to extract square roots. The existence of a quadratic nonresidue of size polynomial in $\log p$ is a known consequence of the ERH. (Not "EGRH": I mean the analogue of Riemann for Dirichlet $L$-series; here we need the $L$-series associated to the quadratic character $\bmod p$.) $\endgroup$
    – Noam D. Elkies
    Commented Sep 10, 2017 at 1:41

0

Reset to default

You must log in to answer this question.