using System;
using System.Numerics;

namespace Laba
{


	class MyRandom
	{
		static Random rand = new Random();
		public static BigInteger gen(BigInteger low, BigInteger up)    // генерация числа в диапазоне [low,up)
		{
			int sz = (int)BigInteger.Log(up, 2);
			BigInteger ans = 0, p = 1;
			do
			{
				ans = 0;
				p = 1;
				for (int i = 0; i < sz; i++)
				{
					ans += rand.Next(2) * p;
					p *= 2;
				}
			}
			while (ans < low || ans >= up);

			return ans;
		}
	}


	class PrimeTest
	{
		static int Jac(BigInteger a, BigInteger n)
		{
            int ans = 1;


			//избавление от четности
			while (a > 1)
			{
				int x = 0;
				while (a % 2 == 0)
				{
					x++;
					a /= 2;
				}
                if (x % 2 == 1 && (n % 8 == 3 || n % 8 == 5))
					ans = -ans;
				//квадратичный закон взаимности
				if (a % 4 == 3 && n % 4 == 3)
					ans = -ans;

				BigInteger temp = a;
				a = n % temp;
				n = temp;
			}
			return ans;
		}

        public static bool is_prime(BigInteger n)
		{
            if (n < 2 || n%2==0)
                return false;
			if (n == 2 || n == 3)
				return true;

            int k = (int)BigInteger.Log(n, 2);
			for (int i = 0; i < k; i++)
			{
				BigInteger a = MyRandom.gen(2, n);
				if (BigInteger.GreatestCommonDivisor(a, n) > 1)
					return false;

				BigInteger Jacoby = Jac(a, n);
				if (Jacoby == -1)
					Jacoby += n;
				if (BigInteger.ModPow(a, (n - 1) / 2, n) != Jacoby)
					return false;
			}
			return true;

		}
	}


	class Blum
	{

		public BigInteger P, Q, x0, M;

        public Blum(BigInteger p, BigInteger q, BigInteger x)
        {
            P = p;
            Q = q;
            x0 = x;
            M = p * q;
        }

        BigInteger lcm(BigInteger x, BigInteger y)
		{
            return x / BigInteger.GreatestCommonDivisor(x, y) * y;
		}
        public BigInteger[] GenerateSequence(int len)
		{
			BigInteger[] x = new BigInteger[len];
            x[0] = x0;
			for (int i = 1; i < len; i++)
				x[i] = x[i - 1] * x[i - 1] % M;
			return x;
		}
        public BigInteger GenerateIthElement(int i)
		{
            BigInteger l = lcm(P - 1, Q - 1);

			BigInteger pow = BigInteger.ModPow(2, i, l);
            BigInteger ans = BigInteger.ModPow(x0, pow, M);
            return ans;
		}
	}




	class MainClass
	{


		public static void Main(string[] args)
		{
            // это блум блум
            BigInteger p = 19;
            BigInteger q = 11;
            BigInteger x0 = 3;
            Blum bb = new Blum(p, q, x0);
			Console.WriteLine("p = {0}", bb.P);
			Console.WriteLine("q = {0}", bb.Q);
			Console.WriteLine("M = {0}", bb.M);
			Console.WriteLine("x0 = {0}", bb.x0);
            int i = 7;
			Console.WriteLine("{0} element of sequence is {1}", i, bb.GenerateIthElement(i));

			BigInteger[] x = bb.GenerateSequence(10);
			Console.WriteLine("Sequence:");
            for (int k = 0; k < 10; k++)
				Console.WriteLine(x[k]);

            // это Соловей

            Console.WriteLine();
            BigInteger n = 167; // число которое хотим проверить на простоту
            if (PrimeTest.is_prime(n))
            {
                Console.WriteLine("{0} простое", n);
            }
            else
            {
                Console.WriteLine("{0} состановное", n);
            }
			n = 147;    // число которое хотим проверить на простоту
			if (PrimeTest.is_prime(n))
			{
				Console.WriteLine("{0} простое", n);
			}
			else
			{
				Console.WriteLine("{0} состановное", n);
			}
            Console.ReadKey();
		}
	}
}