Finding irreducible and primitive polynomials
The paper presents new fast constructions of irreducible and primitive polynomials. It contains the following main results: 1. For any \(N \in \mathbb{N}\) one can construct an irreducible polynomial of degree \(n = N + O (N \exp (-( \log \log N)^{1/2-\varepsilon}))\) over \(GF(p)\) in time \((p \log N)^{O(1)}\). 2. For sufficiently large \(Q\) one can construct the field \(GF(q)\) with \(q = Q + O(Q \log^{-A}Q)\) (\(A\) constant) in time \((\log Q)^{O(1)}\). 3. For sufficiently large \(Q\) one can construct the field \(GF(q)\) with \(q=(Q + O (Q \exp (-(\log Q)^{1-\varepsilon})))\) and its primitive roots in time \(\exp (O(\log Q/ \log \log \log Q))\). 4. For any \(N \in \mathbb{N}\) one can construct an integer \(n=N+O(N^ \epsilon)\) and a primitive root in \(GF(p^ n)\) in time \(p^{cN/ \log \log N}\) \((c\) constant).
- Prime values of polynomials and irreducibility testing
- scientific article; zbMATH DE number 1253967
- Prime values of irreducible polynomials
- Irreducible values of polynomials
- Irreducibility of Polynomials
- Irreducibility Testing and Factorization of Polynomials
- Using trace to identify irreducible polynomials
- From prime numbers to irreducible multivariate polynomials
- On the irreducible factors of a polynomial
- Detecting prime numbers via roots of polynomials
- scientific article; zbMATH DE number 3882549 (Why is no real title available?)
- scientific article; zbMATH DE number 4152517 (Why is no real title available?)
- scientific article; zbMATH DE number 17387 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 3997938 (Why is no real title available?)
- scientific article; zbMATH DE number 3893304 (Why is no real title available?)
- scientific article; zbMATH DE number 3276887 (Why is no real title available?)
- scientific article; zbMATH DE number 4185767 (Why is no real title available?)
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Topics in multiplicative number theory
- Univariate polynomial factorization over finite fields
- On finding primitive roots in finite fields
- On the construction of irreducible and primitive polynomials from \(\mathbb{F}_{q^m} [x]\) to \(\mathbb{F}_q [x]\)
- Sequences of irreducible polynomials over odd prime fields via elliptic curve endomorphisms
- Computational aspects of retrieving a representation of an algebraic geometry code
- Efficient indexing of necklaces and irreducible polynomials over finite fields
- scientific article; zbMATH DE number 437575 (Why is no real title available?)
- A Cellular Automata Based Approach for Generation of Large Primitive Polynomial and Its Application to RS-Coded MPSK Modulation
- Fast algorithm for finding primitive polynomials over GF(q)
- A fast algorithm to compute irreducible and primitive polynomials in finite fields
- Efficient indexing of necklaces and irreducible polynomials over finite fields
- Fast construction of irreducible polynomials over finite fields
- Fast construction of irreducible polynomials over finite fields
- Factoring polynomials over finite fields: A survey
- Bounded distance decoding of linear error-correcting codes with Gröbner bases
- Search of primitive polynomials over finite fields
- Parity of the number of irreducible factors for composite polynomials
This page was built for publication: Finding irreducible and primitive polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1311621)
