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

Ivanyos, Gábor; Karpinski, Marek; Rónyai, Lajos; Saxena, Nitin

doi:10.1090/S0025-5718-2011-02505-6

Trading GRH for algebra: Algorithms for factoring polynomials and related structures
HTML articles powered by AMS MathViewer

by Gábor Ivanyos, Marek Karpinski, Lajos Rónyai and Nitin Saxena PDF

Math. Comp. 81 (2012), 493-531 Request permission

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

László Babai and Lajos Rónyai, Computing irreducible representations of finite groups, Math. Comp. 55 (1990), no. 192, 705–722. MR 1035925, DOI 10.1090/S0025-5718-1990-1035925-1
Eric Bach, Joachim von zur Gathen, and Hendrik W. Lenstra Jr., Factoring polynomials over special finite fields, Finite Fields Appl. 7 (2001), no. 1, 5–28. Dedicated to Professor Chao Ko on the occasion of his 90th birthday. MR 1803933, DOI 10.1006/ffta.2000.0306
E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x
Paul Camion, A deterministic algorithm for factorizing polynomials of $\textbf {F}_q[X]$, Combinatorial mathematics (Marseille-Luminy, 1981) North-Holland Math. Stud., vol. 75, North-Holland, Amsterdam, 1983, pp. 149–157. MR 841289
Qi Cheng and Ming-Deh A. Huang, Factoring polynomials over finite fields and stable colorings of tournaments, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 233–245. MR 1850608, DOI 10.1007/10722028_{1}2
Alexander Chistov, Gábor Ivanyos, and Marek Karpinski, Polynomial time algorithms for modules over finite dimensional algebras, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (Kihei, HI), ACM, New York, 1997, pp. 68–74. MR 1809971, DOI 10.1145/258726.258751
Arjeh M. Cohen, Gábor Ivanyos, and David B. Wales, Finding the radical of an algebra of linear transformations, J. Pure Appl. Algebra 117/118 (1997), 177–193. Algorithms for algebra (Eindhoven, 1996). MR 1457838, DOI 10.1016/S0022-4049(97)00010-8
David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
S. A. Evdokimov, Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 176 (1989), no. Teor. Slozhn. Vychisl. 4, 104–117, 153 (Russian, with English summary); English transl., J. Soviet Math. 59 (1992), no. 3, 842–849. MR 1023599, DOI 10.1007/BF01104107
Sergei Evdokimov, Factorization of polynomials over finite fields in subexponential time under GRH, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 209–219. MR 1322724, DOI 10.1007/3-540-58691-1_{5}8
K. Friedl, L. Rónyai, Polynomial time solutions of some problems of computational algebra; Proc. 17th ACM STOC (1985), pp. 153-162.
Shuhong Gao, On the deterministic complexity of factoring polynomials, J. Symbolic Comput. 31 (2001), no. 1-2, 19–36. Computational algebra and number theory (Milwaukee, WI, 1996). MR 1806204, DOI 10.1006/jsco.1999.1001
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
Willem A. de Graaf, Michael Harrison, Jana Pílniková, and Josef Schicho, A Lie algebra method for rational parametrization of Severi-Brauer surfaces, J. Algebra 303 (2006), no. 2, 514–529. MR 2255120, DOI 10.1016/j.jalgebra.2005.06.022
Willem A. de Graaf and Gábor Ivanyos, Finding splitting elements and maximal tori in matrix algebras, Interactions between ring theory and representations of algebras (Murcia), Lecture Notes in Pure and Appl. Math., vol. 210, Dekker, New York, 2000, pp. 95–105. MR 1758404
Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
Ming-Deh A. Huang, Generalized Riemann hypothesis and factoring polynomials over finite fields, J. Algorithms 12 (1991), no. 3, 464–481. MR 1114921, DOI 10.1016/0196-6774(91)90014-P
Dale Husemoller, Elliptic curves, Graduate Texts in Mathematics, vol. 111, Springer-Verlag, New York, 1987. With an appendix by Ruth Lawrence. MR 868861, DOI 10.1007/978-1-4757-5119-2
G. Ivanyos, M. Karpinski, N. Saxena, Schemes for Deterministic Polynomial Factoring, Proc. 34th ISSAC (2009), 191-198.
Valentine Kabanets and Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Comput. Complexity 13 (2004), no. 1-2, 1–46. MR 2105971, DOI 10.1007/s00037-004-0182-6
Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
Neeraj Kayal and Nitin Saxena, Complexity of ring morphism problems, Comput. Complexity 15 (2006), no. 4, 342–390. MR 2324421, DOI 10.1007/s00037-007-0219-8
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.
Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723, DOI 10.1007/978-1-4612-0853-2
Serge Lang, Algebra, 3rd ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002. MR 1878556, DOI 10.1007/978-1-4613-0041-0
H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329–347. MR 1052099, DOI 10.1090/S0025-5718-1991-1052099-2
Maurice Mignotte and Claus Schnorr, Calcul déterministe des racines d’un polynôme dans un corps fini, C. R. Acad. Sci. Paris Sér. I Math. 306 (1988), no. 12, 467–472 (French, with English summary). MR 939433
Robert T. Moenck, On the efficiency of algorithms for polynomial factoring, Math. Comp. 31 (1977), no. 137, 235–250. MR 422193, DOI 10.1090/S0025-5718-1977-0422193-8
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
Lajos Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), no. 3, 391–400. MR 955147, DOI 10.1016/0196-6774(88)90029-6
L. Rónyai, Factoring polynomials modulo special primes, Combinatorica 9 (1989), no. 2, 199–206. MR 1030373, DOI 10.1007/BF02124680
Lajos Rónyai, Computing the structure of finite algebras, J. Symbolic Comput. 9 (1990), no. 3, 355–373. MR 1056632, DOI 10.1016/S0747-7171(08)80017-X
Lajos Rónyai, Galois groups and factoring polynomials over finite fields, SIAM J. Discrete Math. 5 (1992), no. 3, 345–365. MR 1172743, DOI 10.1137/0405026
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
Greg Stein, Factoring cyclotomic polynomials over large finite fields, Finite fields and applications (Glasgow, 1995) London Math. Soc. Lecture Note Ser., vol. 233, Cambridge Univ. Press, Cambridge, 1996, pp. 349–354. MR 1433158, DOI 10.1017/CBO9780511525988.026
Greg Stein, Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields, Math. Comp. 70 (2001), no. 235, 1237–1251. MR 1709159, DOI 10.1090/S0025-5718-00-01233-3
Christiaan van de Woestijne, Deterministic equation solving over finite fields, ISSAC’05, ACM, New York, 2005, pp. 348–353. MR 2280567, DOI 10.1145/1073884.1073932