void fastPow_2variant(int num, int MOD,int m) {//изпълнение на задача 10
	cout << "Variant 2:" << endl;
	int c = 0;//променливав която ще извършваме степенуване на всяка итерация на цикъла

	int b = num;//запазваме стойноста на въведеното число num
	int tmp = 0;//  променлива в която ще съхраним (c % MOD)
		int res = 0;
	for (int i = 2;i < m;i*= 2) {

		if (i & 1)


			b = ((long long)b * b) % MOD;
		c = pow(num, i);


		if (i == 2)
			cout << num << "^" << i << " =" << "(" << num << "^" << i / 2 << ")" "^" << 2 << "mod(" << MOD << ")" << " " << c % MOD << endl;

		else {
			if (i > 2) {
				c = pow(num, i / 2);
				tmp = abs(c % MOD);
				res = pow(tmp, 2);
				cout << num << "^" << i << " =" << "(" << num << "^" << i / 2 << ")" "^" << 2 << "mod(" << MOD << ")" << " " << tmp << "^" << 2 << "mod(" << MOD << ")" << res % MOD << endl;
			}

		}
	}

	cout << endl;

	cout << num << "^" << m << "=" << num << "^64 + 32 + 4 =" << MOD << " " << 4 << "*" << 2 << "*" << 4 << "mod(" << MOD << ")" << " " << (4*2*4) % MOD;
}
bool isPrime(int n)//фунция за проверка дали едно число е просто
{

	if (n <= 1)  return false;
	if (n <= 3)  return true;


	if (n % 2 == 0 || n % 3 == 0) return false;

	for (int i = 5; i*i <= n; i = i + 6)
		if (n%i == 0 || n % (i + 2) == 0)
			return false;

	return true;
}


int power(int x, unsigned int y, int p)
{
	int s = 1;

	x = x % p;

	while (y > 0)
	{

		if (y & 1)
			s = (s*x) % p;

		y = y >> 1;
		x = (x*x) % p;
	}
	return s;
}
void findPrimefactors(unordered_set<int> &s, int n) //намираме простите числа
{

	while (n % 2 == 0)
	{
		s.insert(2);
		n = n / 2;
	}

	for (int i = 3; i <= sqrt(n); i = i + 2)
	{

		while (n%i == 0)
		{
			s.insert(i);
			n = n / i;
		}
	}


	if (n > 2)
		s.insert(n);
}
int CheckFor_PR(int n) //изпълнение на задача 11 проверка за примитивен корен
{
	unordered_set<int> s;


	if (isPrime(n) == false)
		return false;


	int p = n - 1;


	findPrimefactors(s, p);


	for (int r = 2; r <= p; r++)
	{

		bool flag = false;
		for (auto it = s.begin(); it != s.end(); it++)
		{


			if (power(r, p / (*it), n) == 1)
			{
				flag = true;
				break;
			}
		}


		if (flag == false)
			return true;
	}


	return false;
}

void findALLprimities(int n)// изпълнение на задача 12 отпечатване на примитивните корени
{
	unordered_set<int> s;

	// Check if n is prime or not
	if (isPrime(n) == false)
		cout << "There is not a primitive root in Z(" << n << ")" << endl;


	int p = n - 1;


	findPrimefactors(s, p);


	for (int r = 2; r <= p; r++)
	{

		bool flag = false;
		for (auto it = s.begin(); it != s.end(); it++)
		{


			if (power(r, p / (*it), n) == 1)
			{
				flag = true;
			}



		}
		if (flag == false) {
			cout << r << " ";
		}
	}


}
int discreteLogarithm(int a, int modul) //изпълнение на задача 13 намиране на дискретен логаритъм
{
	int n = (int)sqrt(modul) + 1;


	int arr[200];
	for (int i = 0;i < modul;i++) {
		arr[i] = i;
	}

	for (int i = n; i >= 1; --i)
		arr[power(a, i * n, modul)] = i;

	for (int j = 0; j < n; ++j)
	{

		int cur = (power(a, j, modul) * arr[j]) % modul;


		if (arr[cur])
		{
			int discreteLOG = arr[cur] * n - j;

			if (discreteLOG < modul)
				return discreteLOG;
		}
	}
	return -1;
}
void findResidualField(int num, int modul) {
	int arr[200];
	bool flag = false;
	for (int i = 0;i < modul;i++) {
		arr[i] = i;
		if (arr[i] == num && (isPrime(num) == true)) {
			flag = true;
			break;
		}
	}
	if (flag && CheckFor_PR(modul)) {
		cout << "There are a residual field in Z(" << modul << ")" << endl;
		for (int i = 1;i < modul;i++) {
			arr[i] = i;
		}
		cout << "F(" << modul << ") = {";
		for (int i = 1; i < modul; i++)
		{
			cout << arr[i] << ((i == modul - 1) ? "" : ",");
		}
		cout << "}";
	}
	else {
		cout << "NO" << endl;
	}
}