Fermat Prime Checker Algorithm
In abstract algebra, objects that behave in a generalized manner like prime numbers include prime components and prime ideals. A prime number (or a prime) is a natural number greater than 1 that is not a merchandise of two smaller natural numbers. method that are restricted to specific number forms include Pépin's test for Fermat numbers (1877), Proth's theorem (c. 1878), the Lucas – Lehmer primality test (originated 1856), and the generalized Lucas primality test., the Islamic mathematician Ibn al-Haytham (Alhazen) found Wilson's theorem, characterizing the prime numbers as the numbers N, that evenly divide (N-1)!+1.
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;
}
}
}
