Simple algebras are difficult

ABSTRACT

Let F be a finite field or an algebraic number field. In previous work we have shown how to find the basic building blocks (the radical and the simple components) of a finite dimensional algebra over F in polynomial time (deterministically in characteristic zero and Las Vegas in the finite case). Here we address the more general problem of finding zero divisors in A. This problem is equivalent to finding a nontrivial common invariant subspace of a set of linear operators and includes, as a subcase, the problem of factoring polynomials over the field in question. In [FR] the problem of zero divisors has been reduced, in polynomial time (Las Vegas in the finite case), to the case of simple algebras. We show that, while zero divisors can be found in Las Vegas polynomial time if F is finite, the problem over the rationals might be substantially more difficult. We link the problem to hard number theoretic problems such as quadratic residuosity modulo a composite number. We show that assuming the Generalized Riemann Hypothesis, there exists a randomized polynomial time reduction from quadratic residuosity to determining whether or not a given 4-dimensional algebra over Q has zero divisors. It will follow that finding a pair of zero divisors is at least as hard as factoring squarefree integers. As for the finite case, we give a polynomial time Las Vegas method to construct explicit isomorphisms of matrix algebras. Applications include an algorithm to solve the problem of finding common invariant subspaces for a set of linear operators. Another application answers a question of W. M. Kantor on permutation groups. Finally, as another application of the GRH, we mention a partial result on deterministic factoring over finite fields.

REFERENCES

• Ba: L. Babai, Monte-Carlo algorithms in graph isomorphism testing; Tech. Rep. 79-10, Dep. Math. Star., Universite de Montreal, 1979.
• B: Eric Bach, Fast algorithms under the extended riemann hypothesis: A concrete estimate, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.290-295, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802203]
• Be1: E. R. Ber}ekamp, Algebraic coding theory; McGraw-Hill, 1968.
• Be2: E. R. Berlekamp, Factoring polynomials over large finite fields; Math. of Computation 24, 1970, 713-715.
• Cas: J. W. S. Cassels, Rational quadratic forms; Academic Press, 1978.
• FR: K Friedl , L Rónyai, Polynomial time solutions of some problems of computational algebra, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.153-162, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22162]
• GJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• GM: Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
• H: I. N. Herstein, Noncommutatiw: rings; Math. Association of America, 1968.
• Hu1: Ming-Deh A. Huang, Factorization of polynomials over finite fields and factorization of primes in algebraic number fields, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.175-182, December 1984 [doi>10.1145/800057.808679]
• Hu2: M-D A Huang, Riemann hypothesis and finding roots over finite fields, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.121-130, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22159]
• IR: K. Ireland, M. Rosen, A classical introduction to modern number theory; Springer-Verlag, 1982.
• KMS: E. Kaltofen, D. R. Musser, D. Saunders, A generalized class of polynomials that are hard to factor; SIAM Journal on Computing, vol. 12, no .3, 1983, 473-483.
• K: Ravi Kannan, Improved algorithms for integer programming and related lattice problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.193-206, December 1983 [doi>10.1145/800061.808749]
• L: J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms; Journal of Algorithms, vol. 1, 1980, 142-186.
• LO: J. C. Lagarias, A. M. Odlyzko, Effective versions of the Chebotarev density theorem; Algebraic number fields (L- functions and Galois theory) A. Frhlich, ed., Academic Press 1977, 409-464.
• Lu: E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time; J. Comput. $yst. Sci. 25, 1982, 42-65.
• Mi: G. Miller, Riemann's hypothesis and tests for prireality; J. Comput. System Sci. 13, 1976, 300-317.
• NZ: I. Niven, H. S. Zuckerman, All introduction to the theory of numbers; (third ed.) John Wiley and Sons 1971.
• O'M: 0. T. O'Meara, Introduction to quadratic forms; Springer- Verlag 1963.
• P: R. S. Pierce, Associative algebras; Springer-Verlag 1982.
• PS: John M. Pollard , Claus P. Schnorr, An efficient solution of the congruence x2+ky2=m (modn), IEEE Transactions on Information Theory, v.33 n.5, p.702-709, September 1, 1987 [doi>10.1109/TIT.1987.1057350]
• Ra: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• Ra1: M. O Rabin, Probabilistic algorithms in finite fields; SIAM Journal on Computing, Vol 9, No 2, 1980, 273-280.
• R1: L. R6nyai, Zero divisors and invariant subspaces; University of Oregon TechnicM Report CiS-TR 85-11, 1985.
• R2: L. R6nyai, Factoring polynomials over finite fields, submitted for publication

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  G. Mathematics of Computing

General Terms:
Algorithms, Theory, Verification