DefaultPolynomial is the commonly used polynomial g(x) = (x^2 + 1) mod n
(n *big.Int)
| 16 | |
| 17 | // DefaultPolynomial is the commonly used polynomial g(x) = (x^2 + 1) mod n |
| 18 | func DefaultPolynomial(n *big.Int) func(*big.Int) *big.Int { |
| 19 | bigOne := big.NewInt(1) |
| 20 | bigTwo := big.NewInt(2) |
| 21 | return func(x *big.Int) *big.Int { |
| 22 | xSquared := new(big.Int).Exp(x, bigTwo, n) // see: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Core_ideas |
| 23 | xSquared.Add(xSquared, bigOne) |
| 24 | xSquared.Mod(xSquared, n) |
| 25 | return xSquared |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | // PollardsRhoFactorization is an implementation of Pollard's rho factorization algorithm |
| 30 | // using the default parameters x = y = 2 |