using System;

public class Program

{

    public static void Main()

    {

        // decimal: precision gives accurate answer, but only works up to num = 19, 

        // double: does not get overflow exceptions but does not have enough 

        //   precision to accurately resolve the key arithmetic condition: n^(p-1) % p != 1  -> prime

        decimal num = 19;

        int tries = 12;

        bool prime = isPrime(num, tries);

​

        Console.WriteLine("{0} is {1}a prime number.", num, prime ? "" : "not ");

    }

    public static decimal YthPowerOfX(int x, int y) // ex. 7^9

    {

        if (y == 0)

            return 1;

        string binary = Convert.ToString(y, 2); // 1001

        decimal lastPower = x;

        decimal power = binary[binary.Length - 1] == '1' ? x : 1; // 7

        checked {

            for (int i = binary.Length - 2; i >= 0; i--)

            {

                lastPower *= lastPower; // 7 * 7 = 49 // 49 * 49 = 2401 // 2401 * 2401 = 5764801

​

                if (binary[i] == '1')

                    power *= lastPower; // 7 * 5764801 = 40353607

            }

        }

        return power;

    }

    // probabilistic algorithm - one that produces a correct result with a certain probablility

    public static bool isPrime(decimal num, int maxTries)

    {

        // check maxTries times, 1/2^maxTries = probablity of false positive

        for (int i = 0; i <= maxTries; i++)

        {

            // get a random number between 1 and x

            Random rand = new Random();

            int r = rand.Next(1, (int)num);

            decimal power = YthPowerOfX(r, (int)num - 1);

            Console.WriteLine($"{r}^{num-1} => {power} % {num} = {power % num}");

            if (power % num != 1) // n^(p-1) % p != 1  -> prime

                return false;

        }

        // passed Fermat's "little theorem" maxTries times, number is prime with (1 - 1/2^maxTries)*100 percent certainty

        return true;

    }

}