#### Fermat Prime Checker

J
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;
}
}
}