#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

long long p,q,e,d;



//Euklideszi algoritmus:
long long euk(long long a,long long b) {
    long long csere;

//amíg az a / b nem nulla, b  mardék, a meg az előző b
    while(a%b!=0)
    {
        csere=b;
        b=a%b;
        a=csere;
    }
    return b;
}
//kibovitett euklideszi módosított
long long kibeukmod(long long a,long long b) {

    long long x0 = 1, x1 = 0, y0 = 0, y1 = 1;
    long long csere1, csere2, csere3;
    long long elojel1 = -1, elojel2 = 1;
    long long fi=a;
    while(a % b != 0) {
        csere1 = (a / b) * y1 + y0 ;//yk sort számolja
        csere3 = (a / b) * x1 + x0 ;
        x0 = x1 ;
        y0 = y1 ;
        x1 = csere3 ;
        y1=csere1 ;
        csere2=b ;
        b= a % b ;//törtész
        a=csere2;
        elojel1=-elojel1;//kitevő és páratlanról indul
        elojel2=-elojel2;
    }
    x1= x1 * elojel1 ;
    y1 = y1 * elojel2;

    return y1;//d-t kapjuk vissza
}

long long kibeukmod2(long long a, long long b)
{

    /*long long y0=1;
    long long y1=0;
    long long y2 = 0;
    long long csere;//rk
    long long csere2;//qk
    long long elojel=-1;
    long long fi=a;
    while(a%b!=0)
    {
        csere=(a/b)*y1+y0;//yk sort számolja
        y0=y1;
        y1=csere;
        csere2=b;
        b=a%b;//törtész
        a=csere2;
        elojel=elojel * -1;//kitevő és páratlanról indul
    }
    y1=elojel*y1;
    while(y1<0) {
        y1=y1+fi;//d kiszámolása, d mindig pozitív
    }*/
    long long x0 = 1, x1 = 0, y0 = 0, y1 = 1;
    long long csere1, csere2, csere3;
    long long elojel1 = -1, elojel2 = 1;
    long long fi=a;
    while(a % b != 0) {
        csere1 = (a / b) * y1 + y0 ;//yk sort számolja
        csere3 = (a / b) * x1 + x0 ;
        x0 = x1 ;
        y0 = y1 ;
        x1 = csere3 ;
        y1=csere1 ;
        csere2=b ;
        b= a % b ;//törtész
        a=csere2;
        elojel1=-elojel1;//kitevő és páratlanról indul
        elojel2=-elojel2;
    }
    x1= x1 * elojel1 ;
    y1 = y1 * elojel2;

    return x1;//visszafejtésnél a c1 értékéhez kell
}

long long gyorshatvanyozas(long long alap, long long kitevo, long long mod)
{
    long long result = 1;
    while (kitevo > 0)
    {
        if (kitevo % 2 == 1)
            result = (result * alap) % mod;
        kitevo = kitevo >> 1;
        alap = (alap * alap) % mod;
    }
    return result;
}

long long miller_rabin(long long n) {
    long long a=2;
    long long d;
    long long s=0;
    long long n1=n-1;
    long long r;
    if(n%2==0)
    {
        return 0;
    }
    else
    {
        while(n1%2==0)//megszámolja hány S van benne
        {
            s++;
            n1=n1/2;
        }
        d=(n-1)/(int)pow(2,s);
        if(gyorshatvanyozas(a,d,n)==1)
        {
            return 1;
        }
        else
        {
            for(r=0; r<s; r++)
            {
                if(gyorshatvanyozas(a,(int)pow(2,r)*d,n)==n-1)
                {
                    return 1;
                }
            }
        }
        return 0;
    }

}

//addig generál, amíg két prímet nem ad vissza
void kulcsgeneralas() {
    long long n,fi;
    while(1) {
        p=rand();
        if(miller_rabin(p)==1)
        {
            break;
        }
    }

    p = 17 ;
    while(1) {
        q=rand();
        if(miller_rabin(q)==1)
        {
            break;
        }
    }
    q = 13 ;

    //a p-nek és a q-nak prímnek kell lenni
    //Miller-Rabin kell még ide, mert ez teszteli, hogy prím-e a p és a q
    n=p*q; //n es e a nyilvanos kulcs
    // generálni kell majd e-t
    fi=(p-1)*(q-1);

    while(1) //ide fogjuk belerakni az e generalast
    {
        //e=rand()%(fi-2)+2;
        e=rand()%(fi-2)+2;
        if(euk(fi,e)==1)// ezért írom előre a fi-t ,mert az nagyobb mlong long az e (füzet)
        {
            break;
        }
    }
    d=kibeukmod(fi,e);
    while(d < 0) {
        d += (p-1) * (q-1);
    }

}

long long titkositas (long long m) {

    return gyorshatvanyozas(m,e,p*q);

}
long long visszafejtes (long long c) {
    long long m;
    /*cp=c%p;
    cq=c%q;
    dp=d%(p-1);
    dq=d%(q-1);
    m=gyorshatvanyozas(cp,dp,p*q)*gyorshatvanyozas(q,p-1,p*q)+gyorshatvanyozas(cq,dq,p*q)*gyorshatvanyozas(p,q-1,p*q);*/
    long long nagyobb, kisebb ;
    long long c1, c2 ;
    long long y1, y2;
    long long kitevo1, kitevo2;
    if(p > q) {
        nagyobb = p;
        kisebb = q;
    }
    else {
        nagyobb = q;
        kisebb = p;
    }
    //y1 = kibeukmod2(nagyobb, kisebb);
    y1 = kibeukmod(nagyobb, kisebb);
    //y2 = kibeukmod(nagyobb, kisebb);
    y2 = kibeukmod2(nagyobb, kisebb);
    printf("y1: %lld\n",y1) ;
    printf("y2: %lld\n",y2) ;
    kitevo1 = d % (p - 1);
    kitevo2 = d % (q - 1);
    c1 = gyorshatvanyozas(c, kitevo1 , p);
    c2 = gyorshatvanyozas(c, kitevo2 , q);
    printf("c1: %lld\n",c1) ;
    printf("c2: %lld\n",c2) ;
    m =  (y1 * q * c1 )+ (y2 * p * c2) ;
    while (m < 0) {
       m += (p*q);
    }
    m = m % (p * q);

    return m;


}

int main() {
    srand (time(NULL));
    long long szam;
    long long m;
    char c[100];
    kulcsgeneralas();


    for (int i = 0; i <10; i++) {
        if (miller_rabin(12))
            printf("yes") ;
    }


    printf("p= %lld \nq= %lld \ne= %lld \nd= %lld \np * q= %lld\n fi(n)= %lld\n",p,q,e,d,p*q, (p-1) * (q - 1) );
    printf("#####################\n");
    printf("Adjon meg egy uzenetet, amit titkositunk: "), scanf("%lld", &m);
    //printf("Adja meg a kodlando szoveget: ", &c);
    szam=titkositas(m);
    printf("%lld titkositva: %lld\n",m, szam);
    printf("sima: %lld\n",gyorshatvanyozas(szam, d, p * q));
    printf("kinai:%lld\n",visszafejtes(szam));
}