using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Security.Cryptography;

namespace EC2
{
    class Program
    {
        public static BigInteger NR;
        public static BigInteger B;
        public static BigInteger p;
        public static int cnt = 0;
        public static List<BigInteger> PNR;
        public static Random rand = new Random();
        public static List<BigInteger> Q = new List<BigInteger>();
        public static BigInteger r;
        public static BigInteger l;
        public static string m;
        public static List<BigInteger> P;
        static void Main(string[] args)
        {
            while (true)
            {
                Info();
                int idx;

                try
                {
                    idx = int.Parse(Console.ReadLine());
                }
                catch (FormatException)
                {
                    continue;
                }
                Console.Clear();
                try
                {



                    switch (idx)
                    {
                        case 1:
                            {
                                GenerateEC();
                                Console.ReadLine();
                                Console.Clear();
                                break;
                            }

                        case 2:
                            {
                                ElGamal();
                                Console.ReadLine();
                                Console.Clear();
                                break;
                            }
                        case 0:
                            {
                                return;
                            }
                        default:
                            break;
                    }
                }
                catch (FileNotFoundException)
                {
                    Console.WriteLine("Не заданы параметры Эллиптической кривой");
                    Console.ReadLine();
                    return;
                }
            }
        }

        public static void ElGamal()
        {
            try
            {
                ReadParam();
                int counter = 0,
                    lastStep = 0;
                Console.Write("Введите l: ");
                l = BigInteger.Parse(Console.ReadLine());
                WriteNumber("l.txt", l);
                P = QuickSumPoint(Q, l, p);
                WritePoint(P, "P.txt");

                while (true)
                {
                    Console.WriteLine("Введите номер шага, который хотите исполнить: ");
                    Console.WriteLine("\t1 - Если хотите сгенерировать случайный показатель k'");
                    Console.WriteLine("\t2 - Если хотите убадиться что R принадлежит E(K)");
                    Console.WriteLine("\t3 - Если хотите вычислить подпись");
                    Console.WriteLine("\t4 - Если хотите проверить подпись");
                    Console.WriteLine("\t5 - Если хотите погасить монету");
                    Console.WriteLine("\t0 - Если хотите выйти");
                    int idx;
                    try
                    {
                        idx = int.Parse(Console.ReadLine());

                        m = File.ReadAllText("m.txt");
                    }
                    catch (FormatException)
                    {
                        continue;
                    }
                    catch (FileNotFoundException)
                    {
                        Console.WriteLine("Создайте файл m.txt");
                        Console.ReadLine();
                        Console.Clear();
                        return;
                    }
                    Console.Clear();

                    try
                    {
                        switch (idx)
                        {
                            case 1:
                                {
                                    EStep1();
                                    lastStep = 1;
                                    break;
                                }
                            case 2:
                                {
                                    if (lastStep != 1 || !EStep2())
                                    {
                                        DeleteFiles();
                                        return;
                                    }

                                    lastStep = 2;
                                    break;
                                }
                            case 3:
                                {
                                    if (lastStep != 2 || !EStep3())
                                    {
                                        DeleteFiles();
                                        return;
                                    }
                                    lastStep = 3;
                                    break;
                                }
                            case 4:
                                {
                                    if (lastStep != 3)
                                    {
                                        DeleteFiles();
                                        return;
                                    }
                                    counter++;
                                    if (EStep4())
                                    {
                                        Console.WriteLine("Подпись принята");
                                    }
                                    else
                                    {
                                        Console.WriteLine("Подпись не принята");
                                    }
                                    lastStep = 0;
                                    break;
                                }
                            case 5:
                                {
                                    if (EStep5())
                                        Console.WriteLine("Подпись действительна");
                                    else
                                        Console.WriteLine("Подпись не действительна");
                                    DeleteFiles(true);
                                    return;
                                }
                            case 0:
                                {
                                    DeleteFiles();
                                    return;
                                }
                            default:
                                break;
                        }
                        Console.WriteLine("Шаг {0} выполнен", idx);
                        Console.ReadLine();
                        Console.Clear();
                    }
                    catch (FileNotFoundException er)
                    {
                        Console.WriteLine(er.Message);
                        DeleteFiles();
                        return;
                    }
                }
            }
            catch (FormatException)
            {
                Console.Clear();
                throw;
            }
            catch (FileNotFoundException)
            {

                throw;
            }
            catch (Exception)
            {

                throw;
            }
        }
        public static void EStep1()
        {
            List<BigInteger> _R;
            while (true)
            {
                BigInteger _k;
                do
                {
                    _k = BigInteger.ModPow(new Random().Next(99, 9999), new Random().Next(99, 9999), r);
                } while (_k == 0 || _k == r);

                _R = QuickSumPoint(Q, _k, p);
                if (_R[0] != 0)
                {
                    WriteNumber("_k.txt", _k);
                    break;
                }
            }
            WritePoint(_R, "_R.txt");
        }
        public static bool EStep2()
        {
            List<BigInteger> _R = readPoint("_R.txt");
            if ((_R[1] * _R[1]) % p != (_R[0] * _R[0] * _R[0] + B) % p) return false;

            BigInteger alpha;
            List<BigInteger> R;
            while (true)
            {
                do
                {
                    alpha = BigInteger.ModPow(new Random().Next(99, 9999), new Random().Next(99, 9999), r);
                } while (alpha == 0 || alpha == r);

                R = QuickSumPoint(_R, alpha, p);

                if (R[0] != 0)
                    break;
            }
            WritePoint(R, "R.txt");

            var Bb = R[0] * Reverse(_R[0], r) % r;
            WriteNumber("B.txt", Bb);

            var _m = alpha * Reverse(Bb, r) * NumMessage(m) % r;

            WriteNumber("_m.txt", _m);

            return true;
        }
        public static bool EStep3()
        {
            var l = BigInteger.Parse(File.ReadAllText("l.txt"));
            var _m = BigInteger.Parse(File.ReadAllText("_m.txt"));
            var _k = BigInteger.Parse(File.ReadAllText("_k.txt"));
            var _R = readPoint("_R.txt");
            if (_m == 0) return false;

            var _s = l * _R[0] + _k * _m % r;

            WriteNumber("_s.txt", _s);

            return true;
        }
        public static bool EStep4()
        {
            var P = readPoint("P.txt");
            var _R = readPoint("_R.txt");
            var _m = BigInteger.Parse(File.ReadAllText("_m.txt"));
            var _s = BigInteger.Parse(File.ReadAllText("_s.txt"));
            var Bb = BigInteger.Parse(File.ReadAllText("B.txt"));

            var mult1 = QuickSumPoint(Q, _s, p);
            var mult2 = QuickSumPoint(P, _R[0], p);
            var mult3 = QuickSumPoint(_R, _m,  p);
            var sum1 = SummaTochek(mult2, mult3, p);
            if (mult1[0] == sum1[0] && mult1[1] == sum1[1])
            {
                var s = _s * Bb % r;
                WriteNumber("s.txt", s);
                foreach (var item in Directory.GetFiles(Environment.CurrentDirectory))
                {
                    if (Path.GetFileNameWithoutExtension(item) == "m" || Path.GetFileNameWithoutExtension(item) == "R" || Path.GetFileNameWithoutExtension(item) == "s")
                        continue;
                    if (Path.GetExtension(item) == ".txt")
                        File.Delete(item);
                }
                return true;
            }
            else
                return false;
        }
        public static bool EStep5()
        {
            var R = readPoint("R.txt");
            var s = BigInteger.Parse(File.ReadAllText("s.txt"));
            var M = NumMessage(m);
            if (M == 0 || R[0] == 0) return false;

            var mult1 = QuickSumPoint(Q, s, p);
            var mult2 = QuickSumPoint(P, R[0], p);
            var mult3 = QuickSumPoint(R, M, p);
            var sum1 = SummaTochek(mult2, mult3,  p);
            return (mult1[0] == sum1[0] && mult1[1] == sum1[1]);
        }



        private static void WritePoint(List<BigInteger> _R, string path)
        {
            using (var write = new StreamWriter(File.Open(path, FileMode.Create)))
            {
                write.WriteLine(_R[0]);
                write.WriteLine(_R[1]);
            }
        }
        private static List<BigInteger> readPoint(string path)
        {
            var _R = new List<BigInteger>();
            using (var sr = new StreamReader(File.Open(path, FileMode.Open), Encoding.Default))
            {
                _R.Add(BigInteger.Parse(sr.ReadLine()));
                _R.Add(BigInteger.Parse(sr.ReadLine()));
            }

            return _R;
        }
        private static void WriteNumber(string path, BigInteger num)
        {
            using (StreamWriter wr = new StreamWriter(File.Create(path), Encoding.Default))
            {
                wr.Write(num);
            }
        }
        private static BigInteger NumMessage(string m)
        {
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < m.Length; i++)
            {
                str.Append((int)m[i]);
            }
            return BigInteger.Parse(str.ToString());
        }
        public static void DeleteFiles(bool flag = false)
        {
            foreach (var item in Directory.GetFiles(Environment.CurrentDirectory))
            {
                if (flag == false && Path.GetFileName(item) == "m.txt") continue;
                if (Path.GetExtension(item) == ".txt")
                    File.Delete(item);
            }
        }

        public static void ReadParam()
        {
            using (var sr = new StreamReader(File.Open("GeneralSettings.txt", FileMode.Open), Encoding.Default))
            {
                p = BigInteger.Parse(sr.ReadLine());
                B = BigInteger.Parse(sr.ReadLine());
                r = BigInteger.Parse(sr.ReadLine());
                Q.Add(BigInteger.Parse(sr.ReadLine()));
                Q.Add(BigInteger.Parse(sr.ReadLine()));
            }
        }
        private static void Info()
        {
            Console.WriteLine("Введите");
            Console.WriteLine("\t1 - Если хотите сгенерировать ЭК ");
            Console.WriteLine("\t2 - Если хотите создать электронную монету");
            Console.WriteLine("\t0 - Для выхода");
        }
        public static void GenerateEC()
        {
            int m = 5;
            BigInteger D = 3;
            bool flag = true;
            Console.Write("l ");
            int l = int.Parse(Console.ReadLine());
            if (l <= 4)
            {
                Console.WriteLine("Нет простых чисел, удовлетворяющих условию алгоритма");
                return;
            }

            Console.Write("m = ");
            cnt = int.Parse(Console.ReadLine());

            while (true)
            {
                step1:
                while (true)
                {
                    flag = true;
                    List<BigInteger> razl;
                    FindPrime(l);
                    razl = razlP(D, p);

                  // if (razl.Count() == 0)
                   //     goto step1;

                    PNR = pnr(razl[0], razl[1], p);
                    if (PNR.Count() == 0) goto step1;

                    if (p != PNR[1])
                    {
                        for (int i = 1; i <= m; i++)
                        {
                            if (BigInteger.ModPow(p, i, PNR[1]) == 0)
                            {
                                cnt += 1;
                                if (cnt > 20)
                                {
                                    Console.WriteLine("Такого p не существует");
                                    Console.ReadKey();
                                    return;
                                }
                                goto step1;
                            }
                        }
                        break;
                    }
                    goto step1;
                }

                BigInteger conut = 2, j = 1;
                List<BigInteger> tochka = new List<BigInteger>();
                int counter = 0;

                step5:
                while (true)
                {
                    if (PNR[0] == PNR[1] * 2)
                        Proverka(ref flag, ref conut, 2);

                    if (PNR[0] == PNR[1] * 3)
                        Proverka(ref flag, ref conut, 3);

                    if (PNR[0] == PNR[1] * 1)
                        Proverka(ref flag, ref conut, 1);

                    if (PNR[0] == PNR[1] * 6)
                        Proverka(ref flag, ref conut, 6);

                    if (!flag) goto step6;
                    tochka = new List<BigInteger>();
                    for (BigInteger i = j; ; i++, j++)
                    {
                        BigInteger z = (B + i * i * i) % p;
                        if (Legandr(z, p) == 1)
                        {
                            if (ModSqrt(z, p) == 0) continue;
                            else
                            {
                                tochka.Add(i);
                                tochka.Add(ModSqrt(z, p));
                            }
                            i++; j++;
                            break;
                        }
                    }

                    BigInteger cnt = PNR[0];

                    List<BigInteger> mulp1p2 = QuickSumPoint(tochka, cnt, p);

                    if (mulp1p2.Any())
                    {
                        if (counter++ < 100)
                            goto step5;
                        else
                        {
                            goto step1;
                        }
                    }
                    break;
                }

                step6:
                if (!flag)
                    continue;
                NR = PNR[0] / PNR[1];

                List<BigInteger> Q = QuickSumPoint(tochka, NR, p);

                if (!Q.Any() || Q[1] == 0)
                    continue;

                Console.WriteLine("p = " + p);
                Console.WriteLine("r = " + PNR[1]);
                Console.WriteLine("B = " + B);
                Console.WriteLine("Q = (" + Q[0] + ", " + Q[1] + ")");
                WriteToFiles(Q);
                break;
            }
        }
        public static string c10to2(BigInteger i)
        {
            string s = "";
            while (i > 0) { s = (i % 2).ToString() + s; i /= 2; }
            return s == "" ? "0" : s;
        }
        private static List<BigInteger> QuickSumPoint(List<BigInteger> P, BigInteger cnt, BigInteger p)
        {
            BigInteger lengthBase = CountBit(cnt);
            string c = c10to2(cnt);
            char[] b = c.ToCharArray();
            Array.Reverse(b);
            c = new string(b);
            List<List<BigInteger>> basePoints = new List<List<BigInteger>>();
            List<List<BigInteger>> result = new List<List<BigInteger>>();
            basePoints.Add(P);
            int k = 0;
            for (BigInteger i = 1; i <= cnt; i *= 2)
            {
                if (!basePoints[k].Any())
                {
                    break;
                }
                else
                {
                    basePoints.Add(SummaTochek(basePoints[k], basePoints[k], p));
                }

                if (c[k] == '1')
                {
                    result.Add(basePoints[k]);
                }
                k++;
            }

            if (!result.Any())
                return new List<BigInteger>();
            List<BigInteger> resultPoint = result[0];

            for (int i = 1; i < result.Count; i++)
            {
                if (!resultPoint.Any())
                    resultPoint = result[i];
                else
                    resultPoint = SummaTochek(resultPoint, result[i], p);
            }

            return resultPoint;
        }
        private static int CountBit(BigInteger P)
        {
            int count = 0;
            while (P > 0)
            {
                P >>= 1;
                count++;
            }
            return count;
        }
        private static void WriteToFiles(List<BigInteger> Q)
        {
            using (StreamWriter wr = new StreamWriter(File.Open("GeneralSettings.txt", FileMode.Create), Encoding.Default))
            {
                wr.WriteLine(p);
                wr.WriteLine(B);
                wr.WriteLine(PNR[1]);
                wr.WriteLine(Q[0]);
                wr.WriteLine(Q[1]);
            }
            return;
            List<BigInteger> mulp1p2_new;
            StreamWriter Cout = null, Cout1 = null, Cout2 = null;
            try
            {
                Cout = new StreamWriter(File.Open("x.txt", FileMode.Create));
                Cout1 = new StreamWriter(File.Open("y.txt", FileMode.Create));
                Cout2 = new StreamWriter(File.Open("ec.txt", FileMode.Create));
            }
            catch (IOException e)
            {
                Console.WriteLine(e.Message);
            }
            BigInteger por = PNR[1];
            try
            {
                Cout.WriteLine(Q[0]);
                Cout1.WriteLine(Q[1]);
                Cout2.WriteLine(Q[0] + " " + Q[1]);
            }
            catch (IOException e)
            {
                Console.WriteLine(e.Message);
            }
            mulp1p2_new = SummaTochek(Q, Q, p);
            try
            {
                Cout.WriteLine(mulp1p2_new[0]);
                Cout1.WriteLine(mulp1p2_new[1]);

                Cout2.WriteLine(mulp1p2_new[0] + " " + mulp1p2_new[1]);
            }
            catch (IOException e)
            {
                Console.WriteLine(e.Message);
            }
            while (por != 3)
            {
                if (!mulp1p2_new.Any())
                {
                    mulp1p2_new = Q;
                    try
                    {
                        Cout.WriteLine(mulp1p2_new[0]);
                        Cout1.WriteLine(mulp1p2_new[1]);

                        Cout2.WriteLine(mulp1p2_new[0] + " " + mulp1p2_new[1]);
                    }
                    catch (IOException e)
                    {
                        Console.WriteLine(e.Message);
                    }
                }
                else
                {
                    mulp1p2_new = SummaTochek(mulp1p2_new, Q, p);
                    try
                    {
                        Cout.WriteLine(mulp1p2_new[0]);
                        Cout1.WriteLine(mulp1p2_new[1]);
                        Cout2.WriteLine(mulp1p2_new[0] + " " + mulp1p2_new[1]);
                    }
                    catch (IOException e)
                    {
                        Console.WriteLine(e.Message);
                    }
                }
                por--;
            }
            Cout.Close();
            Cout1.Close();
            Cout2.Close();
        }

        public static BigInteger powmod(BigInteger x, BigInteger a, BigInteger m)
        {
            BigInteger r = 1;
            while (a > 0)
            {
                if (a % 2 != 0)
                    r = mulmod(r, x, m);
                a = a >> 1;
                x = mulmod(x, x, m);
            }
            return r;
        }

        static BigInteger randomBinBigInteger(int l)
        {
            RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
            byte[] Nresult = new byte[BigInteger.Pow(2, l).ToByteArray().LongLength];
            BigInteger result;
            do
            {
                rng.GetBytes(Nresult);
                result = new BigInteger(Nresult);
            } while (result <= BigInteger.Pow(2, (l - 1)) || result >= BigInteger.Pow(2, l));

            return result;
        }

        static BigInteger GenSimple(int l)
        {
            BigInteger result;
            result = randomBinBigInteger(l);
            while (!Isprime(result))
                result = randomBinBigInteger(l);
            return result;
        }

        static bool Isprime(BigInteger p)
        {
            if (p == 2 || p == 3)
                return true;
            if (p < 2 || p % 2 == 0)
                return false;
            BigInteger t = p - 1;
            int s = 0;
            while (t % 2 == 0)
            {
                t /= 2;
                s += 1;
            }

            for (int i = 0; i < 20; i++)
            {
                RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
                byte[] tmpa = new byte[p.ToByteArray().LongLength];
                rng.GetBytes(tmpa);
                BigInteger a;
                a = new BigInteger(tmpa);
                while (a < 2 || a >= p - 2)
                {
                    rng.GetBytes(tmpa);
                    a = new BigInteger(tmpa);
                }
                BigInteger x = BigInteger.ModPow(a, t, p);
                if (x == 1 || x == p - 1)
                    continue;

                for (int r = 1; r < s; r++)
                {
                    x = BigInteger.ModPow(x, 2, p);
                    if (x == 1) return false;
                    if (x == p - 1)
                        break;
                }
                if (x != p - 1)
                    return false;
            }
            return true;
        }

        private static Boolean isSqrt(BigInteger n, BigInteger sqr)
        {
            BigInteger lowerBound = sqr * sqr, upperBound = (sqr + 1) * (sqr + 1);
            return (n >= lowerBound && n < upperBound);
        }

        public static BigInteger SqrtN(BigInteger N)
        {
            if (N == 0) return 0;
            if (N > 0)
            {
                int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(N, 2)));
                BigInteger sqr = BigInteger.One << (bitLength / 2);

                while (!isSqrt(N, sqr))
                {
                    sqr += N / sqr;
                    sqr /= 2;
                }
                return sqr;
            }
            throw new ArithmeticException("NaN");
        }

        public static BigInteger gcd(BigInteger a, BigInteger b)
        {
            if (b == 0)
                return a;
            return gcd(b, a % b);
        }

        static Tuple<BigInteger, BigInteger> RashEvkl(BigInteger a, BigInteger b)
        {
            BigInteger r0 = a, r1 = b, x0 = 1, x1 = 0, y0 = 0, y1 = 1;
            BigInteger x, y, d;
            while (true)
            {
                BigInteger q = r0 / r1, r = r0 % r1;
                if (r == 0) break;
                else
                {
                    r0 = r1; r1 = r;
                    x = x0 - q * x1;
                    x0 = x1; x1 = x;
                    y = y0 - q * y1;
                    y0 = y1; y1 = y;
                }
            }
            d = r1;
            x = x1;
            y = y1;
            return new Tuple<BigInteger, BigInteger>(x, y);
        }

        static BigInteger Pow(BigInteger a, BigInteger b)
        {
            BigInteger result = 1;
            for (BigInteger i = 0; i < b; i++)
                result *= a;
            return result;
        }

        static BigInteger Jacobi(BigInteger a, BigInteger n)
        {
            if (gcd(a, n) != 1)
                return 0;
            BigInteger r = 1;
            if (a < 0)
            {
                a = -a;
                if (n % 4 == 3)
                    r = -r;
            }
            while (a != 0)
            {
                BigInteger k = 0;
                while (a % 2 == 0)
                {
                    k++;
                    a = a / 2;
                }
                if (k % 2 != 0)
                {
                    if (n % 8 == 3 || n % 8 == 5)
                        r = -r;
                }
                if (n % 4 == 3 && a % 4 == 3)
                    r = -r;
                BigInteger temp = a;
                a = n % a;
                n = temp;
            }
            return r;
        }

        static BigInteger Reverse(BigInteger a, BigInteger m)
        {
            BigInteger d = gcd(a, m);
            if (d != 1)
                return -1;
            else
            {
                Tuple<BigInteger, BigInteger> pair = RashEvkl(a, m);
                BigInteger x0 = pair.Item1 % m;
                while (x0 < 0) x0 += m;
                BigInteger inv = x0 % m;
                return inv;
            }
        }

        static BigInteger ModSqrt(BigInteger a, BigInteger p)
        {
            a += p;
            BigInteger jacobi = Jacobi(a, p);
            if (jacobi == -1)
                return 0;

            int N = 0;
            if (jacobi == 1)
            {
                for (int i = 2; i < p; i++)
                {
                    if (Jacobi(i, p) == -1)
                    {
                        N = i;
                        break;
                    }
                }
            }
            BigInteger h = p - 1;
            int k = 0;
            while (h % 2 == 0)
            {
                k++;
                h = h / 2;
            }
            BigInteger a1 = BigInteger.ModPow(a, (h + 1) / 2, p);
            BigInteger a2 = Reverse(a, p);
            BigInteger N1 = BigInteger.ModPow(N, h, p);
            BigInteger N2 = 1;
            BigInteger[] j = new BigInteger[k - 1];
            for (int i = 0; i <= k - 2; i++)
            {
                BigInteger b = (a1 * N2) % p;
                BigInteger c = (a2 * b * b) % p;
                BigInteger pow = Pow(2, k - 2 - i);
                BigInteger d = BigInteger.ModPow(c, pow, p);
                if (d == 1)
                    j[i] = 0;

                if (d == p - 1 || d - p == -1)
                    j[i] = 1;
                N2 = (N2 * (BigInteger.ModPow(N1, BigInteger.Pow(2, i) * j[i], p))) % p;
            }
            BigInteger answer = (a1 * N2) % p;
            BigInteger answer1 = (-answer + p) % p;
            return answer;
        }

        public static List<BigInteger> SummaTochek(List<BigInteger> P1, List<BigInteger> P2, BigInteger p)
        {
            List<BigInteger> res = new List<BigInteger>();
            BigInteger lambda, x1 = P1[0], y1 = P1[1], x2 = P2[0], y2 = P2[1];
            if (x1 == x2 && y1 == y2)
            {
                BigInteger chis = (3 * x1 * x1) % p, znam = (2 * y1) % p;
                if (znam == 0)
                    return res;
                lambda = chis * Reverse(znam, p) % p;
            }
            else
            {
                BigInteger chis = (y2 - y1) % p, znam = (x2 - x1) % p;
                if (!(znam >= 0))
                    znam += p;
                if (znam == 0)
                    return res;

                lambda = chis * Reverse(znam, p) % p;
            }
            BigInteger xr = (lambda * lambda - x1 - x2) % p, yr = (-y1 + lambda * (x1 - xr)) % p;
            if (!(xr >= 0))
                xr += p;
            if (!(yr >= 0))
                yr += p;
            res.Add(xr);
            res.Add(yr);
            return res;
        }

        public static bool isKvadrVich(BigInteger B, BigInteger p)
        {
            if (Legandr(B, p) == 1)
                return true;
            else return false;
        }
        public static bool isKubVich(BigInteger B, BigInteger p)
        {
            if (BigInteger.ModPow(B, (p - 1) / gcd(p - 1, 3), p) == 1)
                return true;
            else return false;
        }

        private static List<BigInteger> pnr(BigInteger c, BigInteger d, BigInteger p)
        {
            List<BigInteger> T = new List<BigInteger>();
            T.Add(c + 3 * d);
            T.Add(c - 3 * d);
            T.Add(2 * c);
            T.Add(c * (-2));
            T.Add(3 * d - c);
            T.Add(-c - 3 * d);
            for (int i = 0; i < T.Count; i++)
            {
                T[i] += (1 + p);
                if ((T[i] % 2).Equals(0) && Isprime((T[i] / 2)))
                    return new List<BigInteger>() { T[i], T[i] / 2 };
                else if ((T[i] % 3).Equals(0) && Isprime((T[i] / 3)))
                    return new List<BigInteger>() { T[i], T[i] / 3 };
                else if ((T[i] % 6).Equals(0) && Isprime((T[i] / 6)))
                    return new List<BigInteger>() { T[i], T[i] / 6 };
                else if ((T[i] % 1).Equals(0) && Isprime((T[i] / 1)))
                    return new List<BigInteger>() { T[i], T[i] / 1 };
            }
            return new List<BigInteger>();
        }

        private static void FindPrime(int l)
        {
            p = GenSimple(l);
            while ((p % 6) != 1)
                p = GenSimple(l);
        }

        public static int Legandr(BigInteger a, BigInteger p)
        {
            if (a == 0) return 0;
            if (a == 1) return 1;
            int result;
            if (a < 0)
            {
                result = Legandr(-a, p);
                if ((((p - 1) / 2) % 2) != 0)
                    result = -result;
            }
            if (a % 2 == 0)
            {
                result = Legandr(a / 2, p);
                if (((p * p - 1) & 8) != 0)
                    result = -result;
            }
            else
            {
                result = Legandr(p % a, a);
                if (((a - 1) * (p - 1) & 4) != 0)
                    result = -result;
            }
            return result;
        }

        private static void Proverka(ref bool t, ref BigInteger conut, int num)
        {
            if (PNR[0] == PNR[1] * num)
            {
                for (BigInteger i = conut; ; i++)
                {
                    if (i > 1000000)
                    {
                        t = false;
                        break;
                    }
                    bool f = isKvadrVich((i + 1) % p, PNR[0]), h = isKubVich((i + 1) % p, PNR[0]);
                    if (num == 6 && f && h || num == 1 && !f && !h || num == 2 && !f && h || num == 3 && f && !h)
                    {
                        B = i;
                        conut = B + 1;
                        break;
                    }
                }
            }
        }

        public static List<BigInteger> razlP(BigInteger D, BigInteger p)
        {
            if (Legandr(-D, p) == -1) return new List<BigInteger>();
            BigInteger R = ModSqrt(-D, p);
            int i = 0;
            List<BigInteger> U = new List<BigInteger>(), M = new List<BigInteger>();
            U.Add(R);
            M.Add(p);
            do
            {
                M.Add((U[i] * U[i] + D) / M[i]);
                U.Add(BigInteger.Min(U[i] % M[i + 1], M[i + 1] - U[i] % M[i + 1]));
                i++;
            } while (M[i] != 1);
            i--;
            List<BigInteger> a = new List<BigInteger>(), b = new List<BigInteger>();
            for (int j = 0; j <= i; j++)
            {
                a.Add(0);
                b.Add(0);
            }
            a[i] = U[i];
            b[i] = 1;
            while (i != 0)
            {
                BigInteger znam = a[i] * a[i] + D * b[i] * b[i];
                if ((U[i - 1] * a[i] + D * b[i]) % znam == 0)
                    a[i - 1] = (U[i - 1] * a[i] + D * b[i]) / znam;
                else
                    a[i - 1] = (-U[i - 1] * a[i] + D * b[i]) / znam;

                if ((-a[i] + U[i - 1] * b[i]) % znam == 0)
                    b[i - 1] = (-a[i] + U[i - 1] * b[i]) / znam;
                else
                    b[i - 1] = (-a[i] - U[i - 1] * b[i]) / znam;
                i--;
            }
            List<BigInteger> res = new List<BigInteger>();
            res.Add(a[0]);
            res.Add(b[0]);
            return res;
        }
        public static BigInteger mulmod(BigInteger x, BigInteger y, BigInteger m)
        { return (x * y) % m; }
     }
}