New algorithms for finding irreducible polynomials over finite fields

Shoup, Victor

doi:10.1090/S0025-5718-1990-0993933-0

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

New algorithms for finding irreducible polynomials over finite fields

Author: Victor Shoup
Journal: Math. Comp. 54 (1990), 435-447
MSC: Primary 11T06; Secondary 11Y16
MathSciNet review: 993933
Full-text PDF Free Access

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] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. 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] Eric Bach and Victor Shoup, Factoring polynomials using fewer random bits, J. Symbolic Comput. 9 (1990), no. 3, 229–239. MR 1056625 (91h:11149), http://dx.doi.org/10.1016/S0747-7171(08)80011-9
[5] Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York, 1968. MR 0238597 (38 #6873)
[6] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 0276200 (43 #1948), http://dx.doi.org/10.1090/S0025-5718-1970-0276200-X
[7] Paul F. Camion, Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials, IEEE Trans. Inform. Theory 29 (1983), no. 3, 378–385. MR 712404 (84k:12008), http://dx.doi.org/10.1109/TIT.1983.1056666
[8] Benny Chor and Ronald L. Rivest, A knapsack type public key cryptosystem based on arithmetic in finite fields (preliminary draft), Advances in cryptology (Santa Barbara, Calif., 1984) Lecture Notes in Comput. Sci., vol. 196, Springer, Berlin, 1985, pp. 54–65. MR 820013, http://dx.doi.org/10.1007/3-540-39568-7_6
[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] Joachim von zur Gathen, Irreducible polynomials over finite fields, (New Delhi, 1986) Lecture Notes in Comput. Sci., vol. 241, Springer, Berlin, 1986, pp. 252–262. MR 889924 (89c:11176), http://dx.doi.org/10.1007/3-540-17179-7_15
[12] Joachim von zur Gathen, Factoring polynomials and primitive elements for special primes, Theoret. Comput. Sci. 52 (1987), no. 1-2, 77–89. MR 918114 (89a:11126), http://dx.doi.org/10.1016/0304-3975(87)90081-8
[13] J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp. 45 (1985), no. 171, 251–261. MR 790658 (87a:12005), http://dx.doi.org/10.1090/S0025-5718-1985-0790658-X
[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. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, 271–296. MR 553223 (81b:12013), http://dx.doi.org/10.1007/BF01390234
[18] Serge Lang, Algebra, 2nd ed., Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1984. MR 783636 (86j:00003)
[19] Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814 (81g:12002), http://dx.doi.org/10.1137/0209024
[20] Wolfgang M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin, 1976. MR 0429733 (55 #2744)
[21] A. Schönhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Informat. 7 (1976/77), no. 4, 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] Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276 (91f:11088), http://dx.doi.org/10.1016/0020-0190(90)90195-4
[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. L. van der Waerden, Algebra. Vol 1, Translated by Fred Blum and John R. Schulenberger, Frederick Ungar Publishing Co., New York, 1970. MR 0263582 (41 #8187a)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|