using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

namespace Lab6
{
    class Program {
        static void Main(string[] args) {
            genBigPrimeNumber(20);

            Console.ReadLine();
        }

        static void genBigPrimeNumber(int k) {
            BigInteger n, r;
            BigInteger p, q;
            n = r = 0;
            p = q = 13;

            while (p.ToString().Length < k) {
                r = genNumber(q);
                n = (q * r) + 1;

                //Console.WriteLine(r + " : " + q);

                if (BigInteger.ModPow(2, n - 1, n) != 1 || (BigInteger.ModPow(2, n, n) - 1) != 1)
                    continue;
                else {
                    q = p;
                    p = n;
                    //Console.WriteLine(q + " : " + p + " ; Del: " + (p - 1) % q + "; Ran: " + r);
                }

            }

            Console.WriteLine("q|p-1 = " + q + "; p = " + p);

            Console.WriteLine((p - 1) % q);

        }

        static BigInteger genNumber(BigInteger q) {
            // выберем случайное целое число a в отрезке [2, q − 3]
            RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();

            byte[] _r = new byte[q.ToByteArray().LongLength];

            BigInteger r;

            do {
                rng.GetBytes(_r);
                r = new BigInteger(_r);
            }
            while ((r < 2 || r >= q - 3) || r % 2 != 0);

            return r;
        }
    }
}