We consider two problems. First let u be an element of a quaternion algebra B over Q(d~(1/2)) such that u is non-central and u~2 ∈ Q. We relate the complexity of finding an element v' such that uv' = -v'u and v'~2 ∈ Q to a fundamental problem studied earlier. For the second problem assume that A (≌) M_2(Q(d~(1/2))). We propose a polynomial (randomized) algorithm which finds a non-central element l ∈ A such that l~2 ∈ Q. Our results rely on the connection between solving quadratic forms over Q and splitting quaternion algebras over Q, and Castel's algorithm which finds a rational solution to a non-degenerate quadratic form over Q in 6 dimensions in randomized polynomial time. We use these two results to construct a four dimensional subalgebra over Q of A which is a quaternion algebra. We also apply our results to analyze the complexity of constructing involutions.
展开▼
