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

int ModularExponential(int,int,int);
int gcd(int,int,int&,int&);
int calculateD(int);
int getE(int,int);

int main()
{
        FILE *f;
        int arr[5000];
                f = fopen("file.txt","r");
                if(f != NULL){

                        for(int i = 0; i < 5000; ++i)
                            fscanf(f,"%d", &arr[i]);

                }
                else
                    std::cout << "No file";
               int i,j;
               int p = arr[std::rand()%1000];;
                int q = arr[std::rand()%1000];
               int n = p * q;
                int Euler = (p-1)*(q-1);
                int d = calculateD(Euler);
                int e = getE(Euler,d);
                int g = gcd(e,Euler, i, j);
                int m = 2;
                int k = ModularExponential(m,e,n);
                int l = ModularExponential(m,e*d,n);
               std::cout <<" p = " << p << " q = " <<q << " phi = " << Euler <<
                   " e = " << e << " d = " << d << " k = " << k << " l = " << l;
                fclose(f);
        system("pause");
                return 0;
}

int ModularExponential(int x,int d ,int n){
        x %= n;
        int result = 1;
        while(d > 0){
                        if( d & 1)
                                result = (result * x) % n;
                        x = (x*x) % n;
                        d >>= 1;
        }
        return result;
}

int gcd (int a, int b, int & x, int & y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

int calculateD(int phi){
    int d_s = 0, d,x,y;
    while(d_s != 1)
    {
        d = rand()%100;
        d_s = gcd(d,phi,x,y);
    }
    return d_s;
}

int getE(int phi,int d){
    int e = 0, e_s = 0, x,y;
    while(e_s != 1){
        e += 1;
        e_s = (e*d)%phi;
    }
    return e_s;
}