Factor base

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for

- 1

, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy

N = 77

, use factor base

{2, 3, 5}

and the two relations

1 3^{2} \equiv 15 = 3 \cdot 5 (mod 77), 4 0^{2} \equiv 60 = 2^{2} \cdot 3 \cdot 5 (mod 77) .

(1)

The residues have exponent vectors

(0, 1, 1)

and

(2, 1, 1)

in the order

(2, 3, 5)

. Adding the two vectors modulo two gives

(0, 0, 0)

, so multiplying the residues gives

15 \cdot 60 = 900 = 3 0^{2}

. Consequently

(13 \cdot 40)^{2} \equiv 3 0^{2} (mod 77), X = 13 \cdot 40 mod 77 = 58, Y = 30,

(2)

and $g cd (X - Y, 77) = 7$ and $g cd (X + Y, 77) = 11$ . Neither individual residue was a square; combining the relations made all exponents even.

Figure 1.
A factor base turns two smooth relations into a congruence of squares through exponent parity
. The original $N = 77$ example uses the ordered factor base $(2, 3, 5)$ . The rows $(0, 1, 1)$ and $(2, 1, 1)$ add to zero modulo two, giving residue product $900 = 3 0^{2}$ . The product of the original inputs is $520 \equiv 58 (mod 77)$ ; greatest common divisor calculations then extract seven and eleven. **Details**.

In a larger collection, choose relations

x_{i}^{2} \equiv r_{i} (mod N)

with positive residues

r_{i} = \prod_{j = 1}^{B} p_{j}^{e_{ji}}

. If a nonempty selection

I

has an even sum in every exponent coordinate, set

X = \prod_{i \in I} x_{i} mod N, Y = \prod_{j = 1}^{B} p_{j}^{\frac{1}{2} \sum_{i \in I} e_{ji}} mod N .

(3)

Then

X^{2} \equiv Y^{2} (mod N)

. Finding such a selection is a linear dependence problem over the finite field

F_{2}

: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

Table of contents
- Exponent vector Factor base
  - Prime-exponent difference Exponent vector

Exponent vector ( $e (r) = (e_{1}, \dots, e_{B})$ )

 0  0

Relative to an ordered factor base

(p_{1}, \dots, p_{B})

, a positive integer

r = \prod_{j} p_{j}^{e_{j}}

has exponent vector

(e_{1}, \dots, e_{B})

. Multiplication of such integers adds their exponent vectors. Reducing every coordinate modulo two gives the parity vector used to find congruences of squares. The ordering and any sign coordinate must be used consistently across all rows.