I have a ring $R$ which is known to be a Dedekind domain, but not necessarily a Euclidian domain, and a nonzero ideal generated by one or two elements in this ring. How can I check if this ideal is a prime ideal?
For ideals generated by one element, this is equivalent to being a prime element in the ring. I programmed a clone of the Erathosthenes sieve for my ring, but this only shows me which elements are irreducible, which does not necessarily imply primality.
To be more concrete, my ring $R$ is the ring of integers in an imaginary quadratic number field $\mathbb{Q}(d)$ (for $d$ a negative squarefree integer).
These rings are of the form $R = \mathbb{Z}[\sqrt{-d}]$ or $R = \mathbb{Z}[\frac{1+\sqrt{-d}}{2}]$, depending on $d$. These are Dedekind domains, and every ideal there is generated by either one or two elements.
For some $d$ (like $-1$, $-2$, $-3$), these are Euclidean domains, where I can use the division with remainder to find the greatest common divisor of two numbers, meaning that each ideal is generated by one element.
For others (like $d = -7$), there is no division with remainder, and we can't use the Euclidean algorithm.
But even here it is not yet clear for me: how do I distinguish irreducible from prime elements? The most famous example: for $d = -5$ we have $R = \mathbb{Z}[\sqrt{-5}]$, and the element $2$ is not prime here, since $2 \cdot 3 = 6 = (1+\sqrt{-5})\cdot(1-\sqrt{-5})$ and 2 is not a factor of either term on the right side.
By testing multiples, I can find numbers with different decompositions, and then know that those factors can't be prime. But when can I stop searching, if I don't find any?
In this particular ring, the first elements not yet shown as either units, irreducible-not-prime or composite (after checking all elements until about $\pm 50 \pm 50i$) are $\pm \sqrt{-5}$, $\pm 4 \pm 2\sqrt{-5}$, $\pm 6 \pm \sqrt{-5}$. Could I be sure here that there really are prime?
Another example, $d = -7$, $R = \mathbb{Z}[\frac{1+\sqrt{-7}}{2}] = \mathbb{Z}[X]/(X^2+X+2)$: Here I find lots of irreducible-non-prime elements, and the only small "irreducible and not yet shown as non-prime" are $\pm \frac{1-\sqrt{-7}}{2}$. (The principal ideal generated by these elements look quite same as the one created by $\frac{1+\sqrt{-7}}{2}$, though - I think there is simply a glitch in my program.)
This ring is non-Euclidean, and I suppose most (if not all but the zero ideal) prime ideals are generated by two elements here. If I have a candidate pair of elements, how do I find out if it is really a nonzero prime (= maximal) ideal?
Any ideas here would helpful, since I'm a bit stuck here. (Most literature about computational ideal theory I found only works in polynomial rings over fields (and makes heavy use of this fact), thus it does not really help here.)
(I'm writing a program which should then be able to work on any of these rings $R$ (and any ideals there), thus facts that are only valid in a small number of those rings are less helpful. But feel free to mention them nevertheless, maybe some of them can be generalized.)
To check if an ideal is prime, one way is to look at the quotient $R / I$; the ideal $I$ is prime if and only if $R / I$ is an integral domain.
To expand a bit on that: say you have two elements $(x, y)$, and you want to know if the ideal $I$ they generate is prime. This ideal $I$ certainly contains the elements $xx^*$ and $y y^*$ (where * is the Galois "conjugation" automorphism of R). These are in $\mathbb{Z}$, so they have a highest common factor; let's say that is $k$.
Then $kR$ is an ideal of $R$ contained in $I$. Moreover, the ring $R / k R$ is finite, and you can now describe $R / I$ by a finite computation, because it's a quotient of $R / kR$. In particular, you can check whether or not $R / I$ is a field.