Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Trading GRH for algebra: Algorithms for factoring polynomials and related structures

Authors: Gábor Ivanyos, Marek Karpinski, Lajos Rónyai and Nitin Saxena
Journal: Math. Comp. 81 (2012), 493-531
MSC (2010): Primary 68W30, 12Y05, 16Z05
Published electronically: May 10, 2011
MathSciNet review: 2833506
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we develop a general technique to eliminate the assumption of the Generalized Riemann Hypothesis (GRH) from various deterministic polynomial factoring algorithms over finite fields. It is the first bona fide progress on that issue for more than 25 years of study of the problem. Our main results are basically of the following form: either we construct a nontrivial factor of a given polynomial or compute a nontrivial automorphism of the factor algebra of the given polynomial. Probably the most notable application of such automorphisms is efficiently finding zero divisors in noncommutative algebras. The proof methods used in this paper exploit virtual roots of unity and lead to efficient actual polynomial factoring algorithms in special cases.

References [Enhancements On Off] (What's this?)

  • [BR90] L. Babai, L. Rónyai, Computing irreducible representations of finite groups, Proc. 30th IEEE FOCS (1989) pp. 93-98; journal version appeared in Mathematics of Computation 55, 192 (1990), 705-722. MR 1035925 (91d:68057)
  • [BGL01] E. Bach, J. von zur Gathen, H. W. Lenstra, Jr., Factoring polynomials over special finite fields; Finite Fields and Their Applications 7(2001), 5-28. MR 1803933 (2001k:11252)
  • [Be67] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Technical Journal 46(1967), 1853-1859. MR 0219231 (36:2314)
  • [Cam83] P. Camion, A deterministic algorithm for factorizing polynomials of $ \mathbb{F}_q[x]$, Ann. Discr. Math., 17, (1983), 149-157. MR 841289 (87i:11177)
  • [CH00] Q. Cheng, M. A. Huang, Factoring Polynomials over Finite Fields and Stable Colorings of Tournaments, Algorithmic Number Theory Symposium (ANTS) IV, LNCS 1838, (2000), 233-245. MR 1850608 (2002g:11178)
  • [CIK97] A. Chistov, G. Ivanyos, M. Karpinski, Polynomial time algorithms for modules over finite dimensional algebras, Proc. ISSAC 1997, 68-74. MR 1809971
  • [CIW96] A. M. Cohen, G. Ivanyos, D. B. Wales, Finding the radical of an algebra of linear transformations, Journal of Pure and Applied Algebra, 117-118 (1997), 177-193. (Proc. MEGA'96.) MR 1457838 (98h:16026)
  • [CZ81] D. G. Cantor, H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Mathematics of Computation, 36(154), 1981, 587-592. MR 606517 (82e:12020)
  • [Ev89] S. A. Evdokimov, Factorization of a solvable polynomial over finite fields and the generalized Riemann Hypothesis, Zapiski Nauchnykh Seminarov LOMI, 176(1989), 104-117. MR 1023599 (91a:11063)
  • [Ev94] S. Evdokimov, Factorization of polynomials over finite fields in subexponential time under GRH, Proc. 1st ANTS, Lecture Notes In Computer Science 877, Springer-Verlag 1994. MR 1322724 (95m:11145)
  • [FR85] K. Friedl, L. Rónyai, Polynomial time solutions of some problems of computational algebra; Proc. 17th ACM STOC (1985), pp. 153-162.
  • [Gao01] S. Gao, On the deterministic complexity of factoring polynomials, J. of Symbolic Computation, 31(1-2), 2001, 19-36. MR 1806204 (2002c:11175)
  • [G87] J. von zur Gathen, Factoring polynomials and primitive elements for special primes, Theoretical Computer Science, 52, 1987, 77-89. MR 918114 (89a:11126)
  • [GHPS06] W. A. de Graaf, M. Harrison, J. Pilnikova, J. Schicho, A Lie algebra method for rational parametrization of Severi-Brauer surfaces, J. Algebra 303, 2006, 514-529. MR 2255120 (2007e:14058)
  • [GI00] W. A. de Graaf, G. Ivanyos, Finding splitting elements and maximal tori in matrix algebras, In: F. Van Oystaeyen, M. Saorin (eds), Interactions between Ring Theory and Representations of Algebras, (Proc. Euroconference in Murcia, 1998), Lecture Notes in Pure and Applied Mathematics 210, Marcel Dekker 2000, 95-105. MR 1758404 (2001f:16089)
  • [GS92] J. von zur Gathen, V. Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity, 2(1992), 187-224. MR 1220071 (94d:12011)
  • [Hua85] M. A. Huang, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM STOC (1985) pp. 121-130; journal version appeared in J. Algorithms, 12 (1991), 464-481. MR 1114921 (92j:68057)
  • [Hu86] D. Husemöller, Elliptic curves; Springer, 1986. MR 868861 (88h:11039)
  • [IKS08] G. Ivanyos, M. Karpinski, N. Saxena, Schemes for Deterministic Polynomial Factoring, Proc. 34th ISSAC (2009), 191-198.
  • [KI03] V. Kabanets, R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Proc. 35th ACM STOC (2003), 355-364; journal version appeared in Computational Complexity, 13 (2004), 1-46. MR 2105971 (2005i:68025)
  • [KS98] E. Kaltofen, V. Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp., 67 (1998), 1179-1197. MR 1459389 (99m:68097)
  • [KS05] N. Kayal, N. Saxena, On the Ring Isomorphism and Automorphism Problems, Proc. 20th IEEE Conference on Computational Complexity (2005) pp. 2-12; journal version appeared in Computational Complexity 15 (4), (2006), 342-390. MR 2324421 (2009g:68074)
  • [KU08] K. Kedlaya, C. Umans, Fast modular composition in any characteristic, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (2008) pp. 146-155.
  • [La80] S. Lang, Algebraic number theory, Springer-Verlag, 1980. MR 1282723 (95f:11085)
  • [La02] S. Lang, Algebra, Springer-Verlag, 2002. MR 1878556 (2003e:00003)
  • [L91] H. W. Lenstra, Finding isomorphisms between finite fields, Mathematics of Computation 56 (1991), 329-347. MR 1052099 (91d:11151)
  • [MS88] M. Mignotte, C.-P. Schnorr, Calcul déterministe des racines d''un polynôme dans un corps fini, Comptes Rendus Académie des Sciences (Paris), 306 (1988), 467-472. MR 939433 (89i:11134)
  • [Moe77] R. T. Moenck, On the efficiency of algorithms for polynomial factoring, Math. Comp., 31 (1977), 235-250. MR 0422193 (54:10185)
  • [PH78] S. Pohlig, M. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance, IEEE Transactions on Information Theory, 24 (1978), 106-110. MR 0484737 (58:4617)
  • [Rab80] M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput, 9 (1980), 273-280. MR 568814 (81g:12002)
  • [Ró87] L. Rónyai, Factoring Polynomials over finite fields, Proc. 28th IEEE FOCS (1987) pp. 132-137; journal version appeared in Journal of Algorithms, 9 (1988), 391-400 MR 955147 (89k:11124)
  • [Ró89a] L. Rónyai, Factoring polynomials modulo special primes, Combinatorica, 9 (1989), 199-206. MR 1030373 (90k:11161)
  • [Ró90] L. Rónyai, Computing the structure of finite algebras, Journal of Symbolic Computation, 9 (1990), 355-373. MR 1056632 (91h:68093)
  • [Ró89b] L. Rónyai, Galois Groups and Factoring Polynomials over Finite Fields, Proc. 30th IEEE FOCS (1989) pp. 99-104; journal version appeared in SIAM J. on Discrete Mathematics, 5 (1992), 345-365. MR 1172743 (94a:68055)
  • [Sch85] R. J. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, 44 (1985), 483-494. MR 777280 (86e:11122)
  • [S96] G. Stein, Factoring cyclotomic polynomials over large finite fields, Proceedings of the third international conference on finite fields and applications (1996) pp. 349-354. MR 1433158 (98b:11122)
  • [S01] G. Stein, Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields, Mathematics of Computation 70 (2001), 1237-1251. MR 1709159 (2001j:11119)
  • [W05] C. van de Woestijne, Deterministic equation solving over finite fields, Proc. ISSAC 2005, 348-353. MR 2280567

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 12Y05, 16Z05

Retrieve articles in all journals with MSC (2010): 68W30, 12Y05, 16Z05

Additional Information

Gábor Ivanyos
Affiliation: Computer and Automation Research Institute of the Hungarian Academy of Sciences, Lágymányosi u. 11, 1111 Budapest, Hungary.

Marek Karpinski
Affiliation: Department of Computer Science and Hausdorff Center for Mathematics, University of Bonn, 53117 Bonn, Germany

Lajos Rónyai
Affiliation: Computer and Automation Research Institute of the Hungarian Academy of Sciences, Lágymányosi u. 11, 1111 Budapest, Hungary and Department of Algebra, Budapest University of Technology and Economics, Műegyetem rkp. 3-9, 1111 Budapest, Hungary.

Nitin Saxena
Affiliation: Hausdorff Center for Mathematics, University of Bonn, 53115 Bonn, Germany

Received by editor(s): September 12, 2009
Received by editor(s) in revised form: November 10, 2010
Published electronically: May 10, 2011
Article copyright: © Copyright 2011 American Mathematical Society

American Mathematical Society