Stage 4: Square Root Step

The Final Step

The linear algebra stage gave us sets of relations whose exponents sum to even values. Now we combine these relations to form a congruence of squares:

x² ≡ y² (mod n)

Once we have this, we can often factor n using:

gcd(x - y, n)

Computing x and y

For each dependency (set of relation indices), we compute:

• x: Product of all rational_values from selected relations (mod n)
• y: Square root of the product of all algebraic_values

Since the exponents sum to even values, the product of algebraic values is a perfect square, so we can compute its integer square root exactly.

Why Does This Work?

The key insight is the relationship between the algebraic and rational sides. For each relation (a, b):

• Algebraic side: b^df(a/b) factors over the algebraic number field
• Rational side: a - mb factors over the integers

Because f(m) ≡ 0 (mod n), these two sides are connected modulo n. When we multiply relations whose exponents sum to even values, both products become perfect squares that are congruent mod n.

Extracting Factors

When It Fails

Sometimes gcd(x - y, n) gives a trivial factor (1 or n). This happens when x ≡ ±y (mod n). In that case, we try another dependency from the nullspace basis. With enough relations, we almost always find a non-trivial factor.