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, p\equiv 3\bmod 4$ 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?
For example, we take $p = 2^{76}3^{15}-1$, it is easy to know that $1+j+k$ is a prime element, since its norm is 2168345519443636233418208968703( a prime). If an element can be factor as $a = bc$, then we have Norm($a$) = Norm($b$)Norm($c$). It is clear to see that it is a prime element in $\mathcal{O}$.
To our best knowledge, this question is solved when the $\mathcal{O}$ is a Hurwitz order Hurwitz, 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}\cdots 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.