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

bool is_prime (unsigned long n) {

    //any prime number must be of the form 6k+1 or 6k-1
    if ((n-1)%6 == 0 || (n+1)%6 == 0)
	; //maybe prime, continue
    else
	return false;
    //basically we checked for divisibility by both 3 and 2

    unsigned long int i;
    for (i = 5; i < (n/2)+1; i += 2)
	if (n%i == 0)
	    return false;
    return true;
}

long get_prime () {

    unsigned long n;

    n = random()%100;
    if (n%2 == 0)
	n++;

    while (1) {  
	if (is_prime (n))
	    break;
	n += 2;
    }

    return n;
    //assuming we do find a prime number at some time.
}

unsigned long hcf (long a, long b) {
    if (b < a) {
	unsigned long temp = a;
	a = b;
	b = temp;
    }
    //b is bigger now

    if (b%a == 0)
	return a;
    else
	return (hcf (a, b%a));
}

//return (p^q)%n
unsigned long exponential_mod (unsigned long p, unsigned long q, unsigned long n) {

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

int main () {

    unsigned long p, q, t, n, e, d;
    unsigned long plain, cipher;

    srandom (time(NULL));

    p = get_prime();
    do
	q = get_prime();
    while (p == q);

    n = p*q;
    t = (p-1)*(q-1);

    //find 'e' relatively prime to 't'

    for (e = 2; e < t; e++) {
	if (hcf (e,t) == 1)
	    break;
    }

    //find 'd' such that d*e congruent 1 mod (t)
    for (d = t+1; 1; d++) {
	if ((((d*e)-1) % t) == 0)
	    break;
    }

    printf ("p:%lu q:%lu n:%lu t:%lu e:%lu d:%lu\n", p, q, n, t, e, d);

    printf ("Enter plain text: ");
    scanf ("%lu", &plain);

    cipher = exponential_mod (plain, e, n);
    printf ("Cipher text: %lu\n", cipher);

    plain = exponential_mod (cipher, d, n);
    printf ("Decrypted text: %lu\n", plain);
    
    return 0;
}