RSA

using System;
using System.Threading.Tasks;
using System.Numerics;

namespace RC4
{
    public class RCAClass
    {

        private int p;
        private int q;
        private int d = 0;
        public long e = 23;

        //N больше любог M
        //Сделать все Без Бигинта
        public byte[] Encrypt(byte[] message)
        {
            var pq = Generate();

            p = pq.Item1;
            q = pq.Item2;

            Console.WriteLine($"p={p}");
            Console.WriteLine($"q={q}");

            long eiler = (p - 1) * (q - 1);
            long N = p * q;
            int tmp = 0;
            int t = 0;
            gcdext((int)e, (int)eiler, ref tmp, ref d, ref t);

            Console.WriteLine((d * e) % eiler);
            //шифр

            var shifr = new long[message.Length];

            for (int i = 0; i < message.Length; i++)
                shifr[i] = ModPow(message[i], e, N);

            for (int i = 0; i < shifr.Length; i++)
                message[i] = (byte)ModPow(shifr[i], d, N);

            return message;
        }



        static public Tuple<int, int> Generate()
        {
            var rand = new Random();

            int p = rand.Next(0,100);
            int q = rand.Next(0,100);

            bool isPSimpl = Test(p);
            bool isQSimpl = Test(q);

            do
            {
                p = rand.Next(0,100);
                isPSimpl = Test(p);
            }
            while (!isPSimpl);

            do
            {
                q = rand.Next(0, 100);
                isQSimpl = Test(q);
            }
            while (!isQSimpl);

            return new Tuple<int, int>(p, q);
        }

        public static bool Test(int num)
        {
            int k = 5;

            long b;

            var rand = new Random();

            for (int i = 0; i < k; i++)
            {
                b = ModPow(rand.Next(2,num-1),num-1,num);
                if (b != 1) return false;
            }

            return true;
        }

        static public long ModPow(long value, long exponent, long modulus)
        {
            if (exponent == 0) return 1;
            long z = ModPow(value, exponent / 2, modulus);
            if (exponent % 2 == 0)
                return (z * z) % modulus;
            else
                return (value * z * z) % modulus;
        }


        static public void gcdext(int a, int b, ref int d,ref int x,ref int y)

        {

            int s;

            if (b == 0)

            {

                d = a; x = 1; y = 0;
                if (d > 1) x = 0;
                return;

            }

            gcdext(b, a % b,ref d,ref x,ref y);

            s = y;

            y = x - (a / b) * (y);

            if (d > 1) x = 0;
            else x = s;

        }

        static public bool[] ReshtoEratosfena(int size)
        {
            var res = new bool[size];

            Parallel.For(0, size, (x) => res[x] = true);
            for (int p=2;p*p<size;)
            {
                for (int i = 2; i * p < size; i++)
                {
                    res[i * p] = false;
                }

                for (int i = p+1; i < size; i++)
                {
                    if (res[i])
                    {
                        p = i;
                        break;
                    }

                }
            }


            return res;
        }
    }
}