scientific article; zbMATH DE number 437575
The paper under review presents a new algorithm for constructing an irreducible polynomial of specified degree \(n\) over the finite field \(GF(q)\). The algorithm is probabilistic in nature and uses an expected number of \(O(( n^ 2\log n+n \log q)\log n\log \log n)\) operations in \(GF (q)\), making it asymptotically faster than previously known probabilistic algorithms for this problem. The only randomness used in the algorithm is an expected number of \(O(n)\) randomly chosen elements of \(GF(q)\). The basic strategy is to choose monic polynomials of degree \(n\) at random until an irreducible one is found. This is reasonable since the probability that such a randomly chosen polynomial is irreducible is approximately \(1/n\). Of course, one then needs an efficient irreducibility test. In this paper two new algorithms for testing irreducibility are given: one is deterministic and the other is probabilistic, erring with probability at most \(1/q\). The author also presents some algorithms for computing minimal polynomials and factoring cyclotomic polynomials over \(GF(q)\). For the entire collection see [Zbl 0771.00043].
- Arithmetic of finite fields
- Computing Frobenius maps and factoring polynomials
- Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Tests and constructions of irreducible polynomials over finite fields
- Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
- Computing isomorphisms and embeddings of finite fields
- scientific article; zbMATH DE number 3997938 (Why is no real title available?)
- An algorithm for finding the minimum degree of a polynomial over a finite field for a function over a vector space depending on the choice of an irreducible polynomial
- Fast construction of irreducible polynomials over finite fields
- Fast construction of irreducible polynomials over finite fields
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140455)