Wikipedia:Reference desk/Archives/Mathematics/2016 December 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 13

Root Finding Algorithm

Hi all, what is the best time complexity for root finding of multivariate polynomial over a finite field Z_p (where p is not fixed) ? 213.8.204.58 (talk) 21:02, 13 December 2016 (UTC)

You asked a related question last year (or someone with almost the same IP address did). I'm having trouble finding a complete answer to this question too. Most papers talk only about factorization and say nothing explicitly about root finding. In addition to what I linked last year, "Factoring multivariate polynomials over large finite fields" by DQ Wan gives a randomized factoring algorithm that takes $O(n^{4.89}\log ^{2}n\log p)$ field operations for bivariate polynomials and some unstated but still polynomial number of operations for arbitrary multivariate polynomials, which means the problem is in RP, at least if the number of variables is fixed. The paper also says that it's not known to be in P. The paper is a bit old (1990) but I can't find any evidence that anyone has found a deterministic polytime algorithm since then. Ping User:PrimeHunter again, I guess. -- BenRG (talk) 05:43, 14 December 2016 (UTC)

I cannot help. PrimeHunter (talk) 10:12, 14 December 2016 (UTC)

First, nice catch - it was me :)

Second, the paper you've cited shows a probabilistic algorithm for polynomial factorization which runs in time polynomial in n (the degree of the polynomial) and in log(q) (over Z_q).

However:

1. The paper talks about polynomial factorization rather than root finding. Are these question equivalent? To my understanding, they are not equivalent, as after factoring it into lower degree polynomials, we have new polynomials that we should find their roots. Maybe the question of root finding for irreducible polynomials is easy for some reason that I am missing now...?
2. For my purpose, I need an algorithm (deterministic or probabilistic) which runs in time polynomial in log(n) and in log(q), instead. Do you know if such an algorithm exists?

Thank you for your help! 213.8.204.57 (talk) —Preceding undated comment added 18:30, 14 December 2016 (UTC)