Aarhus University Seal / Aarhus Universitets segl

Parallel Construction of Irreducible Polynomials

Research output: Working paper/Preprint Working paper

Standard

Parallel Construction of Irreducible Polynomials. / Frandsen, Gudmund Skovbjerg.

Department of Computer Science, Aarhus University, 1991.

Research output: Working paper/Preprint Working paper

Harvard

Frandsen, GS 1991 'Parallel Construction of Irreducible Polynomials' Department of Computer Science, Aarhus University.

APA

Frandsen, G. S. (1991). Parallel Construction of Irreducible Polynomials. Department of Computer Science, Aarhus University.

CBE

Frandsen GS. 1991. Parallel Construction of Irreducible Polynomials. Department of Computer Science, Aarhus University.

MLA

Frandsen, Gudmund Skovbjerg Parallel Construction of Irreducible Polynomials. Department of Computer Science, Aarhus University. 1991., 25 p.

Vancouver

Frandsen GS. Parallel Construction of Irreducible Polynomials. Department of Computer Science, Aarhus University. 1991.

Author

Frandsen, Gudmund Skovbjerg. / Parallel Construction of Irreducible Polynomials. Department of Computer Science, Aarhus University, 1991.

Bibtex

@techreport{67f1f427847d4e969d33649dc76e930a,
title = "Parallel Construction of Irreducible Polynomials",
abstract = "Let arithmetic pseudo-NC^k denote the problems that can be solved by log space uniform arithmetic circuits over the finite prime field GF(p) of depth O(log^k (n + p)) and size polynomial in (n + p). We show that the problem of constructing an irreducible polynomial of specified degree over GF(p) belongs to pseudo-NC^2.5. We prove that the problem of constructing an irreducible polynomial of specified degree over GF(p) whose roots are guaranteed to form a normal basis for the corresponding field extension pseudo-NC^2 -reduces to the problem of factor refinement. We show that factor refinement of polynomials is in arithmetic NC^3. Our algorithm works over any field and compared to other known algorithms it does not assume the ability to take p'th roots when the field has characteristic p.",
author = "Frandsen, {Gudmund Skovbjerg}",
year = "1991",
language = "English",
publisher = "Department of Computer Science, Aarhus University",
type = "WorkingPaper",
institution = "Department of Computer Science, Aarhus University",

}

RIS

TY - UNPB

T1 - Parallel Construction of Irreducible Polynomials

AU - Frandsen, Gudmund Skovbjerg

PY - 1991

Y1 - 1991

N2 - Let arithmetic pseudo-NC^k denote the problems that can be solved by log space uniform arithmetic circuits over the finite prime field GF(p) of depth O(log^k (n + p)) and size polynomial in (n + p). We show that the problem of constructing an irreducible polynomial of specified degree over GF(p) belongs to pseudo-NC^2.5. We prove that the problem of constructing an irreducible polynomial of specified degree over GF(p) whose roots are guaranteed to form a normal basis for the corresponding field extension pseudo-NC^2 -reduces to the problem of factor refinement. We show that factor refinement of polynomials is in arithmetic NC^3. Our algorithm works over any field and compared to other known algorithms it does not assume the ability to take p'th roots when the field has characteristic p.

AB - Let arithmetic pseudo-NC^k denote the problems that can be solved by log space uniform arithmetic circuits over the finite prime field GF(p) of depth O(log^k (n + p)) and size polynomial in (n + p). We show that the problem of constructing an irreducible polynomial of specified degree over GF(p) belongs to pseudo-NC^2.5. We prove that the problem of constructing an irreducible polynomial of specified degree over GF(p) whose roots are guaranteed to form a normal basis for the corresponding field extension pseudo-NC^2 -reduces to the problem of factor refinement. We show that factor refinement of polynomials is in arithmetic NC^3. Our algorithm works over any field and compared to other known algorithms it does not assume the ability to take p'th roots when the field has characteristic p.

M3 - Working paper

BT - Parallel Construction of Irreducible Polynomials

PB - Department of Computer Science, Aarhus University

ER -