| Abstract: | Let F be a finite field or an algebraic number field. In previous papers 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). A finite-dimensional simple algebra A is a full matrix algebra over some not necessarily commutative extension field G of F. The problem remains to find G and an isomorphism between A and a matrix algebra over G. This, too, can be done in polynomial time for finite F. We indicate in the present paper that the problem for F = Q 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. |
