fastexp.java

快速幂级算法 求RSA基础

/*
 * Created on 17.05.2004
 *
 * This program implements the fast exponentiation. 
 */

/**
 * @author Robert
 *
 * This is a class with static functions only.
 * fastExp implements the fast exponentiation.   
 */
public class FastExp {
	static int getCodingLength(int e) {
		int k=0;
		while ((1<<k)<e) ++k;
		return k;
	}
	
	static int fastExp(int g, int e, int n) {
		int l = getCodingLength(e);
		int squares;
		squares = g;
		int result=1;
		//successively compute squares and compute result
		for (int k=0; k<l; ++k) {
			if (((1<<k) & e)>0) {
				result = (result*squares) % n;
			}
			squares = (squares*squares) % n;
		}
		//compute result 
		return result;
	}
	public static void main(String[] args) {
		System.out.println(fastExp(2, 20, 7));
		System.out.println(fastExp(1234, 16912, 2345));
		System.out.println(fastExp(1234, 541200, 2345));
	}
}