Gaußsche Zahlen/Primfaktorzerlegung/Algorithmische Bestimmung/Verfahren

Für eine Gaußsche Zahl ${}z\in \mathbb {Z} [{\mathrm {i} }]$ kann man folgendermaßen entscheiden, ob sie prim ist bzw. wie ihre Primfaktorzerlegung aussieht:

1. Berechne die Norm ${}N(z)$. Ist diese eine Primzahl, so ist nach Fakt das Element ${}z$ selbst prim.
2. Bestimme die (ganzzahligen) Primfaktoren von ${}N(z)$. Schreibe

   ${}N(z)=z{\overline {z}}=2^{r}p_{1}\cdots p_{s}q_{1}\cdots q_{t}\,,$

   wobei die ${}p_{i}$ ungerade mit Rest ${}1$ modulo ${}4$ und die ${}q_{j}$ ungerade mit Rest ${}3$ modulo ${}4$ seien.

3. Schreibe ${}p_{i}=N(u_{i})=u_{i}{\overline {u_{i}}}$ für die Primfaktoren ${}p_{i}$ mit Rest ${}1$ modulo ${}4$, und ${}2^{r}=(-{\mathrm {i} })^{r}(1+{\mathrm {i} })^{2r}$. Damit ist

   ${}z{\overline {z}}=(-{\mathrm {i} })^{r}(1+{\mathrm {i} })^{2r}u_{1}{\overline {u_{1}}}\cdots u_{s}{\overline {u_{s}}}q_{1}\cdots q_{t}\,.$

4. Liste die möglichen Primfaktoren von ${}z$ (und zugleich von ${}{\overline {z}}$) auf: das sind ${}1+{\mathrm {i} }$ (falls ${}2$ mit positivem Exponenten vorkommt), die ${}u_{i}$ und ${}{\overline {u_{i}}}$ sowie die ${}q_{j}$ (da ${}\mathbb {Z} [{\mathrm {i} }]$ ein Hauptidealbereich ist und somit nach Fakt die eindeutige Primfaktorzerlegung gilt, setzt sich die Primfaktorzerlegung von ${}z$ und von ${}{\overline {z}}$ bis auf Einheiten aus Primfaktoren der rechten Seite zusammen).
5. Durch ${}(1+{\mathrm {i} })^{r}$ und die ${}q_{j}$ kann man sofort durchdividieren, da diese Faktoren jeweils sowohl von ${}z$ als auch von ${}{\overline {z}}$ ein Faktor sind.
6. Für die möglichen Primfaktoren ${}u_{i}$ und ${}{\overline {u_{i}}}$ muss man (durch Division mit Rest) überprüfen, ob sie Primfaktoren von ${}z$ sind oder nicht (wenn nicht, so teilen sie ${}{\overline {z}}$). Statt Division kann man auch die möglichen Kombinationen ausmultiplizieren.