2
$\begingroup$

In $\Bbb F_q[x]$ given $d\in\Bbb N$ there is a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=deg(x)$ under $GRH$ and an unconditional randomized algorithm.

  1. Do we know of a randomized $O(poly(nd\log q))$ algorithm to find an irreducible polynomial in $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(x_i)$ at every $i\in\{1,\dots,n\}$?

  2. Does derandomizing PIT derandomize these unconditionally?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.