Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
<|reference_start|>Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields: We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree $d$ over finite field $\mathbb{F}_q$. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. Our construction runs in time $\tilde{O}(d^4 \log^4{q})$.   Our construction extends Shoup's deterministic algorithm (FOCS 1988) for the same problem, which runs in time $\tilde{O}(d^4 p^{\frac{1}{2}} \log^4{q})$ (where $p$ is the characteristic of the field $\mathbb{F}_q$). Shoup had shown a reduction from constructing irreducible polynomials to factoring polynomials over finite fields. We show that by using a fast randomized factoring algorithm, the above reduction yields an efficient pseudo-deterministic algorithm for constructing irreducible polynomials over finite fields.<|reference_end|>
@article{rai2024pseudo-deterministic,
    title={Pseudo-Deterministic Construction of Irreducible Polynomials over Finite
  Fields},
    author={Shanthanu S Rai},
    journal={arXiv preprint arXiv:2410.04071},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.04071},
    primaryClass={cs.DS cs.CC math.NT}
}