New algorithms for finding irreducible polynomials over finite fields
HTML articles powered by AMS MathViewer
 by Victor Shoup PDF
 Math. Comp. 54 (1990), 435447 Request permission
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 polynomialtime reducible to the problem of factoring polynomials over the prime field.References

L. Adleman and H. Lenstra, Finding irreducible polynomials over finite fields, in Proc 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 350355.
 Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, AddisonWesley Series in Computer Science and Information Processing, AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975. Second printing. MR 0413592 E. Bach, Realistic analysis of some randomized algorithms, in Proc. 19th Annual ACM Sympos. on Theory of Computing, 1987, pp. 453461.
 Eric Bach and Victor Shoup, Factoring polynomials using fewer random bits, J. Symbolic Comput. 9 (1990), no. 3, 229–239. MR 1056625, DOI 10.1016/S07477171(08)800119
 Elwyn R. Berlekamp, Algebraic coding theory, McGrawHill Book Co., New YorkToronto, Ont.London, 1968. MR 0238597
 E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025571819700276200X
 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, DOI 10.1109/TIT.1983.1056666
 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, DOI 10.1007/3540395687_{6} W. Eberly, Very fast parallel matrix and polynomial arithmetic, in Proc. 25th Annual Sympos. on Foundations of Computer Science, 1984, pp. 2130. 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.
 Joachim von zur Gathen, Irreducible polynomials over finite fields, Foundations of software technology and theoretical computer science (New Delhi, 1986) Lecture Notes in Comput. Sci., vol. 241, Springer, Berlin, 1986, pp. 252–262. MR 889924, DOI 10.1007/3540171797_{1}5
 Joachim von zur Gathen, Factoring polynomials and primitive elements for special primes, Theoret. Comput. Sci. 52 (1987), no. 12, 77–89. MR 918114, DOI 10.1016/03043975(87)900818
 J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp. 45 (1985), no. 171, 251–261. MR 790658, DOI 10.1090/S0025571819850790658X M. Huang, Riemann hypothesis and finding roots over finite fields, in Proc. 17th Annual ACM Sympos. on Theory of Computing, 1985, pp. 121130. H. Karloff and P. Raghavan, Randomized algorithms and pseudorandom numbers, in Proc. 20th Annual ACM Sympos. on Theory of Computing, 1988, pp. 310321. D. Krizanc, D. Peleg, and E. Upfal, A timerandomness tradeoff for oblivious routing, in Proc. 20th Annual ACM Sympos. on Theory of Computing, 1988, pp. 93102.
 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, DOI 10.1007/BF01390234
 Serge Lang, Algebra, 2nd ed., AddisonWesley Publishing Company, Advanced Book Program, Reading, MA, 1984. MR 783636
 Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
 Wolfgang M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, SpringerVerlag, BerlinNew York, 1976. MR 0429733
 A. Schönhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Informat. 7 (1976/77), no. 4, 395–398. MR 0436663, DOI 10.1007/bf00289470 V. Shoup, Finding witnesses using fewer random bits, Computer Sciences Technical Report no. 725, University of WisconsinMadison, 1987.
 Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276, DOI 10.1016/00200190(90)901954 J. Uspensky, Theory of equations, McGrawHill, 1948. R. Varshamov, A general method of synthesizing irreducible polynomials over Galois fields, Soviet Math. Dokl. 29 (1984), no. 2, 334336.
 B. L. van der Waerden, Algebra. Vol 1, Frederick Ungar Publishing Co., New York, 1970. Translated by Fred Blum and John R. Schulenberger. MR 0263582
Additional Information
 © Copyright 1990 American Mathematical Society
 Journal: Math. Comp. 54 (1990), 435447
 MSC: Primary 11T06; Secondary 11Y16
 DOI: https://doi.org/10.1090/S00255718199009939330
 MathSciNet review: 993933