using System;
using System.Numerics;

namespace Algorithms.Other
{
    /// <summary>
    ///     Fermat's prime tester https://en.wikipedia.org/wiki/Fermat_primality_test.
    /// </summary>
    public static class FermatPrimeChecker
    {
        /// <summary>
        ///     Checks if input number is a probable prime.
        /// </summary>
        /// <param name="numberToTest">Input number.</param>
        /// <param name="timesToCheck">Number of times to check.</param>
        /// <returns>True if is a prime; False otherwise.</returns>
        public static bool IsPrime(int numberToTest, int timesToCheck)
        {
            // You have to use BigInteger for two reasons:
            //   1. The pow operation between two int numbers usually overflows an int
            //   2. The pow and modular operation is very optimized
            var numberToTestBigInteger = new BigInteger(numberToTest);
            var exponentBigInteger = new BigInteger(numberToTest - 1);

            // Create a random number generator using the current time as seed
            var r = new Random(default(DateTime).Millisecond);

            var iterator = 1;
            var prime = true;

            while (iterator < timesToCheck && prime)
            {
                var randomNumber = r.Next(1, numberToTest);
                var randomNumberBigInteger = new BigInteger(randomNumber);
                if (BigInteger.ModPow(randomNumberBigInteger, exponentBigInteger, numberToTestBigInteger) != 1)
                {
                    prime = false;
                }

                iterator++;
            }

            return prime;
        }
    }
}