Let $K$ be a number field and $N$ a positive integer. To find $\alpha \in \mathcal{O}_K$ with $N_{K/\mathbb{Q}}(\alpha) = N$, factor both sides ideally:

If $(\alpha) = \prod \mathfrak{p}_i^{e_i}$, then $N(\alpha) = \prod N(\mathfrak{p}_i)^{e_i}$. Factor $N$ and search for combinations of prime ideals with the correct norm.

For $K = \mathbb{Q}(i)$, finding representations $N = a^2 + b^2$ reduces to finding $\alpha = a + bi \in \mathbb{Z}[i]$ with $N(\alpha) = N$, which exists if and only if all primes $p \equiv 3 \pmod{4}$ occur to even powers in $N$.

The class number formula connects analytic and algebraic invariants: $h_K = \frac{w_K \sqrt{|\Delta_K|}}{2^{r_1}(2\pi)^{r_2}} \cdot \text{Res}_{s=1} \zeta_K(s)$

where:

• $w_K$ = number of roots of unity in $K$
• $r_1$ = number of real embeddings
• $r_2$ = number of complex conjugate pairs of embeddings
• $\zeta_K(s)$ = Dedekind zeta function

This formula shows $h_K < \infty$ and enables computational determination of class numbers.

Algorithms for factoring integers leverage number field sieves:

1. Number Field Sieve (NFS): Select $K$ with small discriminant related to target integer $N$
2. Find elements $\alpha \in \mathcal{O}_K$ with smooth norms (factor into small primes)
3. Build matrix of relations among prime ideals
4. Solve linear algebra to find dependencies yielding factors of $N$

This algorithm has complexity $\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$, substantially faster than trial division or quadratic sieve.