#### Miller-Rabin primality check

```using System;
using System.Numerics;

namespace Algorithms.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>
public static class MillerRabinPrimalityChecker
{
/// <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>
public static bool IsProbablyPrimeNumber(BigInteger n, BigInteger rounds, int? seed = null)
{
Random rand = seed is null
? new()
: new(seed.Value);
}

private static bool IsProbablyPrimeNumber(BigInteger n, BigInteger rounds, Random rand)
{
if (n <= 3)
{
throw new ArgumentException(\$"{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)
BigInteger r = 0;
BigInteger d = 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
int nMaxValue = (n > int.MaxValue) ? int.MaxValue : (int)n;
BigInteger a = rand.Next(2, nMaxValue - 2); // ; pick a random integer a in the range[2, n − 2]

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

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

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

return false;
}

return true;
}
}
}
```  