I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its degree? I am allowing randomized algorithms here.

Can you please provide references for both classical and quantum algorithms? What happens if we can compute polynomial in any $\mathbb{Z}_p$ through the black box.