Algorithmic properties of maximal orders in simple algebras over Q |
| |
Authors: | Lajos Rónyai |
| |
Affiliation: | (1) Computer and Automation Institute, Hungarian Academy of Sciences, Victor Hugo u. 18-22, H-1132 Budapest, HUNGARY |
| |
Abstract: | This paper addresses an algorithmic problem related to associative algebras. We show that the problem of deciding if the index of a given central simple algebra
over an algebraic number field isd, whered is a given natural number, belongs to the complexity classN P co N P. As consequences, we obtain that the problem of deciding if
is isomorphic to a full matrix algebra over the ground field and the problem of deciding if
is a skewfield both belong toN P co N P. These results answer two questions raised in 25]. The algorithms and proofs rely mostly on the theory of maximal orders over number fields, a noncommutative generalization of algebraic number theory. Our results include an extension to the noncommutative case of an algorithm given by Huang for computing the factorization of rational primes in number fields and of a method of Zassenhaus for testing local maximality of orders in number fields. |
| |
Keywords: | 68Q40 11Y40 68Q25 11Y16 |
本文献已被 SpringerLink 等数据库收录! |
|