RSA

#include <iostream>
#include <cmath>

using namespace std;

struct par {
    int r,t;
};

par euclid(int a, int b) {
    int x = a;
    int y = b;
    int t0 = 0;
    int t1 = 1;
    int r = b;
    int t = 1;
    int q;
    printf("q: -\tr: -\tt: -\tx: %d\ty: %d\tt0: %d\tt1: %d\t x mod y:%d\n",x,y,t0,t1,x%y);
    while ((x%y) != 0) {
        r = x % y;
        q = x / y;
        t = (t0 - q*t1) % a;
        x = y;
        y = r;
        t0 = t1;
        t1 = t;
        printf("q: %d\tr: %d\tt: %d\tx: %d\ty: %d\tt0: %d\tt1: %d\tx mod y: %d\n",q,r,t,x,y,t0,t1,x%y);
    }
    par p;
    p.r = r;
    p.t = t;
    return p;
}

// return b^e mod m
int modular_pow(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent & 1)
            result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}


int main () {
    int a,b,n,x;
    cout << "Kérem fi(n)-t" << endl;
    cin >> a;
    cout << "Kérem e-t" << endl;
    cin >> b;
    cout << "Kérem n-t" << endl;
    cin >> n;
    par p = euclid(a,b);
    cout << "r: " << p.r << endl;
    cout << "t: " << p.t << endl;
    int res = (b* p.t) % a ;
    if (res < 0)
        res += a;
        res %= a;
    cout << "Ellenőrzés: " << b << "*" <<  p.t <<" mod (" << a << ") = " << res << endl;
    while (!cin.eof()) {
        cout << "Kérem a titkosítandó üzenetet" << endl;
        cin >> x;
        int y = modular_pow(x, b, n);
        cout << "y = x^e mod n: " << y << endl;
        int z = modular_pow(y, p.t, n);
        cout << "x = y^d mod n: " << z << endl;
    }
    return 0;
}



/*
INPUT:
a (egyik szám)
b (másik szám)
OUTPUT: r (a és b legnagyobb közös osztója)
t (az a legkisebb szám melyre t*b mod a = r)
// feltesszük, hogy a > b
// (ellenkez ̋ esetben felcseréljük a bementeket)
o
x = a
y = b
t0 = 0
t1 = 1
r = b
t = 1
WHILE (x mod y) != 0
q = x div y // maradékos osztás eredménye
r = x mod y // és maradéka
t = (t0 - q*t1) mod a
x = y
y = r
t0 = t1
t1 = t
ENDWHILE
RETURN r, t
*/