#include "test.h"
#include <string.h>
#include <fstream>
#include <iostream>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <map>
#include <random>
#include <conio.h>
#include "windows.h"
#include <string>
#include <functional>

using namespace std;
typedef long long big;


big* evklid_(big a, big b)
{
	big *U;
	U = new big[3];
	U[0] = a; U[1] = 1; U[2] = 0;
	big V[] = { b,0,1 }, T[3], q;
	while (V[0] != 0)
	{
			q = U[0]/V[0];
			for ( int i = 0; i < 3; i++)
			{
				T[i] = U[i] - q * V[i];
			}
			U[0] = V[0]; U[1] = V[1]; U[2] = V[2];
			U[0] = T[0]; V[1] = T[1]; V[2] = V[2];
	}
	return U;

}
//Функция для нахождения элементов С и D системы RSA, возвращающая динамический массив
big* gen_C_d_(big p)
{
	big *cd;
	big *res;
	big s = sqrt(p);

	cd = new big[2];

	cd[0] = rand() % (p)+2;

	while (nod_1(cd[0], p) != 1)
		cd[0] = rand() % (p)+2;

	res = evklid_(cd[0],p);
	cd[1] = res[1];
	if (cd[1] <= 0)
		cd[1] = cd[1] + p;
	delete res;
	return cd;
}

//Функция проверки на простоту
int ferm_(big n)
{
	big z, i, f;
	z = sqrt((double)n) + 1;
	for (i = 2; i <= z; i++)
	{
		if (n % i == 0)
		{
			f = 0;
			break;
		}
		else f = 1;
	}
	return f;
}


//Функция для генерации числа N системы RSA
big* gen_n()
{
	big p, q, *N;
	N = new big[2];
	while (1)
	{
		p = prov4(8);
		q = prov4(8);
		if (p != q)
			break;
	}

	N[0] = p * q;
	N[1] = (p - 1)*(q - 1);
	return N;
}



//Функция быстрого возведения в степень
big pow_mod(big a, big x, big p)
{
	big y=1, c=a;
	for(;x>0;x/=2)
	{
		if(x%2 == 1)
			y=(y*c)%p;
		c=(c*c)%p;
	}

	return y;

}


//Функция перемешивания вершин в массив vertex[]

void change_vertex_number(big *vertex, big v_count)
{
	big i, j;
	for (i = 0; i < v_count; ++i)
	{
		vertex[i] = 0;
	}

	for (i = 0; i < v_count; ++i)
	{
		j = rand() % v_count;
		while (vertex[j] != 0)
			j = rand() % v_count;
		vertex[j] = i;
	}
}


//Изменение начальной матрицы G согласно перемешанным вершинам в матрицу Н
void change_init_matrix(big **init, big **mod, big *vertex, big e_count)
{

	big i, j;
	for (i = 0; i < 2; ++i)
		for (j = 0; j < e_count; ++j)
		{
			mod[i][j] = vertex[init[i][j]];
		}
}

//Приписываем в матрицу Н элементы матрицы R так, чтобы элементы
//полученной матрицы H'ij = Rij||Hij
void change_trans_matrix(big **init, big **mod, big e_count, big **R)
{
	big i, j, k;

	for (i = 0; i < 2; ++i)
	{
		for (j = 0; j < e_count; ++j)
		{
			k = rand() % 6 + 1;
			R[i][j] = k * 10;
			mod[i][j] = init[i][j] + R[i][j];

		}

	}
}
//Шифрование мартрицы H' в F по RSA
void crypting_matrix(big **init,big **mod,big N,big C, big e_count)
{
	big i, j;

	cout << C << endl;
	cout<< N << endl;
	for (i = 0; i < 2; ++i)
		for (j = 0; j < e_count; ++j)
		{
			mod[i][j] = mod_1(init[i][j], C, N);
		}

}

//Изменение Гамильтонова цикла, согласно перестановленных вершин массивa vertex[]
void change_gam_cycle(big *vertex, big *init, big *mod, big v_count)
{
	big i;
	for (i = 0; i < v_count; ++i)
	{
		mod[i] = init[vertex[i]];
	}
}
//Вывод матрицы размера 2 на e_count
void print_matrix(big **mat, big e_count)
{
	big i, j;
	for (i = 0; i < 2; ++i)
	{
		for (j = 0; j < e_count; ++j)
			cout << mat[i][j] << " ";
		cout << endl;
	}
}
//Вывод массива размера v_count
void print_array(big *array, big v_count)
{
	big i;
	for (i = 0; i < v_count; ++i)
		cout << array[i];
	cout << endl;
	cout << endl;
}
//Считывание матрицы размером 2 на e_count из файла
void read_matrix(big e_count, big **G, ifstream& fin)
{
	big i, j;
	big buf = 0;
	for (i = 0; i < 2; ++i)
	{
		for (j = 0; j < e_count; ++j)
		{
			fin>>buf;
			G[i][j] = buf;
			buf = 0;
		}
	}
}
//Считывание массива размером v_count из файла
void read_cycle(big v_count, big *vertex, ifstream& fin)
{
	big i, buf;
	for (i = 0; i < v_count; ++i)
	{
		fin >> buf;
		vertex[i] = buf;
	}
}

//Поиск индекса элемента number
big find_number(big * vertex, big number, big v_count)
{
	big i;
	for (i = 0; i < v_count; ++i)
	{
		if (vertex[i] == number)
			return i;
	}
}

int main()
{
	setlocale(LC_ALL, "Rus");
	int i, choise, count, j;
	big v_count, *mod_gam_cycle, *vertex, e_count, **G, **H, **Ht, **F, *n, *cd, N, C, D, *gam_cycle, **R;


	//Считывание из файла n и m
	ifstream fin;
	fin.open("cycle12.txt");
	if (!fin.is_open())
	{
		cout << "Ошибка открытия файла!" << endl;
	}
	//else //cout << "Файл открыт!" << endl;
	fin >> v_count;
	fin >> e_count;

	n = gen_n();
	cout << n << endl;
	N = n[0];
	cd = gen_C_d_(n[1]);
	C = cd[1];
	D = cd[0];

	cout << "Значения ключей: " << endl;

	cout << "N = " << N << endl;
	cout << "C = " << C << endl;
	cout << "D = " << D << endl;

	delete n;
	delete cd;

	//Динамическиое объявление массивов и матриц
	mod_gam_cycle = new big[v_count];

	G = new big *[2];
	H = new big *[2];
	Ht = new big *[2];
	F = new big*[2];
	R = new big*[2];



	vertex = new big[v_count];
	gam_cycle = new big[v_count];

	for (i = 0; i < e_count; ++i)
	{
		R[i] = new big[e_count];
		G[i] = new big[e_count];
		H[i] = new big[e_count];
		Ht[i] = new big[e_count];
		F[i] = new big[e_count];
	}
	//Считывание маарицы и Гамильтонова цикла из файла


	read_matrix(e_count, G, fin);


	read_cycle(v_count, gam_cycle, fin);
	cout << "Гамельтонов цикл: ";
	print_array(gam_cycle, v_count);
	cout << "Граф:" << endl;
	print_matrix(G, e_count);
	cout << endl;

	cout << "Введите количество задаваемых вопросов:" << endl;
	cin >> count;



	while (count > 0)
	{
		system("cls");
		//Выберите вопрос
			//	printf("Please make choise\n1 - Show Gamilton's cycle\n2 - Graph H is isomorphic of G?\n");
		cout << "Выерите действие:" << endl << "1 - Показать гамельтонов цикл" << endl << "2 - Доказать изоморфность графа." << endl;
		cin >> choise;
		//Перемешивание вершин исходной матрицы
		change_vertex_number(vertex, v_count);
		//Создание изоморфной матрицы

		change_init_matrix(G, H, vertex, e_count);

		print_matrix(H, e_count);

		//Производим слияние изоморфной матрицы с матрицой R для
		//подготовки к шифрованию
		change_trans_matrix(H, Ht, e_count, R);
		//Шифрование марицы
		crypting_matrix(Ht, F, N, C, e_count);
		//Изменение Гамильтонова цикла, согласно перемешанным вершинам
		change_gam_cycle(vertex, gam_cycle, mod_gam_cycle, v_count);
		//После Боб получает шифрованную матрицу и в зависимости от
		//вопроса получает ответ
		printf("Matrix F:\n");
		print_matrix(F, e_count);

		switch (choise)
		{
			//Получение Гамильтонова цикла
		case 1:
			//Вывод модифицированного Гамильтонова цикла
			cout << "Модифицированный цикл:" << endl;
			print_array(mod_gam_cycle, v_count);
			//Вывод изоморфной матрицы для сравнения с Гамильтоновым циклом
			cout << "Изоморфный граф для проверки:" << endl;
            cout<<"4411675502"<<endl;
            cout<<"1767500233"<<endl;
			break;
			//Доказательство изоморфности графа
		case 2:
			/*	printf("Modificated transverse matrix Ht:\n");
				print_matrix(Ht, e_count);*/
			cout << "Изоморфный граф:" << endl;
			print_matrix(H, e_count);
			/*		printf("Transverse array :\n");
					print_array(vertex, v_count);*/

			cout << "Исходный граф:" << endl;
			for (i = 0; i < 2; ++i)
			{
				for (j = 0; j < e_count; ++j)
				{
					cout << find_number(vertex, H[i][j], v_count);
				}
				cout << endl;
			}
			break;
		}
		system("pause");
		count--;

	}

	for (i = 0; i < 2; ++i)
	{
		delete H[i];
		delete Ht[i];
		delete F[i];
		delete R[i];
	}
	printf("All rigth\n");
	fin.close();
	return 0;
}