The True Mathematical Structure of the General Number Field Sieve (GNFS)

The ultimate goal of GNFS is to find $X^2 \equiv Y^2 \pmod N$. To achieve this, mathematicians built a bridge between the “world of real integers” and the “world of algebraic number fields”. That bridge is the “homomorphism”.

Stage 1: The “Homomorphism” Connecting Worlds

1. Polynomial Selection and Root Definition

For a massive composite number $N$, select an integer $m$ and a polynomial $f(x)$ such that $f(m) \equiv 0 \pmod N$. (Example: Expand $N$ in base $m$ and create $f(x)$ from its coefficients. Here, assume $f(x)$ is irreducible (cannot be factored further) over the field of rational numbers $\mathbb{Q}$).

Next, let one of the “complex roots” of the equation $f(x) = 0$ be $\alpha$. Naturally, $f(\alpha) = 0$. $\alpha$ is not an integer but a complex number (an algebraic number) that may involve square roots or imaginary numbers.

2. Construction of Rings and Homomorphisms

Now, prepare two mathematical “rings” (worlds where addition and multiplication are defined).

• World A: $\mathbb{Z}[\alpha]$ (Ring of algebraic integers containing $\alpha$) A world of numbers represented in the form $a + b\alpha + c\alpha^2 + \dots$.
• World B: $\mathbb{Z}/N\mathbb{Z}$ (Ring of residues modulo $N$) A modulo arithmetic world consisting only of integers from $0$ to $N-1$.

Here, we define a mapping $\phi$ from World A to World B as follows: $$\phi : \mathbb{Z}[\alpha] \to \mathbb{Z}/N\mathbb{Z}$$ $$\phi(\alpha) = m \pmod N$$

This mapping $\phi$ is a magical operation that completely replaces the variable $\alpha$ in World A with the integer $m$ in World B. This $\phi$ possesses an extremely powerful property known as a “Ring Homomorphism”. A homomorphism is the property of “warping to another world without breaking the structure of addition and multiplication”. In other words, the following equations hold:

• $\phi(X \times Y) = \phi(X) \times \phi(Y)$
• $\phi(X^2) = \phi(X)^2$

What does this mean? If we can create a “square ($\gamma^2$)” of some complex element $\gamma$ in “World A (the world of $\alpha$)”, warping it to “World B (the modulo world)” via $\phi$ will ** perfectly preserve the square form $\phi(\gamma)^2$**.

Stage 2: The Collapse of Prime Factorization and the Birth of the “Ideal”

We want to collect many appropriate elements $(a - b\alpha)$ in World A ($\mathbb{Z}[\alpha]$) and multiply them together to create a “perfect square (square element)”. Normally, we could simply “prime factorize” each collected $(a - b\alpha)$ and combine them (solving via matrices) so that all prime exponents become even, thus creating a square.

However, here a devastating wall of algebra stands in our way. In algebraic number fields like $\mathbb{Z}[\alpha]$, the “uniqueness of prime factorization (any number can be uniquely expressed as a product of primes in exactly one way)”, which we learn in middle school, collapses.

(Example: In a certain algebraic number field, $6 = 2 \times 3$, but at the same time $6 = (1+\sqrt{-5}) \times (1-\sqrt{-5})$, making it impossible to know which are the true primes.)

If prime factorization is not uniquely determined, the puzzle (sieve method) of “counting the number of primes to make them even” becomes fundamentally impossible to execute.

The Salvation by Kummer and Dedekind: The “Ideal”

What saved us from this collapse was the concept of the “Ideal (ideal number)” created by 19th-century mathematicians. By considering not the elements themselves but the “set of multiples (ideals)” generated by those elements, they made prime factorization possible again.

In the ring of integers of an algebraic number field $\mathcal{O}_K$ (a more complete ring containing $\mathbb{Z}[\alpha]$), even if elements cannot be uniquely prime-factorized, it is proven that “an ideal can always be uniquely prime-factorized into a product of ‘prime ideals ($\mathfrak{p}$)’ in exactly one way”.

Therefore, in GNFS, instead of factorizing the element $(a - b\alpha)$ itself, we perform prime ideal factorization on the principal ideal $\langle a - b\alpha \rangle$ that it generates.

Stage 3: Norms and the Two Sieves

So, how do we know which prime ideals the ideal $\langle a - b\alpha \rangle$ factors into? Here, we use a function called the “Norm”. The norm is a function that converts complex elements of an algebraic number field into “ordinary real integers $\mathbb{Z}$”.

The norm of the element $(a - b\alpha)$ can be calculated by a simple polynomial calculation $b^d f(a/b)$ (where $d$ is the degree of $f(x)$).

Due to algebraic theorems, it is known that “if the norm of a certain ideal can be completely factored into small primes (is smooth), then the original ideal can also be completely factored into small prime ideals.”

Thus, GNFS simultaneously calculates the following two values for a massive number of integer pairs $(a, b)$ and collects only the pairs where both values are “smooth numbers”.

1. Rational Sieve: $a - bm$ (Values in the real world)
2. Algebraic Sieve: $b^d f(a/b)$ (Norm in the algebraic number field world)

By collecting tens of millions of pairs $(a, b)$ where both are smooth, and solving the prime factorization data of ideals (how many prime ideals are included) as a giant matrix (linear algebra over GF(2)), we find a set $S$ of pairs such that “when multiplied together, the exponents of all prime ideals become even”.

Stage 4: The Two Confronting “Obstructions” and the Ideal Class Group

Through matrix calculations, we found that multiplying all the ideals of $(a - b\alpha)$ belonging to set $S$ results in the square of a certain ideal $I$.

However, it doesn’t end here. The deepest and most difficult mathematical wall in GNFS lies here.

What we ultimately want is not the “square of an ideal”, but the “square of an element ($\gamma^2$)” to plug into the mapping $\phi$. Just because the ideal is squared doesn’t necessarily mean the element itself is squared. There exist two formidable mathematical obstructions here.

Obstruction 1: The Wall of the Ideal Class Group

The ideal $I$ is not always an “ideal generated by a single element (principal ideal)”. It is impossible to extract a concrete element $\gamma$ from an ideal that is not principal.

Here, the concept of the “Ideal Class Group ($Cl_K$)” comes into play. The ideal class group is a group that measures “how many non-principal ideals exist in that algebraic number field (how much the uniqueness of prime factorization is broken)”. Even if $\prod \langle a - b\alpha \rangle$ becomes $I^2$, if $I$ is not the identity element (principal ideal) in the ideal class group, it cannot be pulled back to the square of an element.

Obstruction 2: The Wall of the Unit Group

Suppose we get lucky and $I$ is a principal ideal $\langle \gamma \rangle$. Then, $\prod \langle a - b\alpha \rangle = \langle \gamma^2 \rangle$. You might think, “Great, the element is squared too!”, but that is a huge mistake.

The fact that ideals (sets of multiples) are equal does not mean the elements are completely equal. A deviation by a “Unit (a number whose reciprocal is also an integer, like 1 or -1)” inevitably occurs. In other words, the actual equality of the elements is as follows:

($u$ is an element of the unit group $U_K$)

Unless this unit $u$ itself is the square of something (a square element), the left side can absolutely never become a “perfect square of an element”.

Stage 5: Adleman’s Magic “Quadratic Characters”

The obstruction of the ideal class group and the obstruction of the unit group. How do we overcome these two? Here, a genius method called “Quadratic Characters”, introduced by cryptographer Leonard Adleman (the “A” in RSA) and others, makes its appearance.

To determine “whether a certain element is a perfect square in the algebraic number field”, we use an algebraic number field version of the Legendre symbol (quadratic residue). To the giant matrix from earlier (the puzzle to make the count of prime ideals even), we secretly append dozens of additional conditions (columns) stating that “the quadratic characters for some special prime ideals $\mathfrak{q}$ also all become $1$ (even)”.

When we find a set $S$ that satisfies even these additional conditions through matrix calculations, deep theorems of algebraic number theory guarantee that “both the obstruction of the ideal class group and the obstruction of the unit group will naturally vanish with overwhelming probability.”

With this, we finally obtain the true equation.

Final Stage: The Convergence of Worlds and the Fall of Encryption

Finally, all the pieces of the puzzle are in place.

[Element in the Algebraic Number Field World (World A)] $\gamma^2 = \prod (a - b\alpha)$ (We find $\gamma$ from this using a square root algorithm)

[Element in the Real World (World of Rational Numbers)] $V^2 = \prod (a - bm)$ (Since this is just ordinary integer multiplication, the square root $V$ can be found normally)

Now, it’s time for the magical bridge we built at the very beginning, the homomorphism $\phi$, to take the stage. We warp the element $\gamma$ from World A to World B (the world modulo $N$) using $\phi$ (the mapping that substitutes $m$ for $\alpha$).

Meanwhile, we take the $V$ created in the real world directly to the modulo world and call it $X$.

Due to the homomorphism’s property of “preserving structure”, the square relationship that held in World A is perfectly preserved in World B (the world modulo $N$) as well. Furthermore, because the original pairs $(a, b)$ were correspondingly created in the forms $a - b\alpha$ and $a - bm$, these $X$ and $Y$ collide in the world modulo $N$ to produce the following absolute equation:

$$X^2 \equiv Y^2 \pmod N$$

All that is left is to pray that these $X$ and $Y$ are not trivial solutions ($X \equiv \pm Y$) and calculate: $\gcd(X - Y, N)$

If it is a non-trivial solution, the Euclidean algorithm will race through in 0.001 seconds, and the secret primes $p$ and $q$, which are the heart of RSA encryption, will be printed on the output screen.

This is the complete form of the “General Number Field Sieve (GNFS)”, gathering the essence of modern mathematics.