Abstract
In the paper some new fast constructions of irreducible and primitive polynomials are presented. For instance, it is shown, that for anyQ large enough one can design a finite field\(\mathbb{F}\) q withq=Q + o(Q) elements in polynomial time (log Q)o(1).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Adleman, L. M., Lenstra, H. W.: Finding irreducible polynomials over finite fields. Proc. 18 ACM Symp. Theory Comp. 350–355 (1986)
Babaev, G.: The distribution of integer points over algebraic surfaces. Dushanbe, 1966 (in Russian)
Bach, E.: Number-theoretic algorithms. Ann Rev Comp. Sci.4, 119–172 (1990)
Chistov, A. L.: The construction of a finite field in polynomial time. Proc. 7 All-Union Conf. on Math. Logic. Novosibirsk, 1984, p. 196 (in Russian)
Cohen, S. D.: Primitive elements and polynomials: existence results. Preprint 91/65, Glasgow University, pp. 1–12 (1991)
Cohen, S. D.: The explicit construction of irreducible polynomials over finite fields. Preprint 91/71, Glasgow University, pp. 1–7 (1991)
Von zur Gathen, J.: Irreducible polynomials over finite fields. Lecture Notes in Comp. Sci. vol. 241, pp. 252–262. Berlin, Heidelberg, New York: Springer 1986
Evdokimov, S. A.: Factoring a solvable polynomial over a finite field and the Generalized Riemann Hypothesis. Zapiski Nauchn. Semin. Leningr. Otdel. Matem. Inst. Acad. Sci. USSR, 1989, vol. 176, pp. 104–117 (in Russian)
Lidl, R., Niederreiter, H.: Finite fields. New York: Addison-Wesley 1983
MacWilliams F. J., Sloane, N. J. A.: The theory of error-correcting codes. Amsterdam: North-Holland 1977
Montgomery, H. L.: Topics in multiplicative number theory. Lecture Notes in Mathematics, vol. 227 Berlin, Heidelberg, New York: Springer 1971
Pomerance, C.: Factoring. Cryptology and Computational Number Theory. Proc. Symp. Appl. Math.42, 27–47 (1990)
Semaev, I. I.: Construction of irreducible polynomials over finite fields with linearly independent roots. Matem. Sbornik 135(4), 520–532 (in Russian) (1988)
Shoup, V.: Removing randomness from computational number theory. Computer Science Technical Report no. 865 University Wisconsin Madison, 1989
Shoup, V.: New algorithms for finding irreducible polynomials over finite fields. Math. Comp.54(189), 435–447 (1990)
Shoup, V.: Searching for primitive roots in finite fields. Proc. 22 ACM Symp. on Theory of Comp. 546–554 (1990)
Shparlinski, I. E.: On primitive elements in finite fields and on elliptic curves. Matem. Sbornik 181(9), 1196–1206 (in Russian) (1990)
Shparlinski, I. E.: On some problems of theory of finite fields. Uspechi Matem. Nauk 36(1), 165–200 (in Russian) (1991)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Shparlinski, I.E. Finding irreducible and primitive polynomials. AAECC 4, 263–268 (1993). https://doi.org/10.1007/BF01200150
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01200150