New algorithms for finding irreducible polynomials over finite fields

Shoup, Victor

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

New algorithms for finding irreducible polynomials over finite fields
HTML articles powered by AMS MathViewer

by Victor Shoup PDF

Math. Comp. 54 (1990), 435-447 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 polynomial-time reducible to the problem of factoring polynomials over the prime field.

References

Finding irreducible polynomials over finite fields

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592

Realistic analysis of some randomized algorithms

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/S0747-7171(08)80011-9
Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, 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/S0025-5718-1970-0276200-X
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/3-540-39568-7_{6}

Very fast parallel matrix and polynomial arithmetic

Efficient factorization of polynomials over finite fields and generalized Riemann hypothesis

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/3-540-17179-7_{1}5
Joachim von zur Gathen, Factoring polynomials and primitive elements for special primes, Theoret. Comput. Sci. 52 (1987), no. 1-2, 77–89. MR 918114, DOI 10.1016/0304-3975(87)90081-8
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/S0025-5718-1985-0790658-X

Riemann hypothesis and finding roots over finite fields

Randomized algorithms and pseudorandom numbers

A time-randomness tradeoff for oblivious routing

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., Addison-Wesley 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, Springer-Verlag, Berlin-New 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

Finding witnesses using fewer random bits

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/0020-0190(90)90195-4

Theory of equations

A general method of synthesizing irreducible polynomials over Galois fields

29

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