No label defined (Q3140455)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 437575
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 437575 |
Statements
9 November 1994
0 references
algorithm
0 references
irreducible polynomial
0 references
finite field
0 references
algorithms for testing irreducibility
0 references
computing minimal polynomials
0 references
factoring cyclotomic polynomials
0 references
0.9981778860092164
0 references
0.9978135824203492
0 references
0.9042186737060548
0 references
0.8783390522003174
0 references
0.8765961527824402
0 references
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].
0 references