{"record":{"id":"c7454201f2cffbc0","repo":"TheAlgorithms/Go","slug":"factorization-failed","errorCode":null,"errorMessage":"factorization failed","messagePattern":"factorization failed","errorType":"validation","errorClass":null,"httpStatus":null,"severity":"warning","filePath":"math/pollard.go","lineNumber":42,"sourceCode":"\t\txSquared.Mod(xSquared, n)\n\t\treturn xSquared\n\t}\n}\n\n// PollardsRhoFactorization is an implementation of Pollard's rho factorization algorithm\n// using the default parameters x = y = 2\nfunc PollardsRhoFactorization(n *big.Int, f func(n *big.Int) func(x *big.Int) *big.Int) (*big.Int, error) {\n\tx, y, d := big.NewInt(2), big.NewInt(2), big.NewInt(1)\n\tbigOne := big.NewInt(1)\n\tg := f(n)\n\tfor d.Cmp(bigOne) == 0 {\n\t\tx = g(x)\n\t\ty = g(g(y))\n\t\tsub := new(big.Int).Sub(x, y)\n\t\td.GCD(nil, nil, sub.Abs(sub), n)\n\t}\n\tif d.Cmp(n) == 0 {\n\t\treturn nil, errors.New(\"factorization failed\")\n\t}\n\treturn d, nil\n}\n","sourceCodeStart":24,"sourceCodeEnd":46,"githubUrl":"https://github.com/TheAlgorithms/Go/blob/5ba447ec5ff3d1213de65b92e726ee74c5d5cc19/math/pollard.go#L24-L46","documentation":"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.","triggerScenarios":"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).","commonSituations":"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.","solutions":["Run a primality test (e.g., Miller-Rabin) before calling and skip factorization for primes","Retry with a different polynomial function f (e.g., x^2+c with random c) when the error occurs","Handle small n (0, 1) separately before calling the function"],"exampleFix":"// before\nd, err := math.PollardsRhoFactorization(n, math.DefaultPolynomial)\n// after\nif n ProbablyPrime(20) {\n    return n, nil // n is prime, no factorization needed\n}\nd, err := math.PollardsRhoFactorization(n, math.DefaultPolynomial)\nif err != nil {\n    d, err = math.PollardsRhoFactorization(n, otherPolynomial) // retry\n}","handlingStrategy":"retry","validationCode":"if n == nil || n.Cmp(big.NewInt(2)) < 0 || n.ProbablyPrime(20) {\n    return errors.New(\"n must be an odd composite for Pollard rho\")\n}","typeGuard":null,"tryCatchPattern":"d, err := math.PollardsRhoFactorization(n, math.DefaultPolynomial)\nif err != nil {\n    // retry with a different polynomial constant c\nd, err = math.PollardsRhoFactorization(n, makePoly(3))\n}","preventionTips":["Run a Miller-Rabin primality test first and handle primes separately","Retry with different polynomial constants c on failure","Handle n < 2 (and even n: return 2 immediately) outside the rho call","Treat this as a probabilistic algorithm: loop attempts until success"],"tags":["go","math","factorization","probabilistic-algorithm"],"backgroundTag":"factorization-failed","analyzedSha":"5ba447ec5ff3d1213de65b92e726ee74c5d5cc19","analyzedAt":"2026-09-02T21:54:30.227Z","contentChangedAt":null,"schemaVersion":2},"datasetVersion":"2026-09-10T02:17:09.455Z"}