ECCC-Report TR24-147https://eccc.weizmann.ac.il/report/2024/147Comments and Revisions published for TR24-147en-usFri, 04 Oct 2024 17:29:16 +0300
Paper TR24-147
| Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields |
Shanthanu Rai
https://eccc.weizmann.ac.il/report/2024/147We 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.Fri, 04 Oct 2024 17:29:16 +0300https://eccc.weizmann.ac.il/report/2024/147