#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool isprime (long p) {

    int i;

    //every prime number is of the form 6K+1 or 6k-1
    if (((p+1)%6 == 0) || ((p-1)%6 == 0)) {
	i = p/2;
	if (i%2 == 0)
	    i++;
	while (i >= 5) {
	    if (p%i == 0)
		return false;
	    i -= 2;
	}
	return true;
    }
    else
	return false;
}

long get_prime () {

    long p = random ()%100;
    while (!isprime (p))
	p++;

    return p;
}

bool is_relatively_prime (long p, long q) {

    int r;
    //euclid
    if (p < q) {
	int temp = p;
	p = q;
	q = temp;
    }

    do {
	r = p%q;
	p = q;
	if (r != 0)
	    q = r;
	else
	    break;
    }
    while (1);

    if (q == 1)
	return true;
    else
	return false;
}

//this calculates (p^q)mod (n)
long do_modular_exponentiation (long p, long q, long n) {

    //we use the property (ab)mod(c) = ((a)mod(c) * (b)mod(c))mod (c)

    if (q == 1)
	return (p%n);
    else
	return ((p%n)*do_modular_exponentiation(p,q-1,n))%n;
}

int main () {
    
    int pt, ct, pt2; //plain text and cipher text and pt decrypted
    long p, q, n, t, e, d;

    // choose two unique primes
    srandom (time(NULL));
    p = get_prime();
    do
	q = get_prime();
    while (q == p);

    printf ("p:%ld q:%ld ", p, q);
    n = p*q;
    printf ("n:%ld ", n);
    t = (p-1)*(q-1);
    printf ("t:%ld ", t);

    // choose a private key 'e', relatively prime to 't'
    for (e = 2; e < t ; e++)
	 if (is_relatively_prime (e, t)) {
 	    printf ("e:%ld ", e);
	    break;
 	}
    // Hoping we get an 'e' smaller than 't'. 
    // t+1 of course is valid, but it won't encrypt.
 
    for (d = 2; 1; d++)
	if (((d*e)-1)%t == 0) {
	    printf ("d:%ld\n", d);
	    break;
	}
    printf ("Enter plaintext number: ");
    scanf ("%d", &pt);

    //cipher text is (p^e)mod(n)

    ct = do_modular_exponentiation (pt, e, n);
    printf ("Cipher text: %d\n", ct);

    pt2 = do_modular_exponentiation (ct, d, n);
    printf ("Decrypted Cipher Text:%d\n", pt2);

    return 0;    
}