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
MathematicsFinite fieldIrreducible polynomialFactorization of polynomialsDegree (music)PolynomialField (mathematics)Prime (order theory)Reciprocal polynomialMinimal polynomial (linear algebra)Square-free polynomialCombinatoricsDiscrete mathematicsAlgorithmMatrix polynomialPure mathematicsMathematical analysis
Related Publications
Solving Simultaneous Modular Equations of Low Degree
We consider the problem of solving systems of equations $P_i (x) \equiv 0(\bmod n_i )i = 1 \cdots k$ where $P_i $ are polynomials of degree d and the $n_i $ are distinct relativ...
Quantum measurements and the Abelian Stabilizer Problem
We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our ...
Reducing elliptic curve logarithms to logarithms in a finite field
Elliptic curve cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known...
Computing Logarithms in Finite Fields of Characteristic Two
A simple algorithm to find logarithms in a finite field of characteristic two is described. It uses the Euclidean algorithm for polynomials in attempting to reduce an element to...
The Theory of Matrices
Volume 2: XI. Complex symmetric, skew-symmetric, and orthogonal matrices: 1. Some formulas for complex orthogonal and unitary matrices 2. Polar decomposition of a complex matrix...
Publication Info
- Year
- 1990
- Type
- article
- Volume
- 54
- Issue
- 189
- Pages
- 435-447
- Citations
- 170
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
170
OpenAlex
Cite This
Victor Shoup
(1990).
New algorithms for finding irreducible polynomials over finite fields.
Mathematics of Computation
, 54
(189)
, 435-447.
https://doi.org/10.1090/s0025-5718-1990-0993933-0
Identifiers
- DOI
- 10.1090/s0025-5718-1990-0993933-0