int modular_multiplicative_inverse(E, PHI){
  int D  = 0;
  int nt = 1;
  int r = PHI;
  int nr = E % PHI;

  // correct values to acceptable input range
  if (PHI < 0){
    PHI = -PHI;
  }
  if (E < 0){
    E = PHI - (-E % PHI);
  }

  // perform operations to calculate the MMI
  int quot;
  int tmp;
  while (nr != 0) {
    quot = (r/nr) | 0;
    tmp = nt;  
    nt = D - quot*nt;  
    D = tmp;
    tmp = nr;  
    nr = r - quot*nr;  
    r = tmp;
  }
  if (r > 1) { return -1; }
  if (D < 0) { D += PHI; }
  return D;
}

D = modular_multiplicative_inverse(5, 400656)
D = 320525

// memory efficient modular exponentiation for MSP430
//
// calculate PT, where - (CT^E) mod N = PT
// CT is the ciphertext
// E is the secret key
// N the the public key

//
// (CT^E) could be huge, thousands of digits, so we use this algorithm to calculate the value of PT
// after performing 'E' routines.  In this case 320525 iterations of the while loop are performed.

// this is a memory efficient encrypt and decrypt operations

#include <msp430.h>				
#define BIT0 (0x0001)
#define BIT6 (0x0040)

long long modular_exponentiation(long long cipher_text, long long exponent, long long publickey);

long long plaintext = 30;
long long ciphertext = 0;
long long exponent = 5;
long long publickey = 402047;
long long privatekey = 320525;
long long decrypted_plaintext = 0;

void main(void) {
	WDTCTL = WDTPW | WDTHOLD;		// Stop watchdog timer
	P1DIR |= (BIT0 | BIT6);					// Set P1.0 to output direction
	P1OUT = 0;

  // smaller test values
  // exponent = 17
  // public key = 3233
  // private key = 2753
  // plaintext = 65
  // ciphertext = 2790

  // larger
  // exponent = 5
  // public key = 402047
  // private key = 320525
  // plaintext = 30
  // ciphertext = 177180

  // encrypt

  // (plaintext^exponent) mod publickey
  // (PT^E) mod N
  ciphertext = modular_exponentiation(plaintext, exponent, publickey);

  // decrypt
  // (ciphertext^secretkey) mod publickey
  // (CT^D) mod N
  decrypted_plaintext = modular_exponentiation(ciphertext, privatekey, publickey);

  if(plaintext == decrypted_plaintext){
    // set the GREEN led
    P1OUT = BIT6;
  } else {
    // set the RED led
    P1OUT = BIT0;
  }

	//return 0;
}


long long modular_exponentiation (long long cipher_text, long long exponent, long long publickey){
  long long c = 1;
  long long e_prime = 0; // our counter variable
  while(e_prime < exponent){
	  e_prime = e_prime + 1;
	  if(e_prime % 2){
	   P1OUT = BIT0;
	  } else {
	   P1OUT = BIT6;
	  }
	  c = c * cipher_text;
	  c = c % publickey;
  }
  // c is the plaintext
  P1OUT = 0;
  return c;
}