using System;
using Algorithms.Numeric.GreatestCommonDivisor;

namespace Algorithms.Other
{
    /// <summary>Implementation of the Pollard's rho algorithm.
    /// Algorithm for integer factorization.
    /// Wiki: https://en.wikipedia.org/wiki/Pollard's_rho_algorithm.
    /// </summary>
    public static class PollardsRhoFactorizing
    {
        public static int Calculate(int number)
        {
            var x = 2;
            var y = 2;
            var d = 1;
            var p = number;
            var i = 0;
            var gcd = new BinaryGreatestCommonDivisorFinder();

            while (d == 1)
            {
                x = Fun_g(x, p);
                y = Fun_g(Fun_g(y, p), p);
                d = gcd.FindGcd(Math.Abs(x - y), p);
                i++;
            }

            return d;
        }

        private static int Fun_g(int x, int p)
        {
            return (x * x + 1) % p;
        }
    }
}