// CSci 4509 Affine Cipher implementation
// Elena Machkasova, 1/19/05

public class AffineCipher {
    public static void main(String[] args) {
	// testing mod
	/*
	System.out.println(mod(7, 3));
	System.out.println(mod(-7, 3));
	System.out.println(mod(-101, 7));
	*/
	System.out.println(mod(11 * 19, 26));

	if (args.length < 4) {
	    System.out.println("Usage: java ShiftCipher mode a b message");
	    System.out.println("mode: e for encrypt. d for decrypt");
	    System.out.println("a: an integer <= 25, b: an integer <= 25");
	    System.out.println("message: the message to encrypt or decrypt");
	    System.exit(0);
	}

	int a = (new Integer(args[1])).intValue();
	int b = (new Integer(args[2])).intValue();
	if (a < 1 || a > 25 || a < 0 || b > 25) {
	    System.out.println("Illegal value of a or b " + a + " " + b);
	    System.exit(0);
	}
	
	if (args[0].equals("e") || args[0].equals("E")) {
	    // encrypting
	    System.out.println(encrypt(args[3], a, b));
	} else if (args[0].equals("d") || args[0].equals("D")) {
	    // decrypting
	    System.out.println(decrypt(args[3], a, b));
	} else {
	    System.out.println("the first argument must be e or d");
	    System.exit(0);
	}
	
    }

    // computes n mod m defined as the smallest
    // non-negative integer r such that n = k * m + r, 
    // where k is an integer 
    // Assume that m > 0
    public static int mod(int n, int m) {
	int r = n % m;
	if (r < 0) r = r + m;
	return r;
    }

    // assume that the key is valid
    public static String encrypt(String plaintext, int a, int b) {
	int length = plaintext.length();
	StringBuffer ciphertext = new StringBuffer();
	for (int i = 0; i < length; ++i) {
	    char letter = plaintext.charAt(i);
	    if (!Character.isLetter(letter)) {
		System.out.println("Illegal character " + letter);
		System.exit(0);
	    }
	    int position = -1;
	    if (Character.isUpperCase(letter)) {
		position = letter - 'A';
	    }
	    else if (Character.isLowerCase(letter)) {
		position = letter - 'a';
	    }
	    int cipherposition = mod(a * position + b, 26);
	    //System.out.println(cipherposition);
	    ciphertext.append((char) ('A' + cipherposition));
	}
	return ciphertext.toString();
    }

        // assume that the key is valid
    public static String decrypt(String ciphertext, int a, int b) {
	int aInverse = inverse(a, 26);
	int length = ciphertext.length();
	StringBuffer plaintext = new StringBuffer();
	for (int i = 0; i < length; ++i) {
	    char letter = ciphertext.charAt(i);
	    if (!Character.isLetter(letter)) {
		System.out.println("Illegal character " + letter);
		System.exit(0);
	    }
	    int position = -1;
	    if (Character.isUpperCase(letter)) {
		position = letter - 'A';
	    }
	    else if (Character.isLowerCase(letter)) {
		position = letter - 'a';
	    }
	    int plainposition = mod(aInverse * (position - b), 26);
	    //System.out.println(plainposition);
	    plaintext.append((char) ('A' + plainposition));
	}
	return plaintext.toString();
    }

    // find a multiplicative inverse of an integer num modulo an integer base
    // If num is not relatively prime to base, throw a RuntimeException
    // The method implements Extended Euclidean algorithm
    public static int inverse(int num, int base) {
	int b = base;
	int a = num;
	int k1 = 1;
	int k2 = 0;
	int k3 = 0;
	int k4 = 1;
	while (b != 0) {
	    int rem = mod(a, b);
	    int quot = a / b;
	    a = b;
	    b = rem;
	    int new1 = k1 - quot * k3;
	    int new2 = k2 - quot * k4;
	    k1 = k3;
	    k2 = k4;
	    k3 = new1;
	    k4 = new2;
	}

	//System.out.println("k1 = " + k1 + " k2 = " + k2 + " k3 = " + k3 + " k4 = " + k4);
	//System.out.println(mod(k1, 26));
	
	if (mod (k1 * num, base) != 1) {
	    throw new RuntimeException(a + " is not relatively prime with " + base);
	}
	return mod(k1, base);
    }
}

DMLQIFVMHQGLRXDFFY