TheAlgorithms/Go · warning

factorization failed

Error message

factorization failed

What it means

PollardsRhoFactorization returns the error 'factorization failed' (math/pollard.go:41-43) when the rho cycle detection terminates with d == n. That means the GCD step collapsed to n itself for the whole run, so no proper non-trivial factor was found. This typically happens when n is prime (or a prime power where the sequence fails to separate) — Pollard's rho only finds non-trivial factors of composite numbers.

Source

Thrown at math/pollard.go:42

		xSquared.Mod(xSquared, n)
		return xSquared
	}
}

// PollardsRhoFactorization is an implementation of Pollard's rho factorization algorithm
// using the default parameters x = y = 2
func PollardsRhoFactorization(n *big.Int, f func(n *big.Int) func(x *big.Int) *big.Int) (*big.Int, error) {
	x, y, d := big.NewInt(2), big.NewInt(2), big.NewInt(1)
	bigOne := big.NewInt(1)
	g := f(n)
	for d.Cmp(bigOne) == 0 {
		x = g(x)
		y = g(g(y))
		sub := new(big.Int).Sub(x, y)
		d.GCD(nil, nil, sub.Abs(sub), n)
	}
	if d.Cmp(n) == 0 {
		return nil, errors.New("factorization failed")
	}
	return d, nil
}

View on GitHub (pinned to 5ba447ec5f)

Solutions

1. Run a primality test (e.g., Miller-Rabin) before calling and skip factorization for primes
2. Retry with a different polynomial function f (e.g., x^2+c with random c) when the error occurs
3. Handle small n (0, 1) separately before calling the function

Example fix

// before
d, err := math.PollardsRhoFactorization(n, math.DefaultPolynomial)
// after
if n ProbablyPrime(20) {
    return n, nil // n is prime, no factorization needed
}
d, err := math.PollardsRhoFactorization(n, math.DefaultPolynomial)
if err != nil {
    d, err = math.PollardsRhoFactorization(n, otherPolynomial) // retry
}

if n == nil || n.Cmp(big.NewInt(2)) < 0 || n.ProbablyPrime(20) {
    return errors.New("n must be an odd composite for Pollard rho")
}

d, err := math.PollardsRhoFactorization(n, math.DefaultPolynomial)
if err != nil {
    // retry with a different polynomial constant c
d, err = math.PollardsRhoFactorization(n, makePoly(3))
}

When it happens

Trigger: Calling math.PollardsRhoFactorization(n, f) with a prime n; with n == 1 or n == 0; occasionally with certain composite inputs where the default polynomial g(x)=x^2+1 mod n fails to find a factor in the first cycle (retrying with a different polynomial usually fixes it).

Common situations: Users assuming the function works for any n including primes, without a prior primality test; benchmark/tests generating random n that turn out prime; hard-coded polynomials whose cycle degenerates for the given n.

Related errors

• empty slice provided
• integer overflow
• negative Exponent provided
• no Modular Inverse exists
• interval boundaries should be finite numbers

AI-assisted analysis of TheAlgorithms/Go@5ba447ec5f (2026-09-02). Data as JSON: /api/errors/c7454201f2cffbc0. Report an issue: GitHub.