Return to Question

1. Compute fundamental units $u_1, u_2 \in \mathcal{O}_K^\times$.
2. Use Hilbert's Theorem 90 to construct $c \in K^\times$ such that $$ c \cdot \sigma(c) = u_i, $$ for a generator $\sigma \in \mathrm{Gal}(K/\mathbb{Q})$.
3. We expect that the norm $N_{K/\mathbb{Q}}(c)$ is nontrivially related to the factorization of $N$, so that a factor can be recovered via a gcd computation.

1. Compute fundamental units $u_1, u_2 \in \mathcal{O}_K^\times$.
2. Use Hilbert's Theorem 90 to construct $c \in K^\times$ such that $$ u_i = \frac{c}{\sigma(c)}, $$ for a generator $\sigma \in \mathrm{Gal}(K/\mathbb{Q})$.
3. We expect that the norm $N_{K/\mathbb{Q}}(c)$ is nontrivially related to the factorization of $N$, so that a factor can be recovered via a gcd computation.

Unlike the number field sieve, where there are many chances for success if the final congruence is trivial and 'we do not expect inordinate amounts of bad luck' in taking different kernel vectors from the linear algebra, here we appear to have very limited flexibility:

Unlike the number field sieve, where there are many chances for success if the final congruence is trivial and we do not expect inordinately long strings of bad luck in taking different kernel vectors from the linear algebra, here we appear to have very limited flexibility:

$$ f(t) = 4t^3 - 3Nt - Ny, $$

$$ f(t) = 4t^3 - 3Nt - Nx, $$