/**
 * A class for RSA cryptography
 *
 * @version	$Id: RSA.java,v 1.2.2.2 2005/01/11 14:48:09 nthiery Exp $
 * @author	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
**/

import java.math.BigInteger;
import java.util.List;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ArrayList;
import gnu.regexp.*;

class RSA {

    /**
     * Returns a big integer from its list of digits in base radix
     *
     * For example, [0,1,0,0,1] in base 2 denotes the integer 18
     *
     * @param digits	a List of non-negative BigInteger: the list of digits.
     * @param radix	a non-negative BigInteger: the radix
     *
     * @return		the non-negative BigInteger whose digits are digits in base radix
     **/
    public static BigInteger fromBase(List digits, BigInteger radix) {
	BigInteger n = BigInteger.valueOf(0);
	BigInteger power = BigInteger.valueOf(1);
	for(Iterator it = digits.iterator(); it.hasNext();) {
	    // Invariant: power = radix^i
	    n=n.add(power.multiply((BigInteger)it.next()));
	    power=power.multiply(radix);
	}
	return(n);
    }

    /**
     * Returns the list of the digits of a big integer in base radix
     *
     * For example, the integer 18 is written as [0,1,0,0,1] in base 2
     *
     * @param n		a non-negative BigInteger
     * @param radix	a non-negative BigInteger: the radix
     *
     * @return		the list of digits of n in base radix, as a List of BigInteger
     **/
    public static List toBase(BigInteger n, BigInteger radix) {
	LinkedList digits = new LinkedList();
	while(!n.equals(BigInteger.valueOf(0))) {
	    BigInteger[] div = n.divideAndRemainder(radix);
	    n = div[0];
	    digits.add(div[1]);
	}
	return(digits);
    }

    /**
     * Encodes an ASCII string as a list of BigInteger's < radix
     *
     * By using the standard ASCII code, each character of the string
     * is considered as an integer between 0 and 255. Then, the whole
     * string is considered as a (big) non-negative integer written in
     * base 256, which is returned as a list of digits in base radix.
     *
     * Example: "ABC" is considered as the number 4407873 = 65 + 66*256 + 67*256^2.
     * Expressed in base radix=65521, the result would be the
     * collection [17966, 67], because 4407873 = 17966 + 67*65521
     *
     * @param string	a string
     * @param radix	a non-negative BigInteger: the radix
     * @return		a List of BigInteger's
     **/
    public static List encode(String string, BigInteger radix) {
	ArrayList digits = new ArrayList(string.length());
	for (int i=0; i<string.length(); i++) {
	    digits.add(BigInteger.valueOf((int)(string.charAt(i))));
	}
	return(toBase(fromBase(digits,BigInteger.valueOf(256)), radix));
    }

    /**
     * Decodes an ASCII string from a list of BigInteger's < radix
     *
     * See encode for the description of the encoding
     *
     * @param string	a collection of non-negative BigInteger's less than radix
     * @param radix	a non-negative BigInteger: the radix
     * @return		a string
     **/
    public static String decode(List digits, BigInteger n) {
	String string = "";
	digits = toBase(fromBase(digits,n), BigInteger.valueOf(256));
	for(Iterator it = digits.iterator(); it.hasNext();) {
	    string = string + (char)(((BigInteger)it.next()).intValue());
	}
	return(string);
    }

    /**
     * Returns a copy of the collection after application of the RSA
     * algorithm with key (n,key) to each BigInteger in the List
     *
     * @param digits	a collection of non-negative BigInteger's < n
     * @param n		a non-negative BigInteger
     * @param key	a non-negative BigInteger
     * @return		a collection of non-negative BigInteger's < n
     **/
    public static List rsa(List digits, BigInteger n, BigInteger key) {
	ArrayList result = new ArrayList(digits.size());
	for(Iterator it = digits.iterator(); it.hasNext(); ) {
	    result.add(((BigInteger)it.next()).modPow(key, n));
	}
	return(result);
    }

    /**
     * Inverse of a big integer modulo m
     *
     * @param n		a BigInteger
     * @param exponent  a BigInteger
     * @param m		a BigInteger
     * @return		a BigInteger: n^power mod m
    **/
    public BigInteger modInverse(BigInteger n, BigInteger power, BigInteger modulo) {
	return new BigInteger("0");
    }

    /**
     * Power of a big integer modulo m
     *
     * @param n		a BigInteger
     * @param exponent  a BigInteger
     * @param m		a BigInteger
     * @return		a BigInteger: n^power mod m
    **/

    public BigInteger modPow(BigInteger n, BigInteger power, BigInteger modulo) {
	return new BigInteger("0");
    }

}