FermatPrimeChecker.cs

usingSystem;
usingSystem.Numerics;

namespaceAlgorithms.Other;

/// <summary>
/// Fermat's prime tester https://en.wikipedia.org/wiki/Fermat_primality_test.
/// </summary>
publicstaticclassFermatPrimeChecker
{
/// <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>
publicstaticboolIsPrime(intnumberToTest,inttimesToCheck)
{
// 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
varnumberToTestBigInteger=newBigInteger(numberToTest);
varexponentBigInteger=newBigInteger(numberToTest-1);

// Create a random number generator using the current time as seed
varr=newRandom(default(DateTime).Millisecond);

variterator=1;
varprime=true;

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

iterator++;
}

returnprime;
}
}