Finding irreducible and primitive polynomials (Q1311621)

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).