Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

Question

Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ are irreducible and of equal degree what is the best technique to factor such polynomials?

Assume $GCD$ of coefficients is $1$ after removing denominator.

1. Is there a deterministic or a randomized algorithm that is polynomial time in complexity in total degree ($d$), variables ($n$) and number of bits in coefficients ($L$)?

2. Is there an algorithm that is at least in $O(2^{c\cdot n}(d\cdot L)^c)$ for a fixed real $c$?

Assume that the polynomial and its factors have at most $\max(2^{2d},2^{2n})$ coefficients.

Answer 1

Note that a polynomial of degree $d$ with $n$ variables may have $\binom{n+d}n$ monomials, hence both input and output may have size exponential in $n$ and $d$, if the polynomials are represented by lists of monomials and coefficients, as the OP seems to assume. (The additional assumption at the end of the question is completely unhelpful, as $\binom{n+d}n\le\max\{2^{2d},2^{2n}\}$ anyway.)

Having said that, von zur Gathen and Kaltofen [1] prove that there exist randomized factoring algorithms for multivariate polynomials over $\mathbb Q$ (and certain other fields) that work in time polynomial in the size of the input and output: i.e., $d$, $n$, $L$, and the number of nonzero coefficients.

[1] Joachim von zur Gathen and Erich Kaltofen: Factoring sparse multivariate polynomials, Journal of Computer and System Sciences 31 (1985), no. 2, pp. 265–287, doi: 10.1016/0022-0000(85)90044-3.