Function PollardsRhoFactorization

math/pollard.go:31–45

PollardsRhoFactorization is an implementation of Pollard's rho factorization algorithm using the default parameters x = y = 2

(n *big.Int, f func(n *big.Int) func(x *big.Int) *big.Int)

// 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
}