New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- 1 January 1990
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 54 (189) , 435-447
- https://doi.org/10.2307/2008704
Abstract
We present a new algorithm for finding an irreducible polynomial of specified degree over a finite field. Our algorithm is deterministic, and it runs in polynomial time for fields of small characteristic. We in fact prove the stronger result that the problem of finding irreducible polynomials of specified degree over a finite field is deterministic polynomial-time reducible to the problem of factoring polynomials over the prime field.Keywords
This publication has 10 references indexed in Scilit:
- Algebraic Coding TheoryPublished by World Scientific Pub Co Pte Ltd ,2014
- Factoring polynomials using fewer random bitsJournal of Symbolic Computation, 1990
- On the deterministic complexity of factoring polynomials over finite fieldsInformation Processing Letters, 1990
- Factoring polynomials and primitive elements for special primesTheoretical Computer Science, 1987
- Factorization of Multivariate Polynomials Over Finite FieldsMathematics of Computation, 1985
- Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomialsIEEE Transactions on Information Theory, 1983
- Probabilistic Algorithms in Finite FieldsSIAM Journal on Computing, 1980
- A bound for the least prime ideal in the Chebotarev Density TheoremInventiones Mathematicae, 1979
- Equations over Finite Fields An Elementary ApproachLecture Notes in Mathematics, 1976
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970