MillerRabinPrimalityChecker.cs

usingSystem;
usingSystem.Numerics;

namespaceAlgorithms.Numeric;

/// <summary>
/// https://en.wikipedia.org/wiki/Miller-Rabin_primality_test
/// The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test:
/// an algorithm which determines whether a given number is likely to be prime,
/// similar to the Fermat primality test and the Solovay–Strassen primality test.
/// It is of historical significance in the search for a polynomial-time deterministic primality test.
/// Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known.
/// </summary>
publicstaticclassMillerRabinPrimalityChecker
{
/// <summary>
/// Run the probabilistic primality test.
/// </summary>
/// <param name="n">Number to check.</param>
/// <param name="rounds">Number of rounds, the parameter determines the accuracy of the test, recommended value is Log2(n).</param>
/// <param name="seed">Seed for random number generator.</param>
/// <returns>True if is a highly likely prime number; False otherwise.</returns>
/// <exception cref="ArgumentException">Error: number should be more than 3.</exception>
publicstaticboolIsProbablyPrimeNumber(BigIntegern,BigIntegerrounds,int?seed=null)
{
Randomrand=seedisnull
?new()
:new(seed.Value);
returnIsProbablyPrimeNumber(n,rounds,rand);
}

privatestaticboolIsProbablyPrimeNumber(BigIntegern,BigIntegerrounds,Randomrand)
{
if(n<=3)
{
thrownewArgumentException($"{nameof(n)} should be more than 3");
}

// Input #1: n > 3, an odd integer to be tested for primality
// Input #2: k, the number of rounds of testing to perform, recommended k = Log2(n)
// Output: false = “composite”
// true = “probably prime”

// write n as 2r·d + 1 with d odd(by factoring out powers of 2 from n − 1)
BigIntegerr=0;
BigIntegerd=n-1;
while(d%2==0)
{
r++;
d/=2;
}

// as there is no native random function for BigInteger we suppose a random int number is sufficient
intnMaxValue=(n>int.MaxValue)?int.MaxValue:(int)n;
BigIntegera=rand.Next(2,nMaxValue-2);// ; pick a random integer a in the range[2, n − 2]

while(rounds>0)
{
rounds--;
varx=BigInteger.ModPow(a,d,n);
if(x==1||x==(n-1))
{
continue;
}

BigIntegertempr=r-1;
while(tempr>0&&(x!=n-1))
{
tempr--;
x=BigInteger.ModPow(x,2,n);
}

if(x==n-1)
{
continue;
}

returnfalse;
}

returntrue;
}
}