Abstract
The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field Fq . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O-(n2 + n log q) operations in Fq, where the "soft-O" O- indicates an implicit factor of (log n)O(1). In addition, two new polynomial irreducibility tests are described.
Original language | English (US) |
---|---|
Pages (from-to) | 371-391 |
Number of pages | 21 |
Journal | Journal of Symbolic Computation |
Volume | 17 |
Issue number | 5 |
DOIs | |
State | Published - 1994 |
ASJC Scopus subject areas
- Algebra and Number Theory
- Computational Mathematics