#include <cassert>
#include<iostream>
#include<cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

int ExtendedEuclidAlgGCD(int a, int b, int &s, int &t);
int EuclidAlgGCD(int a, int b);
int mod(int a, int n);
int inverse(int a, int n);
int encrypt(int m, int e, int n);
int decrypt(int c, int d, int n);
int RelativelyPrime(int n);
// function for euclidean algorithm 
int EuclidAlgGCD(int a, int b) {
    if (b == 0)
        return a;
    return EuclidAlgGCD(b, a % b);
}

// Function for Extended Euclidean Algorithm
int ExtendedEuclidAlgGCD(int a, int b, int &s, int &t)
{
  if (b == 0)
  {
    s = 1;
    t = 0;
    return a;
  }
  else
  {
    int s1, t1;
    int d = ExtendedEuclidAlgGCD(b, a % b, s1, t1);
    s = t1;
    t = s1 - (a / b) * t1;
    return d;
  }
}
// Function to find the modular inverse
int mod(int a, int n)
{
  int result = a % n;
  if (result < 0)
  {
    result += n;
  }
  return result;
}


// inverse function
int inverse(int a, int n) {
a = a % n;
for (int i = 1; i < n; i++) {
if ((a * i) % n == 1) return i;
}
return -1; }
// encrypting function
int encrypt(int m, int e, int pq) {
   

// decrypting function
int decrypt(int c, int d, int pq) {
    int solved = 1;
    for (int i = 0; i < d; i++) {
        solved = (solved * c) % pq; }
    return solved; }
int RelativelyPrime(int n) {
    int h;

    do {
        h = rand() % (n - 1) + 2; 
    } while (EuclidAlgGCD(n, h) != 1);

    return h;
}
bool IsPrime(int n) {
    if (n <= 1) {
        return false;
    }
    
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}


int main() {
   //2 random prime numbers
   int p = 13;
   int q = 11;
   int pq =p*q; //calculate n
   int track;
   int phi = (p-1)*(q-1);
   //public key
    cout << "Choose e. Should be a prime small number: " << endl;
    int e; // should i choose e or let the input choose
    cin >> e;
    int m;
    int d = inverse(e, phi);

    cout << "p: " << p << endl;
    cout << "q: " << q << endl;
    cout <<"pq: " << pq << endl;
    cout << "phi: " << phi << endl; //?
    cout << "e: " << e << endl;
    cout << "d: " << d << endl;


    // Encryption
    cout <<"Enter an integer that is smaller than " << pq << endl;
    cin >> m;
    int c = encrypt(m, e, pq);
    cout << "Encrypted message (c): " << c << endl;

    // Decryption
    int m1 = decrypt(c, d, pq);
    cout << "Decrypted message (m): " << m1 << endl;
     assert (m==m1);
  
}