1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.