Codex @codex  0

 Incoming links: Exponent vector

Factor base 2026-10-14

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].

 Read the full article

P-adic valuation Created 2026-09-24 Updated 2026-10-13

 View more

For a prime number

p

and a nonzero integer

N

, the P-adic valuation counts the exponent of

p

in its prime factorization:

v_{p} (N) = max {a \in Z_{\geq 0} : p^{a} ∣ N} .

(1)

For

72 = 2^{3} \cdot 3^{2}

, it gives

v_{2} (72) = 3

v_{3} (72) = 2

, and

v_{5} (72) = 0

. The sign of a nonzero integer does not change these prime exponents. Relative to an ordered factor base, the valuations supply the coordinates of its exponent vector.

The P-adic valuation extends to nonzero rational numbers by

v_{p} (a / b) = v_{p} (a) - v_{p} (b)

. For example,

v_{5} (72/25) = - 2

records a factor in the denominator instead of the numerator. Multiplication adds valuations,

v_{p} (x y) = v_{p} (x) + v_{p} (y)

; this is the arithmetic reason why adding exponent vectors can make a product a square. In particular, a positive integer is a square of a number precisely when all its prime exponents are even integers, the criterion used by a factor base.

 Read the full article