DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2024.33

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

Authors: Shanthanu S. Rai

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract

We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree d over finite field 𝔽_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 Õ(d⁴log⁴q). Our construction extends Shoup’s deterministic algorithm (FOCS 1988) for the same problem, which runs in time Õ(d⁴p^{1/2}log⁴q) (where p is the characteristic of the field 𝔽_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.

Cite as

Shanthanu S. Rai. Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rai:LIPIcs.FSTTCS.2024.33,
  author =	{Rai, Shanthanu S.},
  title =	{{Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.33},
  URN =		{urn:nbn:de:0030-drops-222227},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.33},
  annote =	{Keywords: Algebra and Computation, Finite fields, Factorization, Pseudo-deterministic, Polynomials}
}

Search Results

Documents authored by Rai, Shanthanu S.

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

Abstract

Cite as

Thanks for your feedback!

Could not send message