#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define SIZE 120

class bigInt {
public:
	bigInt(char aBigInt[], bool negativeFlag = false, bool zeroFlag = false) { strcpy(a, aBigInt); setNegative(negativeFlag); setZero(zeroFlag); }
	bigInt() { clear(a); setNegative(false); setZero(true); }
	~bigInt() {};
	
	bool getNegative(void) { return negative; }
	bool getZero(void) { return zero; }
	void setNegative(bool negativeFlag) { negative = negativeFlag; }
	void setZero(bool zeroFlag) { zero = zeroFlag; }
	
	const bigInt& operator=(const bigInt& rhs);

	const bigInt& operator+(bigInt& b);
	const bigInt& operator*(bigInt& b);
	const bigInt& operator-(bigInt& b);
	const bigInt& operator/(bigInt& b);
	const bigInt& operator%(bigInt& b);
	const void operator+=(bigInt& b);
	const void operator*=(bigInt& b);
	const void operator-=(bigInt& b);
	const void operator/=(bigInt& b);
	const void operator%=(bigInt& b);
	const bool operator>(bigInt& b);
	const bool operator<(bigInt& b);
	const bool operator==(bigInt& b);
	const bool operator!=(bigInt& b);
	const bool operator>=(bigInt& b);
	const bool operator<=(bigInt& b);
	const bigInt& bigInt::operator^(long& b);
	const bigInt& bigInt::operator^(bigInt& b);

	void getValue(char thisBigInt[]) {strcpy(thisBigInt, a); } // return a string which is equivalent to the number
	void setValue(char thisBigInt[]) {strcpy(a, thisBigInt); } // set string thisBigInt to the value of an instance
	int getLength() { return strlen(a); }
	char getDigit(int pos) { return a[pos]; } // return CHARACTER at position i
	void setDigit(int pos, char value) { a[pos] = value; } // set CHARACTER at position i to value
	void print() { for (int i = 0; i < getLength(); i++) cout << a[i]; }
	void reverse(void);
	void clear(char ar[]) { ar[0] = '0'; ar[1] = '\0'; }
	void fixArray(char ar[]);

private:
	char a[SIZE];
	bool negative;
	bool zero;
	//helper functions
	int value(char c) { return c - 48; } //convert a character into the digit form
	char represent(int k) { return (char)(k + 48); } //convert a digit into the character form
	int maximum(int a, int b) { return (a > b) ? a : b; }
};

void bigInt::fixArray(char ar[])
{
	int j = 0;
	int len = strlen(ar);
	while ((ar[j] == '0') && (j < len))
		j++;
	if (j == len)
		clear(ar);
	else {
		for (int i = 0; i < len - j; i++)
			ar[i] = ar[i + j];
		ar[len - j] = '\0';
	}
}

const bigInt& bigInt::operator=(const bigInt& rhs)
{
	if (this != &rhs) {			// check for self assignment
		negative = rhs.negative;
		zero = rhs.zero;
		strcpy(a, rhs.a);
	}
	return *this;	//enable cascading
}

//reverse a string
void bigInt::reverse(void)
{
	int len = getLength();
	for (int i = 0; i < len/2; i++) {
		char temp = a[i];
		a[i] = a[len-1-i];
		a[len-1-i] = temp;
	}
}

//========================================== Multiplication function ==============================//
const bigInt& bigInt::operator*(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	int i = 0, j = 0;
	int carry[SIZE][SIZE];
	int r[SIZE][SIZE];

	//reverse 2 number for the convenience in computing
	reverse();
	b.reverse();
	
	//initialize carry[][] and r[][]
	for (i = 0; i <SIZE; i++)
		for (j = 0; j < SIZE; j++) {
			carry[i][j] = 0;
			r[i][j] = 0;
	}

	//fill digits into the array r, which is the temp table in multiplying 2 numbers
	for (i = 0; i < len2; i++) {
		
		for (j = 0; j < len1; j++) {
			
			int x = value(getDigit(j));
			int y = value(b.getDigit(i));
			if (j != 0) {

				r[i][j+i] = (x * y + carry[i][j+i-1]) % 10; // each digit is computed from the product of 2 digits from the operands and the carry from the previous computation
				carry[i][j+i] = (x * y + carry[i][j+i-1]) /10;
				
			}
			else {
				r[i][j+i] = x * y % 10;
				carry[i][j+i] = x * y / 10;
			}
			
		}
		r[i][len1+i] = carry[i][len1+i-1];
		
	}
	
	int carry1[SIZE]; //carry array for the final product
	int tempResult[SIZE]; //final product in digit form
	
	//initialize carry1[] and tempResult[]
	for (i = 0; i < SIZE; i++)
		carry1[i] = 0;
	for (i = 0; i < SIZE; i++)
		tempResult[i] = 0;

	//compute tempResult from the temp table
	for (i = 0; i < len1 + len2; i++) {
		for (j = 0; j < len2; j++)
			tempResult[i] += r[j][i];
		if (i == 0) {
			carry1[i] = tempResult[i] / 10;
			tempResult[i] = tempResult[i] % 10;
		}
		else {
			int temp = tempResult[i];
			tempResult[i] = (temp + carry1[i-1]) % 10;
			carry1[i] = (temp + carry1[i-1]) / 10;
		}
	}
	
	char result[SIZE];
	//convert the final product in digit form into character form
	for (i = 0; i < len1 + len2; i++)
		result[i] = represent(tempResult[i]);
	
	//check if there is a '0' at the beginning of the product
	if (value(result[len1 + len2 - 1]) == 0)
		result[len1 + len2 - 1] = '\0'; // if so, obmit it
	else
		result[len1 + len2] = '\0';
	
	//reverse the operands to get back the original value
	reverse();
	b.reverse();
	//reverse the final result in character form to obtain the correct order
	bigInt returnResult(result);
	returnResult.reverse();

	return returnResult;
}
//=================================================================================================//

//========================================== Addition function ====================================//
const bigInt& bigInt::operator+(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	int i = 0;
	
	//reverse 2 number for the convenience in computing
	reverse();
	b.reverse();
			
	int numA[SIZE], numB[SIZE];
	int carry[SIZE]; //carry array for the sum
	int tempResult[SIZE]; //sum in digit form
	
	//initialize numA[] and numB[]
	for (i = 0; i < SIZE; i++) {
		numA[i] = 0;
		numB[i] = 0;
	}

	if (len1 > len2) {
		for (i = 0; i < len1; i++)
			numA[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numB[i] = value(b.getDigit(i));
		for (i = len2; i < len1; i++)
			numB[i] = 0;
	}
	else {
		for (i = 0; i < len1; i++)
			numA[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numB[i] = value(b.getDigit(i));
		for (i = len1; i < len2; i++)
			numA[i] = 0;
	}

	//initialize carry[] and tempResult[]
	for (i = 0; i < SIZE; i++)
		carry[i] = 0;
	for (i = 0; i < SIZE; i++)
		tempResult[i] = 0;

	int len = maximum(len1, len2);
	//compute tempResult
	for (i = 0; i < len + 1; i++) {
		tempResult[i] = numA[i] + numB[i];
		if (i == 0) {
			carry[i] = tempResult[i] / 10;
			tempResult[i] = tempResult[i] % 10;
		}
		else {
			int temp = tempResult[i];
			tempResult[i] = (temp + carry[i-1]) % 10;
			carry[i] = (temp + carry[i-1]) / 10;
		}
	}
	tempResult[len+1] = carry[len];
	
	char result[SIZE];
	//convert the final product in digit form into character form
	for (i = 0; i < len + 1; i++)
		result[i] = represent(tempResult[i]);
	
	//check if there is a '0' at the beginning of the product
	if (value(result[len]) == 0)
		result[len] = '\0'; // if so, obmit it
	else
		result[len + 1] = '\0';
	
	reverse();
	b.reverse();
	//reverse the final result in character form to obtain the correct order
	bigInt returnResult(result);
	returnResult.reverse();
	
	return returnResult;
}
//=================================================================================================//

//========================================== Subtraction function =================================//
const bigInt& bigInt::operator-(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	int i = 0, j;
	bool negativeFlagOfResult = false;
	bool zeroFlagOfResult = false;
	
	int numA[SIZE], numB[SIZE];
	int carry[SIZE]; //carry array for the sum
	int tempResult[SIZE]; //sum in digit form
	
	char result[SIZE];
	//initialize result[]
	for (i = 0; i < SIZE; i++)
		result[i] = '0';

	//initialize numA[] and numB[]
	for (i = 0; i < SIZE; i++) {
		numA[i] = 0;
		numB[i] = 0;
	}

	if (*this > b) { //positive number
		negativeFlagOfResult = false;
		zeroFlagOfResult = false;
		reverse();
		b.reverse();
		for (i = 0; i < len1; i++)
			numA[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numB[i] = value(b.getDigit(i));
		for (i = len2; i < len1; i++)
			numB[i] = 0;
	}
	else if (*this < b) { //negative number
		negativeFlagOfResult = true;
		zeroFlagOfResult = false;
		reverse();
		b.reverse();
		for (i = 0; i < len1; i++)
			numB[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numA[i] = value(b.getDigit(i));
		for (i = len1; i < len2; i++)
			numB[i] = 0;
	}
	else {
		negativeFlagOfResult = false;
		zeroFlagOfResult = true;
		clear(result);
		bigInt returnResult(result, negativeFlagOfResult, zeroFlagOfResult);
		returnResult.reverse();
		return returnResult;
	}
	
	//initialize carry[] and tempResult[]
	for (i = 0; i < SIZE; i++)
		carry[i] = 0;
	for (i = 0; i < SIZE; i++)
		tempResult[i] = 0;

	int len = maximum(len1, len2);
	
	//compute tempResult
	if (numA[0] < numB[0]) {
		tempResult[0] = numA[0] + 10 - numB[0];
		carry[0] = 1;
	}
	else {
		tempResult[0] = numA[0] - numB[0];
		carry[0] = 0;
	}

	for (i = 1; i < len; i++) {
		if (numA[i]	< carry[i-1] + numB[i]) {
			tempResult[i] = numA[i] + 10 - carry[i-1] - numB[i];
			carry[i] = 1;
		}
		else {
			tempResult[i] = numA[i] - carry[i-1] - numB[i];
			carry[i] = 0;
		}
	}
	
	//convert the final product in digit form into character form
	for (i = 0; i < len; i++)
		result[i] = represent(tempResult[i]);
	
	//remove unnecessary '0's at the beginning of the array
	j = len - 1;
	while ((result[j] == '0') && (j != -1))
		j--;
	if (j == -1)
		clear(result);
	else
		result[j+1] = '\0';
	
	reverse();
	b.reverse();
	
	//reverse the final result in character form to obtain the correct order
	bigInt returnResult(result, negativeFlagOfResult, zeroFlagOfResult);
	returnResult.reverse();

	return returnResult;
}
//=================================================================================================//

const bigInt& bigInt::operator/(bigInt& b)
{
	bigInt tempDividend, quotient;
	char tempDividendResult[SIZE] = "", quotientResult[SIZE] = "";
	char c;
	int i = 0, j, k;
	
	while (i < getLength()) {
		if (tempDividend < b) {
			c = getDigit(i);
			tempDividend.getValue(tempDividendResult);
			k = strlen(tempDividendResult);
			tempDividendResult[k] = c;
			tempDividendResult[k+1] = '\0';
			tempDividend.fixArray(tempDividendResult);
			tempDividend.setValue(tempDividendResult);
			if (tempDividend < b) {
				k = strlen(quotientResult);
				quotientResult[k] = '0';
				quotientResult[k+1] = '\0';
				quotient.fixArray(quotientResult);
				quotient.setValue(quotientResult);
				i++;
			}
		}
		else {
			j = 0;
			while (tempDividend >= b) {
				tempDividend = tempDividend - b;
				j++;
			}
			quotient.getValue(quotientResult);
			k = strlen(quotientResult);
			quotientResult[k] = represent(j);
			quotientResult[k+1] = '\0';
			quotient.fixArray(quotientResult);
			quotient.setValue(quotientResult);
			i++;
		}
	}

	return quotient;
}

//=================================================================================================//
const bigInt& bigInt::operator%(bigInt& b)
{
	bigInt tempDividend, quotient;
	char tempDividendResult[SIZE] = "", quotientResult[SIZE] = "";
	char c;
	int i = 0, j, k;
	
	while (i < getLength()) {
		if (tempDividend < b) {
			c = getDigit(i);
			tempDividend.getValue(tempDividendResult);
			k = strlen(tempDividendResult);
			tempDividendResult[k] = c;
			tempDividendResult[k+1] = '\0';
			tempDividend.fixArray(tempDividendResult);
			tempDividend.setValue(tempDividendResult);
			if (tempDividend < b) {
				k = strlen(quotientResult);
				quotientResult[k] = '0';
				quotientResult[k+1] = '\0';
				quotient.fixArray(quotientResult);
				quotient.setValue(quotientResult);
				i++;
			}
		}
		else {
			j = 0;
			while (tempDividend >= b) {
				tempDividend = tempDividend - b;
				j++;
			}
			quotient.getValue(quotientResult);
			k = strlen(quotientResult);
			quotientResult[k] = represent(j);
			quotientResult[k+1] = '\0';
			quotient.fixArray(quotientResult);
			quotient.setValue(quotientResult);
			i++;
		}
	}

	return tempDividend;
}

//=================================================================================================//
const void bigInt::operator+=(bigInt& b)
{
	bigInt result;
	result = *this + b;
	*this = result;
}

const void bigInt::operator*=(bigInt& b)
{
	bigInt result;
	result = *this * b;
	*this = result;
}

const void bigInt::operator-=(bigInt& b)
{
	bigInt result;
	result = *this - b;
	*this = result;
}

const void bigInt::operator/=(bigInt& b)
{
	bigInt result;
	result = *this / b;
	*this = result;
}

const void bigInt::operator%=(bigInt& b)
{
	bigInt result;
	result = *this % b;
	*this = result;
}

const bool bigInt::operator>(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	
	if ((!negative) && b.getNegative())
		return true;
	else if (negative && (!b.getNegative()))
		return false;
	else if ((!negative) && (!b.getNegative())) {
		if (len1 > len2)
			return true;
		else if (len1 < len2)
			return false;
		else {
			int j = 0;
			while ((a[j] == b.a[j]) && (j != len1))
				j++;
			if (j == len1)		
				return false; // a == b
			else {
				if (value(getDigit(j)) > value(b.getDigit(j)))
					return true;
				else
					return false;
			}
		}
	}
	else if (negative && b.getNegative()) {
		if (len1 > len2)
			return false;
		else if (len1 < len2)
			return true;
		else {
			int j = 0;
			while ((a[j] == b.a[j]) && (j != len1))
				j++;
			if (j == len1)		
				return false; // a == b
			else {
				if (value(getDigit(j)) > value(b.getDigit(j))) 
					return false;
				else 
					return true;
			}
		}
	}
}

const bool bigInt::operator<(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	
	if ((!negative) && b.getNegative())
		return false;
	else if (negative && (!b.getNegative()))
		return true;
	else if ((!negative) && (!b.getNegative())) {
		if (len1 > len2)
			return false;
		else if (len1 < len2)
			return true;
		else {
			int j = 0;
			while ((a[j] == b.a[j]) && (j != len1))
				j++;
			if (j == len1)		
				return false; // a == b
			else {
				if (value(getDigit(j)) > value(b.getDigit(j))) 
					return false;
				else 
					return true;
			}
		}
	}
	else if (negative && b.getNegative()) {
		if (len1 > len2)
			return true;
		else if (len1 < len2)
			return false;
		else {
			int j = 0;
			while ((a[j] == b.a[j]) && (j != len1))
				j++;
			if (j == len1)		
				return false; // a == b
			else {
				if (value(getDigit(j)) > value(b.getDigit(j)))
					return true;
				else
					return false;
			}
		}
	}
}

const bool bigInt::operator==(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	
	if (len1 != len2)
		return false;
	else {
		int j = 0;
		while ((a[j] == b.a[j]) && (j != len1))
			j++;
		if (j == len1)		
			return ((negative && b.getNegative()) || (!negative && (!b.getNegative()))); // a == b
		else 
			return false;
	}
}

const bool bigInt::operator!=(bigInt& b)
{
	return !(*this == b);
}

const bool bigInt::operator>=(bigInt& b)
{
	return ((*this > b) || (*this == b));
}

const bool bigInt::operator<=(bigInt& b)
{
	return ((*this < b) || (*this == b));
}

const bigInt& bigInt::operator^(long& b)
{
	//I wrote this part myself
long i;
bigInt out;
bigInt one("1");
out = *this;

for (i=1;i<b;i++)
{
	out *=	(*this);
}

return out;
}

const bigInt& bigInt::operator^(bigInt& b)
{
	//I wrote this part myself
bigInt i("1");
bigInt out;
bigInt one("1");
out = *this;

while (i<b)
{
	out *=	(*this);
	i=i+one;
}


/*for (i=1;i<b;i=i+1)
{
	out *=	(*this);
}*/

return out;
}
//========================================== MAIN FUNCTION ========================================//
void findM();
void main(void)
{
	bigInt p("257");
	bigInt q("263");
//	bigInt p("17");
//	bigInt q("11");
	bigInt N,C,e("7"),LetterUpE;
	bigInt Letter("88");

	//Find N
	N = p*q;
	N.print();

	//Find C^e
	LetterUpE = Letter^e;

	//find C = Letter ^ 2 mod N
	C = LetterUpE % N;

	cout<< endl << "C=";
	C.print();

	cout<< endl;

	//decrypt
	bigInt phi, phione;
	bigInt d, one("1"),M, CupD;

	//find phi = (p-1)(q-1)
	phi = bigInt(p-one) * bigInt(q-one);
	cout<<endl << "phi:";
	phi.print();
	
	bigInt test;
	char *cTest;
	int intAns;

	intAns = 1;
	
	//find d - I have tried a few methods to do this but I think starting from 1 and going up
	d.setZero(1);

	while (intAns != 0)
	{	
		d=d+one;
		test = bigInt(d * e);
		test = test - one;
		test = test % phi;

		cTest = new char(test.getLength());
		test.getValue(cTest);

		intAns = atoi(cTest);

		//if de-1 mod phi = 0 then thats our d
		if (intAns ==0)
			break;

		

	}


	cout << endl << "d:";
	d.print();
	
	CupD = C ^ d;
	M = CupD % N;
	
	cout << endl << "CupD:";
	CupD.print();
	cout << endl << "M:";
	M.print();





}

void findM()
{
	bigInt C("36487");
	bigInt d, NumPow, M;
	bigInt Mod("67591");
	int intD,iLoop,intM, intAns;
	char charD[10];
	char charAns[2];
	FILE *fin;
	FILE *fout;
	
	fin = fopen("d:\\cmathsnums.txt","r+");
	fscanf(fin,"%d",&intD);
	fclose(fin);

	for (iLoop=intD;iLoop<80000;iLoop++)
	{
		itoa(iLoop,charD,10);
		d.setValue(charD);
		if (NumPow.getLength()<2)
			NumPow = C ^ d;
		else
			NumPow *= C;

		M = NumPow % Mod;
		if (M.getLength()==2){
			M.getValue(charAns);
			intAns = atoi(charAns);
			if (intAns==82)
			{
				cout << iLoop;
				fout = fopen("d:\\cmathans.txt","a+");
				fprintf(fout,"d=%d\n",iLoop);
				fclose(fout);
			}
		
		}

		if (iLoop % 100 == 0)
		{
				cout << iLoop;
				fin = fopen("d:\\cmathsnums.txt","w+");
				fprintf(fin,"%d",iLoop);
				fclose(fin);			
		}

	}


	cout << intD;
//	return;



/*	bigInt p="257";
	bigInt q = "263";
	bigInt N;
	long e=7;
	bigInt C;
	bigInt bChar("82");
	bigInt d;
	bigInt bCharPowE;
	bigInt one("1");
	bigInt r;
	char five;
	int j;
	strcpy(&five,"5");
	//j = ctoi();
	j = atoi(&five);

	cout << j+1;
	return;

	r= (bigInt)"5";

	N = p*q;
	bCharPowE = (bChar^e);
	C= bCharPowE % N;

	C.print();
	cout << endl;

	bigInt M;
	bigInt pqMinusOne;

	pqMinusOne = (((bigInt)"256")*((bigInt)"262"));
	pqMinusOne += one;

	cout << endl << "pqMinusOne=";
	pqMinusOne.print();


	d = pqMinusOne/(bigInt)"7";
	cout << endl << "d=";
	d.print();

	bigInt CpowD;
	CpowD = C^d;

	cout << endl << "CpowD=";
	CpowD.print();

	M = CpowD % N;
	cout << endl;
	M.print();


	bigInt a("123");
	bigInt b("45");
	bigInt c;
	bigInt C("11");
	long d(23);
	bigInt mod("187");
	bigInt pow;
	
	pow = C^d;

	pow.print();
	*/
	cout << endl;
	//c = a % b;
	/*c = (pow) % mod;
	c.print();
	cout << endl;*/

/**/
}