// IRA_Lab_2.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;

struct ABON {
    long long c;
    long long d;
    long long x;
};

struct ABON_RSA{
    long long P;
    long long Q;
    long long N;
    long long d;
    long long c;
};

struct EGMessage {
    long long r;
    long long e;
    long long p;
};

struct STR {
    long long arg1;
    long long arg2;
    long long arg3;
};

bool simpleChecker(long long p){
    for (long long i = 2; i <= sqrt((double)p); i++){
        if (p%i == 0)
            return false;
    }
    return true;
};

long long simpleGen(long long order){
    long long gen, check;
    if(order)
        gen = (rand() * rand() + rand()) % order;
    else
        gen = rand() * rand() + rand() + 1;
    do{
        gen++;
		check = simpleChecker(gen);
    } while (!check);
	return gen;
}

STR gcdO(long long a, long long b){
    STR U, V, T;
    long long q;
    U.arg1 = a; U.arg2 = 1; U.arg3 = 0;
    V.arg1 = b; V.arg2 = 0; V.arg3 = 1;
    while (V.arg1 != 0){
        q = U.arg1 / V.arg1;
        T.arg1 = U.arg1%V.arg1; T.arg2 = U.arg2 - q*V.arg2; T.arg3 = U.arg3 - q*V.arg3;
        U = V; V = T;
    }
    return U;

}

long long gcd(long long a, long long b){
	long long r;
	while (b != 0){
		r = a%b; a = b; b = r;
	}
	return a;
}

long long codeMod(long long a, long long x, long long p){
    long long rez = 1;
    for (long long aCurr=a%p; x>0; x>>=1, aCurr = (aCurr*aCurr)%p)
        if (x & 1)
            rez = rez*aCurr%p;
    return rez;
}

long long genC(long long p){
	long long c;
	do{
		c = simpleGen(0);
	}while(gcd(c, p - 1)!=1 || c<=1 || c>=p-1);
	return c;
}

long long calcD(long long p,long long c){
    long long result;
    STR gcd = gcdO(c,p-1);
    result=gcd.arg2;
    if (result>0)
        return result;
    else
        return result+p-1;

}

long long ShamirExample(){
    long long  p=71,m=10;
    ABON A,B;
	p = simpleGen(0);
	cout<<"p = "<<p<<endl;
	A.c = genC(p);
	A.d = calcD(p, A.c);
	cout<<"A.c = "<<A.c<<" A.d = "<<A.d<<endl;
	B.c = genC(p);
	B.d=calcD(p,B.c);
    cout<<"B.c = "<<B.c<<" B.d = "<<B.d<<endl;
	A.x=codeMod(m,A.c,p);
    B.x=codeMod(A.x,B.c,p);
    A.x=codeMod(B.x,A.d,p);
    B.x=codeMod(A.x,B.d,p);
	cout<<"message: "<<B.x<<endl;
    return B.x;
}

EGMessage EGCode(ABON B,long long m,long long p,long long k, long long g){
    EGMessage message;
    message.p=p;
    message.r=codeMod(g,k,p);
    message.e=(m*codeMod(B.d,k,p))%p;
    return message;
}

long long EGDeCode(EGMessage message,ABON B){
    long long p=message.p;
    long long m=(message.e*codeMod(message.r,p-1-B.c,p))%p;
    return m;
}

void EGExample(){
    EGMessage message;
    ABON B;
   	long long k=7,q,p,g;
   	while(true)
	{
		q = simpleGen(0);
		if(simpleChecker(2*q+1))
		{
			p = 2 * q + 1;
			cout<<"p = "<<p<<endl;
			break;
		}
	}
	for(long long i=2; i < p-1; ++i){
		if(simpleChecker(i) && codeMod(i, q, p)!=1){
			g=i;
			break;
		}
	}
	long long m=15;
    B.c=genC(p);
    B.d=calcD(p,B.c);
    message=EGCode(B,m,p,k,g);
    cout<<"message.r = "<<message.r<<" message.e = "<<message.e<<endl;
    cout<<"Decoded: "<<EGDeCode(message,B)<<endl;

}

long long calcF(ABON_RSA B){
    long long result=(B.Q-1)*(B.P-1);
    return result;
}

long long RSACode(ABON_RSA B,long long m) {
    long long e=codeMod(m,B.d,B.N);
    return e;
}

long long RSADecode(long long e, ABON_RSA B){
    long long result=codeMod(e,B.c,B.N);
    return result;
}

long long RSAExample(){
    ABON_RSA B;
    long long m=15;
    long long e;
    B.P=3;
    B.Q=11;
    B.N=33;
    B.d=3;
    long long F=calcF(B);
    STR st1=gcdO(F,B.d);
    B.c=st1.arg3;
    e=RSACode(B,m);
    cout<<RSADecode(e,B);
    return 0;
}

int main(){
    srand(time(NULL));

     EGExample();
    // RSAExample();
	//ShamirExample();
    return 0;
}