DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.16

Constant-Depth Circuits for Polynomial GCD over Any Characteristic

Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic. Our proofs are based on a recent work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi & Saraf that shows closure of constant depth algebraic circuits under factorization. On our way to the proof, we show that any n-variate symmetric polynomial P that has a small constant depth algebraic circuit can be written as the composition of a small constant depth algebraic circuit with elementary symmetric polynomials. This statement is a constant depth version of a result of Bläser & Jindal, who showed this for algebraic circuits of unbounded depth. As an application of our techniques, we also strengthen the closure results for factors of constant-depth circuits in the work of Bhattacharjee et al. over fields for small characteristic.

Cite as

Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf. Constant-Depth Circuits for Polynomial GCD over Any Characteristic. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.CCC.2026.16,
  author =	{Bhattacharjee, Somnath and Kumar, Mrinal and Rai, Shanthanu S. and Ramanathan, Varun and Saptharishi, Ramprasad and Saraf, Shubhangi},
  title =	{{Constant-Depth Circuits for Polynomial GCD over Any Characteristic}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.16},
  URN =		{urn:nbn:de:0030-drops-270580},
  doi =		{10.4230/LIPIcs.CCC.2026.16},
  annote =	{Keywords: algebraic circuits, polynomial greatest common divisor, symmetric polynomials, finite fields, constant-depth circuits}
}

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.

Constant-Depth Circuits for Polynomial GCD over Any Characteristic

Abstract

Cite as

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

Abstract

Cite as

Thanks for your feedback!

Could not send message