Let $H(-1,-p) = \mathbb{Q}+\mathbb{Q}i+\mathbb{Q}j+\mathbb{Q}k$ be the quaternion algebra over $\mathbb{Q}$ such that $i^2=-1, j^2=-p$ and the quaternion is ramified exactly at $p$ and $\infty$. $\mathcal{O}=\mathbb{Z}+\mathbb{Z}i+\mathbb{Z}j+\mathbb{Z}k$ is an order of the quaternion. We define an element $a\in \mathcal{O}$ is a prime if $a$ cannot be represent as the product of two non unit elements $b,c$, namely, $a=bc,$ where $b,c\in \mathcal{O}$ and $b$, $c$ are not units. The question is, given an element $ a\in \mathcal{O}$. How to efficiently test its primality?
To our best knowledge, this question is solved when the $\mathcal{O}$ is a Hurwitz order, we have no idea about this question when the quaternion algebra is not Hamilton. There exists a very trivial method. First we compute its norm $N$ and factor it $N=p_1^{e_1},\ldots, p_n^{e_n}$, next list all possible elements in the order with proper norm ,namely the factot of $N$ and test whether it is a factor of $a$. But this method is not efficiently.