using System;

public class Program

{

​

        public static void Main(string[] args)

        {

            try

            {

                TestRsaMaths();

                Console.WriteLine("Test completed.");

            }

            catch (Exception e)

            {

                Console.WriteLine(e);

            }

        }

​

​

        public static void TestRsaMaths()

        {

            var euclidResult = RSAMaths.EuclidsAlgo(649 * 11212, 649 * 231212);

            Console.WriteLine("The result of euclids algo with " + (649 * 11212) + " and " +  (649 * 231212) + " was " + euclidResult);

​

            var extendedResult = RSAMaths.ExtendedEuclidsAlgo(649 * 11231, 649 * 1232321);

            Console.WriteLine("The result of extended euclids with " + (649 * 11231) + " and " +  (649 * 1232321) + " was " + extendedResult);

​

            var modExResult = RSAMaths.ModEx(243234, 423423, 32313);

            Console.WriteLine("The result of modular exponentiation of " + (243234) + "^" +  (423423) + " Mod(" + (32313) + ") is " + modExResult);

​

            var weakPrimalityResult = RSAMaths.WeakPrimality(561);

            Console.WriteLine("The result of a weak primality test on " + 561 + " found it could " + (weakPrimalityResult ? "be prime." : "not be prime."));

​

            var strongPrimalityResult = RSAMaths.StrongPrimality(561);

            Console.WriteLine("The result of a strong primality test on " + 561 + " found it could " + (strongPrimalityResult? "be prime." : "not be prime."));

        }

}

public class Triple 

{

    public long d {get; set;}

    public long x {get; set;}

    public long y {get; set;}

    public override string ToString() 

    {

        return "(" + d + ", " + x + ", " + y + ")"; 

    }

    public Triple Set(long d, long x, long y)

    {

        this.d = d;

        this.x = x;

        this.y = y;

        return this;

    }

}

 public static class RSAMaths

 {

​

     public static long EuclidsAlgo(long a, long b)

     {

         if (b == 0)

             return a;

         return EuclidsAlgo(b, a % b);

     }

​

     public static Triple ExtendedEuclidsAlgo(long a, long b)

     {

         if (b == 0)

             return new Triple{d = a, x = 1, y = 0};

         var v = ExtendedEuclidsAlgo(b, a % b);

         return v.Set(v.d, v.y, v.x - (v.y * (a / b)));

     }

​

     public static long ModEx(long a, long b, long n)

     {

         long c = 0;

         long d = 1;

         for(var i = Convert.ToString(b, 2).Length - 1; i >= 0; i--)

         {

             c *= 2;

             d = (d * d) % n;

             if((b & (0x1 << i)) == (0x1 << i))

             {

                 c++;

                 d = (d * a) % n;

             }

         }

         return d;

     }

​

     public static bool StrongPrimality(long n)

     {

         if (n <= 3)

             return n > 1;

         if(n % 2 == 0 || n % 3 == 0)

             return false;

         var i = 5;

         while(i * i <= n)

         {

             if (n % i == 0 || n % (i + 2) == 0)

                 return false;

             i += 6;

         }

         return true;

     }

​

     public static bool WeakPrimality(long n)

     {

         if (ModEx(2, n - 1, n) % n != 1)

             return false;

         return true;

     }

 }