New algorithms for finding irreducible polynomials over finite fields

Author:
Victor Shoup

Journal:
Math. Comp. **54** (1990), 435-447

MSC:
Primary 11T06; Secondary 11Y16

DOI:
https://doi.org/10.1090/S0025-5718-1990-0993933-0

MathSciNet review:
993933

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new algorithm for finding an irreducible polynomial of specified degree over a finite field. Our algorithm is deterministic, and it runs in polynomial time for fields of small characteristic. We in fact prove the stronger result that the problem of finding irreducible polynomials of specified degree over a finite field is deterministic polynomial-time reducible to the problem of factoring polynomials over the prime field.

**[1]**L. Adleman and H. Lenstra,*Finding irreducible polynomials over finite fields*, in Proc 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 350-355.**[2]**A. Aho, J. Hopcroft, and J. Ullman,*The design and analysis of computer algorithms*, Addison-Wesley, 1974. MR**0413592 (54:1706)****[3]**E. Bach,*Realistic analysis of some randomized algorithms*, in Proc. 19th Annual ACM Sympos. on Theory of Computing, 1987, pp. 453-461.**[4]**E. Bach and V. Shoup,*Factoring polynomials using fewer random bits*, Computer Sciences Technical Report No. 757, University of Wisconsin-Madison, 1988. (To appear, J. Symb. Comput.) MR**1056625 (91h:11149)****[5]**E. Berlekamp,*Algebraic coding theory*, McGraw-Hill, 1968. MR**0238597 (38:6873)****[6]**-,*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), pp. 713-735. MR**0276200 (43:1948)****[7]**P. Camion,*Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials*, IEEE Trans. Inform. Theory**29**(1983), pp. 378-385. MR**712404 (84k:12008)****[8]**B. Chor and R. Rivest,*A knapsack type public key cryptosystem based on arithmetic in finite fields*, in Advances in Cryptology: Proceedings of Crypto 84, Lecture Notes in Comput. Sci., vol. 144, Springer-Verlag, 1984, pp. 54-65. MR**820013****[9]**W. Eberly,*Very fast parallel matrix and polynomial arithmetic*, in Proc. 25th Annual Sympos. on Foundations of Computer Science, 1984, pp. 21-30.**[10]**S. Evdokimov,*Efficient factorization of polynomials over finite fields and generalized Riemann hypothesis*, preprint, Leningrad Institute for Informatics and Automatization, USSR Academy of Sciences, 1986.**[11]**J. von zur Gathen,*Irreducible polynomials over finite fields*, Computer Sciences Technical Report No. 188/86, University of Toronto, 1986. MR**889924 (89c:11176)****[12]**-,*Factoring polynomials and primitive elements for special primes*, Theoret. Comput. Sci.**52**(1987), 77-89. MR**918114 (89a:11126)****[13]**J. von zur Gathen and E. Kaltofen,*Factorization of multivariate polynomials over finite fields*, Math. Comp.**45**(1985), 251-261. MR**790658 (87a:12005)****[14]**M. Huang,*Riemann hypothesis and finding roots over finite fields*, in Proc. 17th Annual ACM Sympos. on Theory of Computing, 1985, pp. 121-130.**[15]**H. Karloff and P. Raghavan,*Randomized algorithms and pseudorandom numbers*, in Proc. 20th Annual ACM Sympos. on Theory of Computing, 1988, pp. 310-321.**[16]**D. Krizanc, D. Peleg, and E. Upfal,*A time-randomness tradeoff for oblivious routing*, in Proc. 20th Annual ACM Sympos. on Theory of Computing, 1988, pp. 93-102.**[17]**J. Lagarias, H. Montgomery, and A. Odlyzko,*A bound for the least prime ideal in the Chebotarev density theorem*, Invent. Math.**54**(1979), 271-296. MR**553223 (81b:12013)****[18]**S. Lang,*Algebra*, 2nd ed., Addison-Wesley, 1984. MR**783636 (86j:00003)****[19]**M. Rabin,*Probabilistic algorithms in finite fields*, SIAM J. Comput.**9**(1980), 273-280. MR**568814 (81g:12002)****[20]**W. Schmidt,*Equations over finite fields--An elementary approach*, Lecture Notes in Math., vol. 536, Springer-Verlag, 1976. MR**0429733 (55:2744)****[21]**A. Schönhage,*Schnelle Multiplikation von Polynomen über Körpern der Charakteristik*2, Acta Inform.**7**(1977), pp. 395-398. MR**0436663 (55:9604)****[22]**V. Shoup,*Finding witnesses using fewer random bits*, Computer Sciences Technical Report no. 725, University of Wisconsin-Madison, 1987.**[23]**-,*On the deterministic complexity of factoring polynomials over finite fields*, Computer Sciences Technical Report No. 782, University of Wisconsin-Madison, 1988. (To appear, Inform. Process. Lett.) MR**1049276 (91f:11088)****[24]**J. Uspensky,*Theory of equations*, McGraw-Hill, 1948.**[25]**R. Varshamov,*A general method of synthesizing irreducible polynomials over Galois fields*, Soviet Math. Dokl.**29**(1984), no. 2, 334-336.**[26]**B. van der Waerden,*Algebra*, Vol. 1, 7th ed., Ungar, 1970. MR**0263582 (41:8187a)**

Retrieve articles in *Mathematics of Computation*
with MSC:
11T06,
11Y16

Retrieve articles in all journals with MSC: 11T06, 11Y16

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1990-0993933-0

Article copyright:
© Copyright 1990
American Mathematical Society