Fast construction of irreducible polynomials over finite fields
type: Item
instance of: scholarly article
title: Fast construction of irreducible polynomials over finite fields
zbMATH Open document ID: 0815.11059
author: Victor Shoup
published in: Journal of Symbolic Computation
publication date: 1994-10-13T00:00:00Z
review text: 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 \over 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 \over q}\). The author also presents some algorithms for computing minimal polynomials and factoring cyclotomic polynomials over \(GF (q)\).
reviewed by: Gary L. Ebert
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 638310
zbMATH Keywords: fast construction of irreducible polynomials
zbMATH Keywords: complexity
zbMATH Keywords: factorization of cyclotomic polynomials
zbMATH Keywords: algorithm
zbMATH Keywords: finite field
zbMATH Keywords: algorithms for testing irreducibility
zbMATH Keywords: minimal polynomials
MaRDI profile type: Publication
full work available at URL: jsco.1994.1025
OpenAlex ID: W1994173643
DOI: 10.1006/JSCO.1994.1025
description: scientific article; zbMATH DE number 638310