For Eisenstein numbers $a + b\frac{1+\sqrt{3} i}{2}$ with $0 \le a, b \le n$ how can I efficiently identify all of the primes?

Question

This answer to determining if a coincident point in a pair of rotated hexagonal lattices is closest to the origin? teaches that my real question was how to find if two Eisenstein integers are coprime.

The answer outlines in great detail how to implement the Euclidian algorithm for Eisenstein integers.

It begins:

Set $u := \frac{1+\sqrt{3} i}{2}$. Consider the set $\{a+bu\mid a,b\in\mathbb{Z}\}$. Since $u^2=u-1$, a product of two such numbers belongs to this set as well. I will denote this set $\mathbb{Z}[u]$.^[1]

[1] Actually, $\mathbb{Z}[u]$ means the set of all numbers of the form $a_0+a_1u+\dots+a_ku^k$, where $k\in\mathbb{Z}_{\geq 0}$ and $a_0,\dots,a_k\in \mathbb{Z}$; but since $u^2=u-1$, this is the set I described.

If I was now interested in first testing each Eisenstein integer separately first to see if it was prime, how would I do that short of checking to see if it was coprime with a large number of other Eisenstein integers?

Question: For Eisenstein numbers $a + b\frac{1+\sqrt{3} i}{2}$ with $0 \le a, b \le n$ how can I efficiently identify all of the primes?

Is there an algorithm similar/related to the Euclidian algorithm that I could use to test each number without exhaustively excluding all possible coprimes? Or perhaps a completely different algorithm?

---

click for larger

Eisenstein-Jacobi Primes from Unsolved Problems in Number Theory Third Edition, Richard K. Guy, Springer, 2004, (A16 Gaussian and Eisenstein-Jacobi primes, pp 55-57)

Answer 1

This can be enumerated in some effective manner.

We know that the norm $$N(a+b\omega)=\left(a+b\left(\frac{1+\sqrt{3}i}{2}\right)\right)\left(a+b\left(\frac{1-\sqrt{3}i}{2}\right)\right)=a^2+ab+b^2$$.

Now, if we know $|a|,|b|<n$ so $N(a+b\phi)\leq 3n^2$.

For each prime $p\in \mathbb{Z}$, that sits inside the interval $[0,3n^2]$, you can test whether $p$ is an irreducible in $\mathbb{Z}[\omega]$.

If not, $p=(a+b\omega)(a+b\bar{\omega})$ and then $a+b\omega$ (and $a+b\bar{\omega}=a+b\omega^2=(a-b)-b\omega$) are irreducibles in $\mathbb{Z}[\omega]$. Now you can test whether these coefficients do sit inside your given interval.

Answer 2

Call an Eisenstein integer a good number if it is $a+bu$ for some nonnegative integers $a$ and $b$, where $u=a+b\frac{1+\sqrt3i}2$. If we split the entire complex plane into six equal sectors by lines $x=0$, $y=ux$ and $y=u^2x$, the good number are the Eisenstein numbers that are in the same sector as $1+u$.

An algorithm that checks if a good number is an Eisenstein prime

Here is the algorithm that determines whether a good number $a+bu$ is an Eisenstein prime.

1. If $a=b=1$, return True.
2. If $b=0$ and $a$ is an ordinary prime number that is $2\,\text{mod}\,3$, return TRUE.
3. If $a\not=b\pmod3$ and $a^2+ab+b^2$ is an ordinary prime number, return TRUE.
4. Return FALSE.

(Step 1 and step 2 can be combined as one step: If $a^2+ab+b^2$ is an ordinary prime number, return TRUE.)

The time-complexity of the algorithm depends on how we compute whether an ordinary integer is prime. Suppose we use the most common and simple way by checking whether it is a multiple of an integer at least 2 and at most the square root of it. Then the time-complexity of the algorithm is $O(\max(a,b))$.

List all prime good numbers a+bu where $0\le a,b\le n$

A simple algorithm is just listing all those good numbers and one by one checking if it is an Eisenstein prime as above. The time-complexity is $O(n^3)$.

Here is a faster algorithm, the time-complexity of which is $O(n^2\log \log n)$ if an ordinary Eratosthenes sieve is used to list ordinary primes numbers. If we use a linear sieve instead, the time-complexity is $O(n^2)$.

1. Output $1+u$.
2. Output $p+0u$ and $0+pu$ for each ordinary prime number $p\le n$ that is $2\,\text{mod}\,3$.
3. Compute the set of all ordinary prime numbers $\le 3n^2$.
   For each pairs of positive numbers $(a,b)$ such that $a<b$ and $a^2+ab+b^2$ is a member of that set, output $a+bu$ and $b+au$.