What is known about the computational complexity of primality testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ where $d$ is a square-free number? For what values of $d$ is primality testing easy (i.e., can be determined in polynomial time)?

  • $\begingroup$ You mean in the ring of integers of a quadratic number field? $\endgroup$ Dec 19, 2011 at 17:35
  • $\begingroup$ Yes, sorry. I have edited my question—hopefully it is clearer now. $\endgroup$ Dec 19, 2011 at 17:39
  • 1
    $\begingroup$ $\mathbb{Z}[\sqrt{d}]$ isn't the full ring of integers if $d \equiv 1 \bmod 4$. $\endgroup$ Dec 19, 2011 at 17:43

1 Answer 1


For $K = \mathbb{Q}(\sqrt{d})$, primality testing in $\mathcal{O}_K$ reduces to primality testing of integers. It's known that the prime elements $\alpha \in \mathcal{O}_K$ are either

  • elements whose norms $N(\alpha)$ are prime, or
  • elements whose norms $N(\alpha)$ are squares of a prime $p$ such that $\left( \frac{d}{p} \right) = -1$.

(A slight modification is necessary in the case that $d \equiv 1 \bmod 4$ and $N(\alpha) = 4$. In that case $\alpha$ is prime if and only if $\frac{d-1}{4}$ is odd.)

The first condition can be tested for in polynomial time by the AKS primality test. The second condition can be tested for in polynomial time by AKS and quadratic reciprocity.

  • $\begingroup$ If you don't mind me asking, is there a result stating this? Could you perhaps point me in the right direction? Thanks in advance. $\endgroup$
    – tc1729
    Jan 28, 2014 at 1:55
  • 1
    $\begingroup$ @Siddharth: probably this result can be found in most textbooks on algebraic number theory, possibly as an exercise. $\endgroup$ Jan 28, 2014 at 2:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .