Тест Миллера-Рабина

 private void button_go_Click(object sender, EventArgs e)
        {
            int m = Convert.ToInt32(textBox_number.Text); //Число
            int r = Convert.ToInt32(textBox_rounds.Text); //Количество раундов
            if (miller_rabin(m, r)) textBox_result.Text = "Число простое!";
            else textBox_result.Text = "Число составное!";
        }
 
        public bool miller_rabin(int m, int r) //false - составное, true - простое
        {
            int s = 0, t = m - 1; Random rand = new Random();
            //Каноническое разложение числа m = 2^s*t
            while (true)
            {
                t = t / 2; s++;
                if (prost(t)) break;
            }
            //
            //Цикл А
            //
            for (int i = 0; i < r; i++)
            {
                int a = rand.Next(2, m - 2);
                int x = step(a, t, m);
                if (x != 1 || x != m - 1)  //Цикл B
                {
                    for (int j = 0; j < s - 1; j++)
                    {
                        x = step(x, 2, m);
                        if (x == 1) return false;
                        if (x == m - 1) break;
                    }
                    return false;
                }
            }
            return true;
        }

if (prost(t))

public bool prost(int a) 
        {
            for (int i = 2; i < a / 2 + 1; i++)
            {
                if (a % i == 0) return false;
            }
            return true;
        }

public int step(int a, int b, int mod) // Нахожддение числа по модулю
        {
            int res = 1;
            for (int i = b; i > 0; i--)
            {
                res = res * a;
                if (res > mod)
                {
                    res = res % mod;
                }
            }
            /*if (res - mod == -1)
            {
                return -1;
            }*/
            return res;
        }

 public bool miller_rabin(int m, int r)
{
   return prost(m);
}

//http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Algorithm_and_running_time
        static bool MillerRabinTest(int n, int k)
        {
            if (n <= 1)
                return false;
            if (n == 2)
                return true;
            if (n%2 == 0)
                return false;
            int s = 0, d = n - 1;
            while (d%2 == 0)
            {
                d /= 2;
                s++;
            }
 
            var rand = new Random();
 
            for (int i = 0; i < k; i++)
            {
                long a = rand.Next(2, n - 1);
                int x = (int) BigInteger.ModPow(a, d, n);
                if (x == 1 || x == n - 1)
                    continue;
                for (int j = 0; j < s - 1; j++)
                {
                    x = (x*x)%n;
                    if (x == 1)
                        return false;
                    if (x == n - 1)
                        break;
                }
                if (x != n-1)
                    return false;
            }
            return true;
        }

class Program
    {
        static void Main(string[] args)
        {
            int[] ints = {561, 1105, 31};
            foreach (int x in ints)
            {
                Console.WriteLine($"{x} - IsPrime: {MillerRabinTest(x, 10)}");
            }
        }
 
        //http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Algorithm_and_running_time
        public static bool MillerRabinTest(int n, int k)
        {
            if (n < 2)
                return false;
            if (n == 2)
                return true;
            if (n%2 == 0)
                return false;
            int r = 0, d = n - 1;
            while (d%2 == 0)
            {
                d /= 2;
                r++;
            }
 
            var rand = new Random();
 
            for (int i = 0; i < k; i++)
            {
                int a = rand.Next(2, n - 1);
                BigInteger x = BigInteger.ModPow(a, d, n);
                if (x == 1 || x == n - 1)
                    continue;
                for (int j = 0; j < r - 1; j++)
                {
                    x = BigInteger.ModPow(x, 2, n);
                    if (x == 1)
                        return false;
                    if (x == n - 1)
                        break;
                }
                if (x != n - 1)
                    return false;
            }
            return true;
        }
    }