#include "pch.h"
#include <iostream>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;

void Masiv_s_Elementite_na_Ostatucite(int modul) {
	//изпълнение на задача 1 от проекта
	int arr[200];
	for (int i = 0;i < modul;i++) {
		arr[i] = i;
	}
	for (int i = 0; i < modul; i++)
	{
		cout << arr[i] << ((i == modul - 1) ? "" : ",");
	}

}
void SumOfElementsIN_Z(int a,int b,int n) {//изпълнение на задача 2
	int sum = a + b;
	int modul = sum % n;
	cout << "The sum  of the elements" << " " <<  a << " " << "and" << " " << b << " " << "in Z(" << n << ") is:" << " " << sum << endl;
}
void SubstractionOfElementsIn_Z(int a,int b,int n) {//изпълнение на задача 3
	int sub = a - b;
	int modul;
	if (sub >= 0) {
		modul = sub % n;
	}
	else {
		//ako sub e otricatelno:
		modul = (sub % n + n) % n;
	}

	cout << "The subsraction  of the elements" << " " << a << " " << "and" << " " << b<< " " << "in Z(" << n << ") is:" << " " << sub << endl;
}
int ProdOfElementsin_Z(int a,int b,int n) {//изпълнение на задача 4
	int prod = a * b;
	int modul = prod % n;

	return modul;
	return 0;
}

int **Reciproals(int num, int *count) {//изпълнение на задача 5
	//бройм реципрочните числа
	*count = 0;
	for (int i = 0; i < num;i++) {
		//умножаваме i с всички числа докато даде 1
		for (int j = 0;j < num;j++) {
			if (ProdOfElementsin_Z(i, j, num) == 1) {
				(*count)++;

			}
		}
	}
	int **recip = new int*[2];
	recip[0] = new int[*count];
	recip[1] = new int[*count];

	int index = 0;
	for (int i = 0; i < num;i++) {

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

			//подавам му  числа с които ги умножава и търси реципрочните с който пълни масивите
			if (ProdOfElementsin_Z(i, j, num) == 1) {
				recip[0][index] = i;
				recip[1][index] = j;
				index++;

			}
		}
	}
	return recip;
}
int Find_Recip(int n, int ** recip, int cnt) {//изпълнение на задача 6
	for (int i = 0;i < cnt;i++) {
		if (recip[0][i] == n) {
			return recip[1][i];
		}
	}
	return -1;
}
int RecipBezu(int a, int mod) {//изпълнение на задача 7

	int q = mod;/* delimo*/
	int r = a;

	int tmp = q % r; // брой остатъци

	int coll = 2;
	while (tmp) { //if it is not 0 is true ; else its false

		q = r; //delimoto stawa delitel
		r = tmp; //ostatuka stawa delimo

		tmp = q % r;

		coll++;

	}
	std::cout << coll;





	return 0;
}

int divideRecip(int a, int b, int ** recip, int cnt, int modul) {//изпълнение на задача 8
	int p = Find_Recip(b, recip, cnt);
	if (p != 0) {
		//ако p не е равно на 0 сме намерили реципрочното му
		return  ProdOfElementsin_Z(a, p, modul);//функцията на 4та задача
	}
	else {
		return -1;//ако делението не е възможно
	}
}
void fastPow_1variant(int num,int MOD,int m) {//изпълнение на задача 9

	cout << "Variant 1:" << endl;
	int c = 0;//променливав която ще извършваме степенуване на всяка итерация на цикъла
	int k = 0;
	int b = num;//запазваме стойноста на въведеното число
	int tmp = 0;//тук ще пазим стойноста на m % k
	for (int i = 2;i < MOD;i++) {

		if (i & 1)


		b = ((long long)b * b) % MOD;
		c = pow(num, i);
		cout << num << "^" << i << " =" << num << "*" << num << "^" << i - 1 << "mod(" << MOD << ")" << c % MOD << endl;

		if (c % MOD == 1) {
			k = i;
			tmp = m % k;
				int result = pow(num, tmp);
			cout << "The smallest integer,which a^k mod(n) = 1 ,k = " << " " << i << endl;
			cout << num << "^" << m << " = " << MOD << " " << num << "^" << m << "mod(" << k << ") =" << MOD << " " << num << "^" << tmp << "=" << MOD << " "<< result % MOD;
			break;
		}
	}
//	cout << num << "^" << m << " = " << MOD;
}
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) {//изпълнение на задача 14
	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;
	}
}
int printingArray(int arr[], int n) {//функция за принтиране на масив която ще се използва в следаващите задачи
	for (unsigned i = 0;i < n;i++) {

			cout << arr[i] << ((i == n - 1) ? "" : ",");

	}
	cout << endl;

	return 0;
}
int main()
{

	cout << "Hello this is a Modular Arithmetic project made by Yanislav Yanev" << endl;
		cout << "You can choose exercise betweеn 1,2,3,4,5,6,7,8,9,10,11,12,13,14" << endl;
		int zadacha, modul;
		cout << "Enter number of exercise: ";

		cin >> zadacha;


		while (zadacha != 0) {
			cout << "Enter modul:";
			cin >> modul;

			if (zadacha == 1) {
				//изпълнение на задача 1
				cout << "Izpalnenie na zadacha 1:" << endl;
				cout << "Z" << "(" << modul << ") = {";
				Masiv_s_Elementite_na_Ostatucite(modul);
				cout << "}";
				cout << endl;
			}

			if (zadacha != 1 && zadacha <= 4) {
				int a, b;


				cout << "Enter first number:";
				cin >> a;

				cout << "Enter second number:";
				cin >> b;




				if (zadacha == 2) {
					cout << "Izpalnenie na zadacha 2:" << endl;
					//изпълнение на задача 2
					SumOfElementsIN_Z(a, b, modul);
					cout << endl;
				}
				if (zadacha == 3) {
					// изпълнение на задача 3

					cout << "Izpalnenie na zadacha 3:" << endl;
					SubstractionOfElementsIn_Z(a, b, modul);
					cout << endl;
				}
				if (zadacha == 4) {
					//изпълнение на задача 4
					cout << "Izpalnenie na zadacha 4:" << endl;
					cout << "The prod  of the elements" << " " << a << " " << "and" << " " << b << " " << "in Z(" << modul << ") is:" << " " << ProdOfElementsin_Z(a, b, modul) << endl;

					cout << endl;
				}
			}
			else {
				int counter = 0, n;
				int **reciprochno = Reciproals(7, &counter);
				cout << " Enter number:";
				cin >> n;
				if (zadacha == 5) {
					//изпълнение на задача 5
					cout << "Izpalnenie na zadacha 5:";
					cout << endl;


					printingArray(reciprochno[0], counter);

					printingArray(reciprochno[1], counter);
					cout << endl;
				}
				if (zadacha == 6) {
					//изпълнение на задача 6
					cout << "Izpalnenie na zadacha 6:" << endl;
					cout << Find_Recip(n, reciprochno, counter) << endl;
				}
				if (zadacha == 7) {
					cout << "Izpalnenie na zadacha 7:" << endl;
					cout << RecipBezu(n, modul) << endl;
				}
				if (zadacha == 8) {
					int c;
					cout << "Enter another number:";
					cin >> c;
					cout << "Izpalnenie na zadacha 8:" << endl;
					cout << divideRecip(n, c, reciprochno, counter, modul) << endl;
				}
				if (zadacha == 9) {
					//изпълнение на задача 9
					cout << "Izpalnenie na zadacha 9:" << endl;
					fastPow_1variant(n, modul, 100);
					cout << endl;
				}
				if (zadacha == 10) {
					//изпълнение на задача 10
					cout << "Izpalnenie na zadacha 10:" << endl;
					fastPow_2variant(n, modul, 100);
					cout << endl;
				}
				if (zadacha == 11) {
					// изпълнение на задача 11
					cout << "Izpalnenie na zadacha 11:" << endl;
					if (CheckFor_PR(modul)) {
						cout << "In Z(" << modul << ") have primitive roots" << endl;
					}
					else {
						cout << "In Z(" << modul << ")  do not have any primitive roots" << endl;
					}
				}
				if (zadacha == 12) {
					//изпълнение на задача 12
					cout << "Izpalnenie na zadacha 12:" << endl;
					cout << "All primitive roots in Z(" << modul << ") are:" << " ";
					findALLprimities(modul);
					cout << endl;
				}
				if (zadacha == 13) {
					//изпълнение на задача 13
					cout << "Izpalnenie na zadacha 13:" << endl;
					cout << "The discrete logaritum of number" << " " << n << " " << "in Z(" << modul << ") is:" << " " << discreteLogarithm(n, modul);
					cout << endl;
				}
				if (zadacha == 14) {
					//изпълнение на задача 14
					cout << "Izpalnenie na zadacha 14:" << endl;
					findResidualField(n, modul);
				}




				//освобождаване на паметта заета за 5та задача
				if (reciprochno != nullptr) {
					delete[]reciprochno[1];
					delete[]reciprochno[0];
					delete[]reciprochno;
					reciprochno = NULL;
				}
			}

			cout << "(if you want to stop the program enter 0)" << endl;
			cout << "Enter number of exercise:";
			cin >> zadacha;



		}

	return 0;

}